在键值数据存储中存储目录层次结构 [英] Storing Directory Hierarchy in a Key-Value Data store

问题描述

有什么干净/有效的方法可以将目录层次结构/树存储在键值数据库中(在我的情况下为MongoDB，但其中任何一个)?

What is a clean/efficient method for storing the directory Hierarchy/tree in a Key-Value database (in my case MongoDB but any of them)?

例如树形结构

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

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

The method I am using now, each object links to it's parent

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

这使得插入树并对其进行重新排序非常高效/快速(例如，如果我想将Red及其所有子项移动到Cars目录中).

This makes it very efficient/fast to insert and reorder any aspect of the tree (for example if I want to move Red and all it's children to the Cars directory).

但是当我要递归地访问给定目录的所有子目录及其子目录时，此方法很糟糕.为了使解析更加有效，我可以使用例如一个结构

But this method sucks when I want to all subdirectories and their children for a given directory recursively. To make it efficient to parse I can have a structure for example

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

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

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

But if I want to modify the tree, a whole bunch of objects need to touched and modified.

还有其他方法可以将目录结构存储在KV商店中吗?

Are there any other methods to storing a directory structure in a KV store?

推荐答案

您当前使用的方法称为邻接表模型.

The method you currently use now is called adjacency list model.

嵌套集模型是将分层数据存储在(关系)数据库中的另一种模型.它的在SQL数据库中的实现是众所周知的.另请参见有关修改的预排序树遍历算法的文章.

Another model to store hierarchical data in a (relational) database is the nested set model. Its implementation in SQL databases is well known. Also see this article for the modified preorder tree traversal algorithm.

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

A very simple method: you could store a path per object - with those it should be easy to query trees in NOSQL databases:

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

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

When nodes will be removed or renamed some paths must be updated. But in general, this method looks promising. You just have to reserve a special character as separator. The storage space overhead should be negligible.

此方法称为具体化路径

最后，这是一个比较NOSQL数据库中用于分层数据的不同方法的说明.

这篇关于在键值数据存储中存储目录层次结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！