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

Question

什么是将目录层次结构/树存储在键值数据库中的干净/有效方法（在我的情况下是MongoDB，但是其中任何一个）？

例如树形结构

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

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

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

这使得插入和重新排序树的任何方面非常有效/快速（例如，如果我想将Red及其所有子项移动到Cars目录中）。

但是当我想要递归地给定目录的所有子目录及其子节点时，这种方法很糟糕。为了使解析有效，我可以有一个结构，例如

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

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

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

是否还有其他方法可以在KV商店中存储目录结构？

Answer 1

您目前使用的方法称为邻接列表模型。

在（关系）数据库中存储分层数据的另一种模型是嵌套集模型。它的 SQL数据库中的实现是众所周知的。另请参阅本文了解修改后的预订树遍历算法。

一个非常简单的方法：您可以存储每个对象的路径 - 在NOSQL数据库中查询树应该很容易：

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

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

编辑：此方法称为物化路径

最后，这里是比较NOSQL数据库中分层数据的不同方法。

Answer 2

我没有大量的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 );
}

这将为您提供每个父目录的子目录列表。

Answer 3

我建议将堆存储到数据项的id中。 我认为这是最好的计划。如果你需要大量的东西，任何堆元素都可以成为另一个堆的索引。

例如

{＆quot; id：xxx＆quot;，＆quot; id：yyy＆quot;，＆quot; sub-heap-id：zzz＆quot; ....}

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

Answer 4

制作索引！

http://www.mongodb.org/display/DOCS/Indexes