利用“海底捞算法”在MongoDB中优雅地存储一棵树

目前常见的树形结构数据库存储方案有以下四种，但是在处理无限深度、海量数据的树结构时，都存在一些问题:
1)Adjacency List（邻接表）：每个节点仅记录父节点主键。优点是简单，缺点是访问子树需要递归遍历，对数据库压力大（即使是支持递归SQL的数据库)。
2)Path Enumerations( 路径枚举)：用一个字符串记录当前节点所在路径。优点是查询方便，缺点是占用空间大，查询需要使用like模糊方法，效率低，插入新记录时要手工更改此节点以下所有路径，维护不便。
3)Closure Table(闭包表)：专门一张表维护Path，缺点是占用空间大，操作不直观。
4)Nested Sets (嵌套集)：记录左值和右值，优点是查询子树无需递归，缺点是非常复杂、难操作。

本文介绍的方案原理详见"基于前序遍历的无递归的树形结构的数据库表设计" ，在这里我给它名叫“海底捞算法”，这个比较形象，因为它要求插入一行EndTag在表格的底部(具有最大行号)。本文是这种算法在MongoDB中的实现示例。

这个算法的优点是简单，支持无限深度树、查询子树时无需递归、删除节点和偶尔插入节点时可以做到无需修改其它记录(行号跳号设计)，从以下示例代码中就可以看出这种方案的简洁性：

Books

|-Programning

| |-Languages

| |-Databases

| | |-MongoDB

| | | |-MongoTree

| | |-dbm

|-Arts

db.book.insert({ _id: “Books”, line:1000,level:1} );

db.book.insert({ _id: “Programming”, line:2000,level:2} );

db.book.insert({ _id: “Languages”, line:3000,level:3} );

db.book.insert({ _id: “Databases”, line:4000,level:3} );

db.book.insert({ _id: “MongoDB”, line:5000,level:4} );

db.book.insert({ _id: “MongoTree”, line:6000,level:5} );

db.book.insert({ _id: “dbm”, line:7000,level:4} );

db.book.insert({ _id: “Arts”, line:8000,level:2} );

db.book.insert({ _id: “EndTag”, line:10000,level:0} );

//查询节点 “Databases”下的所有子节点:

db.book.createIndex( {line:1});

var node = db.book.findOne( { _id: “Databases” } );

var next=db.book.findOne( { $and: [ {line: {$gt:node.line}}, {level:{$lte: node.level }}] } );

db.book.find( {$and: [{line: { $gt: node.line }}, {line: { $lt: next.line }}] } );

//插入一个新节点，不需要对其它行号执行加1操作，因为这个示例中行号是跳号设计的，节点可以插入在两个行号的中间

db.book.insert({ _id: “MySql”, line:6500,level:5} );

//删除一个节点，真接删就可以了

db.book.remove({ _id: “Languages”} );

巴特西

利用“海底捞算法”在MongoDB中优雅地存储一棵树

最新文章

热门文章