且听疯吟如此生活三十年
预排序遍历算法树

mptt

1. 预排序遍历树算法

  • mptt (Modified Preorder Tree Traversal)[^1]
  • 优点
    查询效率高,只需要一次查询即可获得层级结构中某个节点的所有子节点,无需递归查询
  • 缺点
    插入、删除、移动节点效率较低
  • 适用
    在传统关系数据库中实现层级树结构
    • 读压力 > 写压力, mptt 算法可以提高效率
    • 写压力 > 读压力,使用传统的邻接表 (adjacency list model)

2. 增删查改

  • Create

    • 假设增加的节点为 c, 该节点前一节点为 p
    • 节点 c 左值为 p 的右值 +1,右值为 p 右值 +2
    • 所有左值大于节点 c 的左值的节点,其左值均 +2
    • 所有右值大于节点 c 的右值的节点,其右值均 +2
    • 写入节点 c 到数据库
    1
    2
    3
    4
    SELECT @cRight := rgt FROM mptt	WHERE name = 'p';
    UPDATE mptt SET rgt = rgt + 2 WHERE rgt > @cRight ;
    UPDATE mptt SET lft = lft + 2 WHERE lft > @cRight ;
    INSERT INTO mptt(name, lft, rgt) VALUES('c', @cRight+ 1, @cRight+ 2);
  • Read

    • 查询节点 c 的子节点:

      • 查询所有左值大于 c 的左值且右值小于 c 的右值的节点

        1
        SELECT * FROM mptt WHERE lft BETWEEN @cLeft and @cRight;
    • 查询节点 c 的父节点:

      • 查询所有左值小于 c 的左值且右值大于 c 的右值(或左值)的节点

        1
        SELECT * FROM mptt WHERE lft < @cLeft and rgt > @cLeft;
    • 节点 c 的子节点个数:

      • (c.right - c.left - 1) / 2
  • Update
    移动节点即:

    • 删除节点
    • 在指定位置新增节点
  • Delete

    • 删除节点 c
    • 所有右值大于 c 右值的节点,右值 -2
    • 所有左值大于 c 左值的节点,左值 -2
    1
    2
    3
    DELETE FROM mptty WHERE lft BETWEEN @cLeft AND @cRight;
    UPDATE mptt SET rgt = rgt - 2 WHERE rgt > @cRight;
    UPDATE mptt SET lft = lft - 2 WHERE lft > @cLeft;

3. 重建树结构

很容易推断,对排序好的 mptt tree,仅需要一次遍历,即可根据所有节点的左右值记录重建树结构
以 python 为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Node class
class Node(object):

def __init__(self, left, right):
super(Node, self).__init__()
self.left = left
self.right = right
self.depth = 1
self.children = []

# arg: Node List
def rebuild(l):
# 节点按左值排序,即遍历顺序
l.sort(key=lambda x: x.left)

# 使用列表暂存每层子树的父节点
# 如 pi[0] 表示第 2 层的节点的父节点在 l 中的 index
pi = [0]

for i, c in enumerate(l):
if c.left != 1:
p = l[i - 1]

# 使用 c 表示此节点,p 表示 c 的前一节点
# 如果连续的两个节点 c 和 p 的左值增加幅度为 1,则说明其深度增加了 1
# 且 p 为 c 及 c 的兄弟节点的父节点
if c.left == p.left + 1:
c.depth = p.depth + 1
if c.depth - 1 > len(pi):
pi.append(i - 1)
else:
pi[c.depth - 2] = i - 1

# 如果 c 的左值大于 p 的父节点的右值,则说明 p 与 c 并非兄弟节点
# 并可以计算出两节点的深度差为 c 的左值与 p 的右值之差减 1
elif c.left > l[pi[p.depth - 2]].right:
c.depth = p.depth - (c.left - p.right - 1)

# 不满足以上两个条件,说明 c 是 p 的兄弟节点
else:
c.depth = p.depth

# 将 c 作为 pi 中记录的父节点的子节点
l[pi[c.depth - 2]].children.append(c)

return l

Update

完整代码及生成 Json 和基于 D3.js[^2] 的树状图:
https://gist.github.com/caoyue/704e472215af29b08a27

[^1]: [1] http://www.sitepoint.com/hierarchical-data-database-2
[^2]: [2] http://d3js.org