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

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

您现在使用的方法称为adjacency list model。

在(关系)数据库中存储分层数据的另一个模型是nested set model。它的implementation in SQL databases is well known。另请参阅this article for the modified preorder tree traversal algorithm。

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

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

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

edit:此方法称为

最后，这里是a comparison of different methods for hierarchical data in NOSQL databases。

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中。我认为这是最好的计划。如果你需要很多东西，任何heap元素都可以是另一个heap的索引。

例如

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

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