CakePHP Tree Behavior工作原理解析：lft与rght字段值含义探究

嘿，我来帮你把CakePHP Tree Behavior的原理彻底搞懂，尤其是你困惑的lft和rght字段！这个行为背后用的是嵌套集合（Nested Set）模型，专门用来高效存储和操作树形结构数据，比单纯用parent_id关联的方式更适合复杂的树操作（比如批量移动分支、快速获取整个子树）。

你可以把这两个字段理解成深度优先遍历树时的"进入"和"离开"标记：

• 当我们第一次访问一个节点（进入它），就给它分配一个lft值
• 当我们遍历完这个节点的所有子节点，准备离开它时，分配一个rght值

这就形成了一个固定规则：任何节点的lft一定小于它所有子节点的lft，而rght一定大于所有子节点的rght；同时，某个节点的所有后代节点，它们的lft和rght都会落在该节点的lft和rght之间。

我们拿你提供的分类数据走一遍遍历流程，你就能直观看到每个lft和rght是怎么来的：

1. 进入根节点「My Categories」→ 标记lft=1
2. 进入子节点「Fun」→ 标记lft=2
3. 进入「Fun」的子节点「Sport」→ 标记lft=3
4. 进入「Sport」的子节点「Surfing」→ 标记lft=4；它没有子节点，直接离开→标记rght=5
5. 进入「Sport」的另一个子节点「Extreme knitting」→ 标记lft=6；没有子节点，离开→标记rght=7
6. 遍历完「Sport」的所有子节点，离开它→标记rght=8
7. 进入「Fun」的另一个子节点「Friends」→ 标记lft=9
8. 进入「Friends」的子节点「Gerald」→ 标记lft=10；离开→rght=11
9. 进入「Friends」的子节点「Gwendolyn」→ 标记lft=12；离开→rght=13
10. 遍历完「Friends」的所有子节点，离开→rght=14
11. 遍历完「Fun」的所有子节点，离开→rght=15
12. 进入根节点的另一个子节点「Work」→ 标记lft=16
13. 进入「Work」的子节点「Reports」→ 标记lft=17
14. 进入「Reports」的子节点「Annual」→ lft=18；离开→rght=19
15. 进入「Reports」的子节点「Status」→ lft=20；离开→rght=21
16. 离开「Reports」→rght=22
17. 进入「Work」的子节点「Trips」→lft=23
18. 进入「Trips」的子节点「National」→lft=24；离开→rght=25
19. 进入「Trips」的子节点「International」→lft=26；离开→rght=27
20. 离开「Trips」→rght=28
21. 遍历完「Work」的所有子节点，离开→rght=29
22. 遍历完根节点的所有子节点，离开→rght=30

你完全不用手动维护lft和rght值，Behavior会自动帮你处理所有复杂操作：

• 添加节点：它会自动调整目标父节点下所有相关节点的lft/rght值，腾出位置给新节点
• 移动节点：批量更新受影响的所有节点的lft/rght，保证树结构的完整性
• 查询操作：提供了find('threaded')直接返回树形结构数组，还有children()、parentNode()、isChildOf()等方法快速操作树节点

CREATE TABLE categories ( 
    id INTEGER(10) UNSIGNED NOT NULL AUTO_INCREMENT, 
    parent_id INTEGER(10) DEFAULT NULL, 
    lft INTEGER(10) DEFAULT NULL, 
    rght INTEGER(10) DEFAULT NULL, 
    name VARCHAR(255) DEFAULT '', 
    PRIMARY KEY (id) 
); 

INSERT INTO categories (id, name, parent_id, lft, rght) VALUES(1, 'My Categories', NULL, 1, 30); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES(2, 'Fun', 1, 2, 15); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES(3, 'Sport', 2, 3, 8); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES(4, 'Surfing', 3, 4, 5); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES(5, 'Extreme knitting', 3, 6, 7); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES(6, 'Friends', 2, 9, 14); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (7, 'Gerald', 6, 10, 11); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (8, 'Gwendolyn', 6, 12, 13); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (9, 'Work', 1, 16, 29); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (10, 'Reports', 9, 17, 22); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (11, 'Annual', 10, 18, 19); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (12, 'Status', 10, 20, 21); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (13, 'Trips', 9, 23, 28); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (14, 'National', 13, 24, 25); 
INSERT INTO categories (id, name, parent_id, lft, rght) VALUES (15, 'International', 13, 26, 27); 

内容的提问来源于stack exchange，提问作者Sandeep