树结构的数据模型(文件系统):文档模型与图模型

Question

我正在评估一个nosql解决方案,用于实现类似于结构的文件系统,包含数百万个项目,其中主要功能必须是:

• 快速查找由n项属性过滤的项目的"父项"或"直接子项"或"子树项",页面结果按项属性排序.

有这个要求我把问题分成2个任务:

1. 为搜索子项/子树子项建模递归项结构
2. 为物品属性搜索项目结构建模

现在,nosql schema free的强大功能是为每个文件存储不同属性的一个很好的功能,这对第2点很有用.

我对第1点关于使用文档数据库(示例mongodb)以及单个项目集合和物化路径设计模式,或使用带有2个集合的图形数据库(示例arangodb)的优缺点进行了一些疑问:数据(文档集合)和items父母关系(边缘集合)和图形遍历函数.

根据我的要求,使用图形数据库的性能有哪些优势？

图形遍历比物化路径过滤器更有效地完成我的任务？

如果是的话,你能解释一下为什么吗？

谢谢

Answer 1

对于像文件系统这样的层次结构,图形数据库肯定是一个很好的选择.特别是Neo4j,你可以有一个架构,如:

(:Folder)-[:IN_FOLDER]->(:Folder)
(:File)-[:IN_FOLDER]->(:Folder)

查找文件或文件夹就像下面的Cypher一样简单:

MATCH (file:File {path: '/dir/file'})
RETURN file

要直接在文件夹下查找所有文件/文件夹:

MATCH (folder:Folder {path: '/dir'})<-[:IN_FOLDER]-(file_or_folder)
RETURN file_or_folder

如果你想以递归方式找到所有文件/文件夹,你可以这样做:

MATCH (folder:Folder {path: '/dir'})<-[:IN_FOLDER*1..5]-(file_or_folder)
RETURN file_or_folder

该1..5调整您正在搜索的深度(一至五级).

对于所有这些,您需要path属性Folder和File标签的索引.当然,根据您的使用情况,您不需要这样做.

在这种情况下Neo4j可以如此快得多的原因是因为一旦在磁盘上找到一个节点,就可以通过几次文件访问来遍历关系,而不是为每一跳搜索整个表或索引.我建议查看O'Reilly的免费书籍图谱数据库,了解有关Neo4j内部的详细信息.

Answer 2

多模型数据库可以更好地服务于您的用例,该数据库既是文档存储又是图形数据库.使用这样的数据存储,您可以将所有项目作为顶点放在一个集合中,并将层次结构的关系作为边缘放在单独的集合中.此外,您可以存储每个项目的路径并具有已排序的索引,如果常量时间很重要,则可以使用路径属性上的哈希索引.

你会得到的

1. O(1)(常量时间)通过其路径查找项目(使用哈希索引)
2. O(1)通过图形邻居或通过(截断的)路径查找父级
3. 使用图邻居在时间O(n)中找到所有n个直接子节点
4. 通过排序索引中的范围查找以与结果中的项目数成比例的时间查找完整子树
5. 通过添加更多的二级索引来接近任意快速项目访问

1.-4.是最好的,因为复杂性不能比结果集的大小更好.

让我更详细地解释性能参数:

情况1.和2.两种方法都很好,因为您只需要一个结果,您可以直接访问.无论您是否使用哈希索引或让排序索引足够,都可能非常重要.

情况3.(直接子节点)使用图形数据库更快,因为它"找到所有直接邻居"作为一个非常快速的原语.如果您依赖于物化路径和已排序的索引,则无法通过范围查询获取直接子项,因此速度会变慢.

情况4.(整个子树)使用物化路径和使用排序索引的范围查询更快,因为它可以只发出(如果需要,使用迭代器)一个完整的范围.图形数据库必须执行图遍历,这将涉及服务器上的(临时)数据突变以进行枚举.

多模型数据库的优势在于,您可以在单个数据存储中结合使用两种方法(3.和4.)的优点.

这种数据库的一种可能性是ArangoDB数据库.

免责声明:我是主要的开发者之一.