基本上在每個系統中都有那么幾張表是自關聯父子關系的結構。往往有很多人都是使用pid來做關聯。在剛進入IT行業時使用CAKEPHP框架編寫WEB的時候，使用它里面的一個ACL plugin實現權限管理的時候。發現一個表結構硬是不明白是怎么回事。具體表結構如下：
| CREATE TABLE acos ( id INTEGER(10) UNSIGNED NOT NULL AUTO_INCREMENT, parent_id INTEGER(10) DEFAULT NULL, model VARCHAR(255) DEFAULT '', foreign_key INTEGER(10) UNSIGNED DEFAULT NULL, alias VARCHAR(255) DEFAULT '', lft INTEGER(10) DEFAULT NULL, rght INTEGER(10) DEFAULT NULL, PRIMARY KEY (id)); |
我們可以看到上面 acos 表用有lft、rght這兩個字段。起初我根本就不明白這兩個是做什么用的，幾次直接修改數據導致數據錯亂。
1.2. 原理解釋
其實這就是樹的后續遍歷的每個節點的左值、右值。如下圖表示:
1.3. 樹的使用（引用上圖樹結構）
構造數據
| DROP TABLE IF EXISTS comment;CREATE TABLE `comment` ( `comment_id` int(11) DEFAULT NULL, `left_num` int(11) DEFAULT NULL, `right_num` int(11) DEFAULT NULL);INSERT INTO `comment` VALUES (1,1,14), (2,2,5), (3,3,4), (4,6,13), (5,7,8), (6,9,12), (7,10,11); CREATE INDEX idx$comment$left_num$right_num ON `comment` (`left_num`, `right_num`); |
查找 '節點4' 的所有子節點
思路:我們只要查找出 節點左值在 '節點4' 左值和右值之間的節點
通俗說法:能被 '節點4' 包住的節點,通過左節點和右節點來判斷是否被 '節點4' 包住。
| -- 獲得 '節點4' 孩子SELECT c.*FROM comment AS p, comment AS cWHERE c.left_num BETWEEN p.left_num AND p.right_num AND p.comment_id = 4;+------------+----------+-----------+| comment_id | left_num | right_num |+------------+----------+-----------+| 4 | 6 | 13 || 5 | 7 | 8 || 6 | 9 | 12 || 7 | 10 | 11 |+------------+----------+-----------+ |
查找 '節點6' 的所有父節點
思路: 找出 左值小于 '節點6' 并且 右值大于 '節點6' 的節點。
通俗說法: 找出那個節點能將 '節點6' 給包住。
| -- 獲得 '節點6' 父親SELECT p.* FROM comment AS p, comment AS cWHERE c.left_num BETWEEN p.left_num AND p.right_num AND c.comment_id = 6;+------------+----------+-----------+| comment_id | left_num | right_num |+------------+----------+-----------+| 1 | 1 | 14 || 4 | 6 | 13 || 6 | 9 | 12 |+------------+----------+-----------+ |
計算 '節點4' 的深度
如果是MySQL5.7 需要修改sql_mode
| SET SESSION sql_mode = 'STRICT_TRANS_TABLES,NO_ZERO_IN_DATE,NO_ZERO_DATE,ERROR_FOR_DIVISION_BY_ZERO,NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION';SELECT c.*, COUNT(c.comment_id) AS depthFROM comment AS p, comment AS cWHERE c.left_num BETWEEN p.left_num AND p.right_num AND c.comment_id = 4GROUP BY c.comment_id;+------------+----------+-----------+-------+| comment_id | left_num | right_num | depth |+------------+----------+-----------+-------+| 4 | 6 | 13 | 2 |+------------+----------+-----------+-------+ |
