将目录层次结构/树存储在键值数据库(在我的情况下是 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 存储中存储目录结构吗?
最佳答案
你现在使用的方法叫做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", ... }
当节点将被删除或重命名时,必须更新一些路径。但总的来说,这种方法看起来很有希望。您只需要保留一个特殊字符作为分隔符。存储空间开销应该可以忽略不计。
编辑:这个方法被称为 materialized path
最后,这里是 a comparison of different methods for hierarchical data in NOSQL databases .
https://stackoverflow.com/questions/1619058/