前言
? ? 最近項目在換數據庫循头，從sqlserver轉到mysql，目前正在準備階段集币，可以預見一些問題。比如mysql中沒有一些復雜的函數翠忠；這使得需要重寫一些數據庫語句鞠苟，甚至要改表結構。
遞歸樹查詢是一個其中問題秽之，mysql中沒有with..來查詢其中子孫節(jié)點当娱，所以需要對其進行改造。
繼承關系設計(原來設計)
? ? 表結構：
| 名稱 | 類型 | 備注 |
|---|---|---|
| id | int | PK |
| parent_id | int | 父節(jié)點id |
| name | varchar(255) | 名稱 |
? ?以下是一些實例數據：
? ? 我們首先會想到如上的設計" 這樣的設計符合第三范式" 能正確的表達菜單的樹狀結構且沒有冗余數據"考榨，但在實際開發(fā)中這種設計及其不方便跨细，先來看查詢一個節(jié)點的所有后代，下面是兩層的數據的SQL語句：
SELECT t1.*
FROM tree AS t1 LEFT JOIN tree AS t2
ON t1.id = t2.parent_id
where t2.parent_id=1
? ? 顯然河质，每需要查多一層冀惭，就需要聯結多一次表。SQL查詢的聯結次數是有限的掀鹅，因此不能無限深的獲取所有的后代散休。
? ? 為了實現這樣的層次關系的樹，就需要多次檢索乐尊，通過父節(jié)點檢索出子節(jié)點后戚丸，再根據檢索出的子節(jié)點進行檢索，以此類推直至到葉子節(jié)點扔嵌，這樣的效率對于少量的數據影響還能忍受昏滴，但是當樹節(jié)點擴充到數十條甚至上百條記錄后猴鲫，單單一次菜單顯示就要檢索數十次該表，整個程序的運行效率就會非常差谣殊。
? ? 所以sqlserver2005后就提供了函數with進行遞歸查詢，但是MySQL并沒有類似的函數牺弄，所以只能自定義函數來實現姻几，或者用一個臨時數組或臨時表，然后在內存中遍歷結果势告，這樣就可以不用檢索那么多次數據庫了蛇捌，但這僅僅是把沉重的運算負擔從一個地方轉移到另一個地方，沒有從根本上解決問題咱台。
? ? 下面是用MySQL寫的自定義查詢所有子節(jié)點函數：
CREATE FUNCTION queryChildrenTree(treeId INT)
RETURNS VARCHAR(4000)
BEGIN
DECLARE sTemp VARCHAR(4000);
DECLARE sTempChd VARCHAR(4000);
SET sTemp='$';
SET sTempChd = CAST(treeId AS CHAR);
WHILE sTempChd IS NOT NULL DO
SET sTemp= CONCAT(sTemp,',',sTempChd);
SELECT GROUP_CONCAT(id) INTO sTempChd FROM tree WHERE FIND_IN_SET(parent_id,sTempChd)>0;
END WHILE;
RETURN sTemp;
END;
select * from tree where FIND_IN_SET(parent_id, queryChildrenTree(1))
路徑枚舉
? ? 路徑枚舉的設計是指通過將所有祖先的信息聯合成一個字符串络拌，并保存為每個節(jié)點的一個屬性。
? ? 路徑枚舉是一個由連續(xù)的直接層級關系組成的完整路徑回溺。如"/home/article/details",其中home是article的直接父親春贸，這也就意味著home是details的祖先。
? ?接下來對上面表進行改造：
? ? 表結構（tree1）：
| 名稱 | 類型 | 備注 |
|---|---|---|
| id | int | PK |
| parent_id | int | 父節(jié)點id |
| name | varchar(255) | 名稱 |
| path | varchar(255) | 路徑 |
? ?以下是一些實例數據：
? ?路徑枚舉的優(yōu)點：可以很方便的查詢所有的祖先和后代遗遵。
--查詢所有的子節(jié)點（包括孫子）
select * from tree1 where path like '0/1%'
select * from tree1 where '0/1/4/6' like CONCAT(path,'%')
? ?路徑枚舉的缺點也很明顯：
- 數據庫不能確保路徑的格式總是正確或者路徑中的節(jié)點確實存在(中間節(jié)點被刪除的情況萍恕，沒外鍵約束)。
- 要依賴高級程序來維護路徑中的字符串车要，并且驗證字符串的正確性的開銷很大允粤。
- VARCHAR的長度很難確定。無論VARCHAR的長度設為多大翼岁，都存在不能夠無限擴展的情況类垫。
閉包表
? ?閉包表需要額外創(chuàng)建了一張TreePaths的表(目的：空間換取時間)，它記錄了表中所有的節(jié)點關系琅坡，并不僅僅是直接的父子關系悉患。它包含兩列，每一列都是一個指向tree3中的treeId的外鍵脑蠕。
? ?這種設計主表已經不再維護節(jié)點之間的關系购撼，都是通過外表來維護節(jié)點的關系，下面是兩個表的結構：
主表結構：
| 名稱 | 類型 | 備注 |
|---|---|---|
| id | int | PK |
| name | varchar(255) | 名稱 |
關系記錄表：
| 名稱 | 類型 | 備注 |
|---|---|---|
| id | int | pk |
| ancestor | int | 祖先id |
| descendant | int | 后代id |
| dept | int | 深度 |
主表數據：
關聯表數據：
查詢所有后代節(jié)點：
SELECT t.*,tp.dept FROM tree2 AS t
INNER JOIN TreePath tp on t.id = tp.descendant
WHERE tp.ancestor = 2
結果如圖：
查詢所有祖先節(jié)點：
SELECT c.* FROM Comment AS c
INNER JOIN TreePaths t on c.CommentId = t.ancestor
WHERE t.descendant = 6
結果如圖：
插入數據：
先插入主表的數據谴仙，然后增加該節(jié)點與其關聯的"祖先-后代"關系迂求。
-- 插入主表數據
insert into tree2 values(8,'haha8')
-- 插入關聯數據
insert INTO TreePath(ancestor,descendant,dept)
select t.ancestor,8,(t.dept+1)
from TreePath AS t
where descendant = 5
union all
SELECT 8,8,0
刪除葉子節(jié)點：
刪除指定節(jié)點關聯的treePath窜醉，然后刪除tree數據
DELETE FROM TreePath WHERE descendant = 8
刪除子樹
DELETE FROM treePath
where descendant
in(SELECT descendant FROM treePath WHERE ancestor = 6)
