MongoDB 基础系列六：数据建模之 Tree Structures

发表于 | 更新于 | 分类于 ， ， ， | 阅读次数：

前言

此篇博文是 Mongdb 基础系列之一；主要介绍 MongoDB 的数据建模相关内容；

本文为作者的原创作品，转载需注明出处；

Model Tree Structures

假设我们有如下的树形结构需要通过 MongoDB 进行建模，

那么通过 MongoDB 将如何对其进行建模呢？总共有五种与之对应的 References 的建模方式，我们依次来分析；

Model Tree Structures with Parent References

该建模方式通过在子节点中依次保存其直接父节点外键的方式来构建此树形结构；通过如下命令来创建这种结构，

1
2
3
4
5
6
db.categories.insert( { _id: "MongoDB", parent: "Databases" } )
db.categories.insert( { _id: "dbm", parent: "Databases" } )
db.categories.insert( { _id: "Databases", parent: "Programming" } )
db.categories.insert( { _id: "Languages", parent: "Programming" } )
db.categories.insert( { _id: "Programming", parent: "Books" } )
db.categories.insert( { _id: "Books", parent: null } )

  • 获取某个节点的直接父节点是非常简单直接的

    1
    db.categories.findOne( { _id: "MongoDB" } ).parent

  • 可以在 parent 字段上创建索引，加速查询效率 

    1
    db.categories.createIndex( { parent: 1 } )

  • 可以通过对 parent 字段进行查询，迅速返回所有相关的子节点，

    1
    db.categories.find( { parent: "Databases" } )

Model Tree Structures with Child References

该建模的方式通过在父节点上存储其直接子节点外键的方式来构建此树形结构；通过如下命令来创建这种结构，

1
2
3
4
5
6
db.categories.insert( { _id: "MongoDB", children: [] } )
db.categories.insert( { _id: "dbm", children: [] } )
db.categories.insert( { _id: "Databases", children: [ "MongoDB", "dbm" ] } )
db.categories.insert( { _id: "Languages", children: [] } )
db.categories.insert( { _id: "Programming", children: [ "Databases", "Languages" ] } )
db.categories.insert( { _id: "Books", children: [ "Programming" ] } )

可见，这种方式是通过在父节点中保存相关子节点的外键来构建这种树形结构的；

  • 通过父类节点获取对应的子节点

    1
    db.categories.findOne( { _id: "Databases" } ).children

  • 通过在 children 字段上创建索引来加速访问

    1
    db.categories.createIndex( { children: 1 } )

  • 通过指定 children 字段来查询其父类节点

    1
    db.categories.find( { children: "MongoDB" } )

Child References 的建模优势体现在,

  1. 当无需对 subtrees 子树进行查询的时候；
  2. 当一个子节点拥有多个父节点的饿时候，

Model Tree Structures with an Array of Ancestors

该建模的方式除了使用 parent 字段来保存其直接父类以外，还通过一个 array 类型字段来保存其所有直接或者间接的父类 - 这种方式被称作 Array of Ancestors pattern；

1
2
3
4
5
6
db.categories.insert( { _id: "MongoDB", ancestors: [ "Books", "Programming", "Databases" ], parent: "Databases" } )
db.categories.insert( { _id: "dbm", ancestors: [ "Books", "Programming", "Databases" ], parent: "Databases" } )
db.categories.insert( { _id: "Databases", ancestors: [ "Books", "Programming" ], parent: "Programming" } )
db.categories.insert( { _id: "Languages", ancestors: [ "Books", "Programming" ], parent: "Programming" } )
db.categories.insert( { _id: "Programming", ancestors: [ "Books" ], parent: "Books" } )
db.categories.insert( { _id: "Books", ancestors: [ ], parent: null } )

  • 查找某个节点的所有父类非常直接方便

    1
    db.categories.findOne( { _id: "MongoDB" } ).ancestors

  • 可以通过在 ancestors 字段上创建索引加速查询效率

    1
    db.categories.createIndex( { ancestors: 1 } )

  • 可以通过对 ancestors 字段查询，直接找到该 ancestor 的所有直接或间接子节点

    1
    db.categories.find( { ancestors: "Programming" } )

    因为每个节点都存储了其所有的直接或者间接的父节点；所以，这个查询是显而易见的；

通过这种 Array of Ancestors 的建模方式，可以非常容易且方便的查询到所有的(直接的或间接的)子节点和父节点；不过这种方式比 Materialized Paths 的方式稍慢；

Model Tree Structures with Materialized Paths

该建模的方式通过 path 字段保存每一个节点从根节点的访问路径，path，注意该访问路径中不包含自己，等价于存储了所有相关父节点信息；注意，该 path 节点使用,分隔符，

1
2
3
4
5
6
db.categories.insert( { _id: "Books", path: null } )
db.categories.insert( { _id: "Programming", path: ",Books," } )
db.categories.insert( { _id: "Databases", path: ",Books,Programming," } )
db.categories.insert( { _id: "Languages", path: ",Books,Programming," } )
db.categories.insert( { _id: "MongoDB", path: ",Books,Programming,Databases," } )
db.categories.insert( { _id: "dbm", path: ",Books,Programming,Databases," } )

  • 可以通过如下的方式通过对 path 排序而获取整个 tree，

    1
    db.categories.find().sort( { path: 1 } )

  • 可以通过对 path 字段使用正则表达式查询进而找到 Programming 节点的所有子节点

    1
    db.categories.find( { path: /,Programming,/ } )

    显然，通过对 path 字段使用 Programming 作为关键字进行正则表达式查询会返回所有相关的子节点；

  • 同理，你可以查询得到根节点既 Books 节点的所有相关子节点信息；使用如下的方式进行查询，

    1
    db.categories.find( { path: /^,Books,/ } )

  • 通过在 path 字段上创建索引加速查询效率

    1
    db.categories.createIndex( { path: 1 } )

    该索引 index 将会根据 query 的查询情况来看是否能够帮助其提升性能，

    • 当查询是从 Root 节点开始，将会显著的提升新能，比如查询的正则表达式为 /^,Books,/ or /^,Books,Programming,/
    • 但是，如果不是从 Root 节点开始查询，而是从其中的某个节点开始，比如 /,Databases,/，那么该查询必须检索所有的 indexes；也因此，在 path 字段上的索引帮助不大；

Model Tree Structures with Nested Sets

该建模的方式针对静态树，也就是该树结构不再发生变化，的情况下能够优化查询的性能；其思想是，为每个节点创建两个坐标，一个是起点，一个是终点，表示的是对该树进行一个往返查询，第一次经过该节点(既是出发的过程)的时候标记为起点值，最后一次访问(既是返回的过程)经过该节点标记为终点值，通过依次为每个节点标记起点和终点，这样，我们就非常容易的可以找到其子节点了；如下图所示，

每个节点有两个坐标值，分别表示 round-trip 出发时经过的坐标值(起始坐标值)与回来的时候经过的坐标值(结束坐标值)，该 round-trip 严格的按照从左至右的顺序执行，这样，我们只要通过起始坐标值比当前节点大，结束坐标值比当前节点小，便可以找到当前节点的所有子节点值；

1
2
3
4
5
6
db.categories.insert( { _id: "Books", parent: 0, left: 1, right: 12 } )
db.categories.insert( { _id: "Programming", parent: "Books", left: 2, right: 11 } )
db.categories.insert( { _id: "Languages", parent: "Programming", left: 3, right: 4 } )
db.categories.insert( { _id: "Databases", parent: "Programming", left: 5, right: 10 } )
db.categories.insert( { _id: "MongoDB", parent: "Databases", left: 6, right: 7 } )
db.categories.insert( { _id: "dbm", parent: "Databases", left: 8, right: 9 } )

比如我们要查询 Database 所有相关的子节点，可以使用如下的查询语句，

1
2
var databaseCategory = db.categories.findOne( { _id: "Databases" } );
db.categories.find( { left: { $gt: databaseCategory.left }, right: { $lt: databaseCategory.right } } );

既是查询起始坐标值( left )比 Database 节点的大，结束坐标值( right )比 Ddatabase 要小的结果集；

我的思考，如果是真的是对静态树进行查询，使用 Array of Ancestors 或者 Materialized Paths 模式感觉都不比这个方式差，而且这两种方式还可以直接查询所有的父节点，既是可以反向查询；

Reference

https://docs.mongodb.com/manual/applications/data-models-tree-structures/