本文由网友
长空X投稿，欢迎转载、分享原文作者：長空 x（csdn 同名“長空 x“，cktools 的作者，github: https://github.com/hjkl950217）
原文連結：https://www.cnblogs.com/gtxck/articles/16293295.html
起因
今天在和懒得勤快聊天时谈到了树形表的处理时，发现目前我俩知道的查树形表都得递归查询，这种方式查询效率是非常底下且不好维护的，那么有没有一种又简单能平行查询的方式呢？后面我俩还真讨论了一种，他快速的修改到他的网站中了。
聲明
文章中的几个方案是我们的讨论结果和一部分网络资料总结。设计方式千万种，文章中介绍的设计方式是针对大部分需要树形表的情况而不代表最优解！最优解已经是集合设计方式、人员水平、业务情况等因素综合之后的方案，这篇分享只是加速找到你的最优解。
什麼是樹形表？
关系型数据库表中，存放树形结构的表。例如某个字段需要选择分类，有一级、二级、...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: 使用 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 查詢出所有數據
分頁查詢：查詢後在內存中修剪掉不需要的數據
這種設計基於這些考慮:
- Id 是数字的情况下，连续的数据
大概率在磁盘上是连续存储，这能提高磁盘 IO 的效率。如果 Id 不是数字，用文章Id创建非聚集索引后也能快速查询。 - 在内存中组装引用关系是非常快的，而且不需要递归就能搞定.(遍历时用 PID 去查找,找到后直接向
ChildNode添加，同时向ParentNode赋值) - 設計邏輯簡單,實習生水平以上的人就能輕鬆維護這種代碼
缺點：如果一顆評論樹有 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 $",2"
分頁查詢：
先用文章 id 按时间排序后查询前 X 个，然后进行第 2 次查询获取楼中楼的数据，第 2 次查询时可以拼多个 startwith。
同时也建议按需冗余level字段以减少查询，path 中虽然隐含了级别数据，但在查询时并不友好。
這種設計基於這些考慮:
- 同方案 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：使用遞歸
前面不是說不使用遞歸嗎？為什麼這裡還要提呢？因為：
- 有些團隊中有人會固執的認為資料庫不應該返回額外數據，也不應加冗餘節點
- mysql 8.0 中增加了 recursive 來在資料庫層面實現遞歸
- 其他無奈
所以如果前面 3 種方案都不適合你的情況，可能你還得回到遞歸這條路線上面，具體的這裡就不提了，網上有許多這類文章。
總結
方案 123 都是通过冗余字段来降低查询成本和理解成本，并且利用不同存储的特性(数据库不适合运算、内存适合快速读写)来实现目标
方案 3 也是，同时也通过分析优化业务实现技术成本与客户体验的共赢。
方案 4 為兜底方案。
我个人比较推崇level+path的组合，这个组合不光能处理评论，也能很好的处理其他的树形结构，毕竟开发人员不能总是有机会影响业务需求不是？
如果你有更好的方案，歡迎留言討論哦~