本文由網友長空X投稿，歡迎轉載、分享

原文作者：長空X（CSDN同名“長空X“，CkTools的作者，github: https://github.com/hjkl950217）

原文鏈接：https://www.cnblogs.com/gtxck/articles/16293295.html

起因

今天在和懶得勤快^[1]聊天時談到了樹形表的處理時，發現目前我倆知道的查樹形表都得遞歸查詢，這種方式查詢效率是非常底下且不好維護的，那么有沒有一種又簡單能平行查詢的方式呢？后面我倆還真討論了一種，他快速的修改到他的網站中了。

懶得勤快官網

聲明

文章中的幾個方案是我們的討論結果和一部分網絡資料總結。設計方式千萬種，文章中介紹的設計方式是針對大部分需要樹形表的情況而不代表最優解！最優解已經是集合設計方式、人員水平、業務情況等因素綜合之后的方案，這篇分享只是加速找到你的最優解。

什么是樹形表？

關系型數據庫表中，存放樹形結構的表。例如某個字段需要選擇分類，有一級、二級、...N級，可以這樣設計：

ID	PID	名字或內容
1		評論1
2	1	評論2
3	1	評論3
4	3	評論4

這樣的數據可以組合成我們大學數據結構中的樹，用來表達層級關系。這里的Id一般情況下用數字最好,但也有不是數字的情況，這點對選擇方案可能有影響，后面會提到這一點。這種數據結構的實體定義一般如下:

class?CommentEntity
{public?int?ID?{get;set;}public?int?PID?{get;set;}//..?若干數據字段public?CommentEntity?ParentNode?{get;set;}public?List<CommentEntity>?ChildNode?{get;set;}
}

實體定義ParentNode指向父節點,ChildNode指向若干子節點。如果你有數據結構中的鏈表知識，能看出這2個字段起指針域的作用。

數據在數據庫中按行存儲，如果我們將數據獲取出來后組裝好ParentNode和ChildNode中的指向，然后就能按你的實際業務情況使用了。

有什么用？

有所屬關系的都可以用這種方式存，例如: 權限關系、分類、類型、級別劃分、行政區劃、評論等等等...

但他麻煩之處在于查詢不方便。比如想要查詢一級分類下面的所有數據，按傳統方式需要先查到id=1的一級分類，再查詢PID=1的數據，再查詢PID=剛才查詢的數據ID 這樣遞歸查詢多次直到結束

目標

我們以評論為例

需要滿足：

1. 進頁面時分頁查詢出主評論,然后按層次關系顯示回評

2. 可以根據某一個評論查詢下屬所有評論

3. 平行查詢而不是遞歸查詢

4. 每個評論數據可以是主評判，也可以是子評論

方案1: 使用tag標記樹

這個方案是添加一個字段tag來標記整顆樹，結構如下:

ID	PID	Tag	內容
1		文章Id1	評論1
2	1	文章Id1	評論2
3	1	文章Id1	評論3
4	3	文章Id1	評論4

Tag用于數據庫查詢，ID和PID用于內存中組裝數據，同時對Tag這一列建立非聚集索引。

查詢方式：

這里新增的字段在每課樹中都是一樣的，最多查詢2次數據庫即可，然后自己在內存中用Pid重新排列引用關系，修剪掉不需要的數據。

第一次查詢：用評論id查詢出文章id(有文章Id時直接第二步)

第二次查詢：用文章id查詢出所有數據

分頁查詢：查詢后在內存中修剪掉不需要的數據

這種設計基于這些考慮:

1. Id是數字的情況下，連續的數據大概率在磁盤上是連續存儲，這能提高磁盤IO的效率。如果Id不是數字，用文章Id創建非聚集索引后也能快速查詢。

2. 在內存中組裝引用關系是非常快的，而且不需要遞歸就能搞定.(遍歷時用PID去查找,找到后直接向ChildNode添加，同時向ParentNode賦值)

3. 設計邏輯簡單,實習生水平以上的人就能輕松維護這種代碼

缺點：如果一顆評論樹有1000層，那無疑會獲取巨量的無用數據

改進：使用level標記級別

增加級別字段:

ID	PID	tag	level	內容
1		文章Id1	1	評論1
2	1	文章Id1	2	評論2
3	1	文章Id1	2	評論3
4	3	文章Id1	3	評論4

查詢時附加上level，能減少一部分無用數據的傳輸，最后復用上面的組裝代碼。

方案2: 使用path標記依賴路徑

借用網上的一張圖直接說明思路(未找到出處,侵權刪除):

結合上面說的改造一下:

ID	PID	Tag	Path	內容
1		文章Id1		評論1
2	1	文章Id1	1	評論2
3	1	文章Id1	1	評論3
4	3	文章Id1	1,2	評論4

在寫入子節點時需要知道父節點的path，但一般來說這點是能滿足的。Tag和Path用于數據庫查詢，ID和PID用于內存中組裝數據。

查詢方式：

查詢全部：仍文章id查詢所有數據，然后在內存中用Pid組裝

查詢id為2及下面的數據：

第一次查詢：查詢id=2的path

第二次查詢：查詢 ?id=2 or startwith $"{path},2"

分頁查詢：

先用文章id按時間排序后查詢前X個，然后進行第2次查詢獲取樓中樓的數據，第2次查詢時可以拼多個 startwith。

同時也建議按需冗余level字段以減少查詢，path中雖然隱含了級別數據，但在查詢時并不友好。

這種設計基于這些考慮:

1. 同方案1差不多，并且理解成本更低

缺點：不算特別的缺點，在查詢子節點數據用path過濾時，是利用不上索引的。

方案3: 不設計樓中樓

借鑒知乎的設計，一看就懂系列：

知乎的結構中只有評論和回評，回評也只需要保存上一次評論的id即可。這種方式不光設計簡單，閱讀體驗也極好（樓中樓深了并非不好看）

ID	PID	GroupID	Tag	內容
1		1	文章Id1	評論1
2	1	1	文章Id1	評論2
3	1	1	文章Id1	評論3
4	3	1	文章Id1	評論4
5		2	文章Id1	評論5

查詢方式：

查詢全部：仍文章id查詢所有PID is null的數據，然后在內存中用PID組裝

查詢id為1及下面的數據：查詢 GroupID = 1的數據。這種設計時不會單獨查詢回評的數據

優點：理解成本非常低，同時存儲壓力也小

方案4：使用遞歸

前面不是說不使用遞歸嗎？為什么這里還要提呢？因為：

1. 有些團隊中有人會固執的認為數據庫不應該返回額外數據，也不應加冗余節點

2. mysql 8.0 中增加了RECURSIVE來在數據庫層面實現遞歸

3. 其它無奈

所以如果前面3種方案都不適合你的情況，可能你還得回到遞歸這條路線上面，具體的這里就不提了，網上有許多這類文章。

總結

方案123都是通過冗余字段來降低查詢成本和理解成本，并且利用不同存儲的特性(數據庫不適合運算、內存適合快速讀寫)來實現目標

方案3也是，同時也通過分析優化業務實現技術成本與客戶體驗的共贏。

方案4為兜底方案。

我個人比較推崇level+path的組合，這個組合不光能處理評論，也能很好的處理其它的樹形結構，畢竟開發人員不能總是有機會影響業務需求不是？

如果你有更好的方案，歡迎留言討論哦~

參考資料

[1]

懶得勤快: https://masuit.org/