代码之家 › 专栏 › 技术社区 › The Unknown

在键值数据存储中存储目录层次结构

key-value mongodb

The Unknown · 技术社区 · 15 年前

在键值数据库中存储目录层次结构/树的干净/高效的方法是什么(在我的例子中是MongoDB,但有任何一种方法)?

例如树结构

- Cars 
   + Audi 
   + BMW
      - M5
   + Ford
- Color
   + Red
      - Apple
      - Cherry
   + Purple
- Funny

我现在使用的方法,每个对象都链接到它的父对象

{ 
  dir: "red"
  parent-dir: "color"
}

这使得插入和重新排序树的任何方面非常有效/快速(例如,如果我想将红色及其所有子项移动到cars目录中)。

但是当我想递归地访问给定目录的所有子目录及其子目录时,这个方法很糟糕。为了提高解析效率,我可以有一个结构,例如

{ 
  dir: "red"
  children: "audi, bmw, ford"
}

{ 
  dir: "bmw"
  children: "m5"
}

但是如果我想修改树,需要对一大堆对象进行触摸和修改。

在Kv存储中,是否有其他方法来存储目录结构?

4 回复 | 直到 9 年前

nedim Thiago Chaves 13 年前

调用当前使用的方法 adjacency list model .

一个非常简单的方法:您可以为每个对象存储一个路径—使用这些路径,可以很容易地在NoSQL数据库中查询树:

{ path: "Color", ... }
{ path: "Color.Red", ... }
{ path: "Color.Red.Apple", ... }
{ path: "Color.Red.Cherry", ... }

删除或重命名节点时,必须更新某些路径。但总的来说,这种方法看起来很有前途。您只需要保留一个特殊字符作为分隔符。存储空间开销应该可以忽略不计。

编辑:此方法被调用 materialized path

Emily 15 年前

我没有太多的NoSQL经验,所以这不是一个确定的答案,但下面是我将如何处理它:

我可能会使用您的第一种方法,其中您有:

{
  dir: 'dir_name',
  parent_dir: 'parent_dir_name'
}

然后设置一个map reduce来快速查询一个目录的子目录。MongoDB的map reduce功能只在开发分支中可用,我还没有使用过,但是在CouchDB中(我假设,经过一些修改,在MongoDB中),您可以执行如下操作:

map:
function(doc) {
  emit( doc.parent_dir, doc.dir );
}

reduce:
function(key, values) {
  return( values );
}

-1

Hogan 15 年前

我建议将堆存储到数据项的ID中。我认为这是最好的计划。如果您需要很多东西,任何堆元素都可以是另一个堆的索引。

如

{ "id:xxx", "id:yyy", "sub-heap-id:zzz"....}

如果这不清楚,发表评论,我回家后会解释更多。

-3

Matt Williamson 15 年前

做个索引!