通常樹形結構的存儲，是在子節(jié)點上存儲父節(jié)點的編號來確定各節(jié)點的父子關系，例如這樣的組織結構：

與之對應的表數(shù)據(jù)(department)：

部門表結構（department）

id??????????部門編號
name????????部門名稱
level???????所在樹層級
parent_id???上級部門編號
復制代碼

1、問題來了

這樣的方式很不錯，可以很直觀的體現(xiàn)各個節(jié)點之間的關系，通?？梢詽M足大多數(shù)需求。但是當業(yè)務需求變得多了，數(shù)據(jù)量龐大了，這樣的方式就不再適合用于生產。

例如：PM加了以下需求：

1. 查出指定部門下所有子孫部門。
2. 查詢子孫部門總數(shù)。
3. 判斷節(jié)點是否葉子節(jié)點。

查出所有子孫部門

使用指定部門編號，一層一層使用遞歸往下查，可能是多數(shù)人會想到的方法。盡管在mysql8.0支持了 cte(公共表表達式)，遞歸效率比傳統(tǒng)遞歸方式有明顯提升，但是查詢效率仍會隨著部門樹層級深度的提高而變差。

另外一種方法，一次性查出所有數(shù)據(jù)，放入內存中處理（數(shù)據(jù)量少時，可以選用。數(shù)據(jù)量多，不怕挨打的人也可以選這種）~

查詢子孫部門總數(shù)

遞歸查詢每一層的數(shù)量，最后相加。

判斷是否葉子節(jié)點

方法1：可以加字段isLeaf的方式，來表示這個節(jié)點是否是葉子節(jié)點。

方法2：直接通過查詢parent_id=當前id的count是否大于0，大于0表示不是葉子節(jié)點，等于0表示為葉子節(jié)點。

在日常中，可能會經常使用上述類似方法去解決類似的問題，但我覺得這樣的方法在效率上不是最優(yōu)解。于是乎開始查找更好的方案去解決這些問題。

要不試試這個方法？

直到后面查到國外一博客中，見到了所謂的《改進后的先序樹遍歷》文章（天哪，竟然是一篇2003年發(fā)表的文章）~

他具體是怎么做的呢？

還是回到剛剛的組織架構

我們從根節(jié)點開始，給董事長左值設為1，下級部門總經理左值設為2，以此類推地沿著邊緣開始遍歷，給每個節(jié)點加上左值，遇到葉子節(jié)點處給節(jié)點加上右值，再繼續(xù)向上沿著邊緣繼續(xù)遍歷，遍歷結束回到根節(jié)點右側,你將得到類似這樣的結構。

遍歷完后每一個節(jié)點都有與之對應的左右值。這個時候可以去除parent_id字段，添加lft,rgt，來存儲左右值。

數(shù)據(jù)和結構準備完畢，我們來試試操作解決上面的需求~

查出所有子孫部門

根據(jù)當前表結構的規(guī)律，可以發(fā)現(xiàn)，要想查出所有子孫部門，只要查左值在 被查尋部門的左\右數(shù)之間的節(jié)點，查出來都是他的子節(jié)點。例如：查詢行政總監(jiān)的所有子部門，行政總監(jiān)的左右數(shù)是9和18，因此只需要用9和18做lft字段的between查詢，查詢出的結果就是【被查部門本身數(shù)據(jù)和所有子孫部門】；

SET?@lft?:=?9;
SET?@rgt?:=?18;
SELECT?*?FROM?department?WHERE?lft?BETWEEN?@lft?AND?@rgt?ORDER?BY?lft?ASC;
/*例子中用BETWEEN將被查部門本身也查了出來。實際中可以用大于小于*/

完美~

查詢子孫部門總數(shù)

到這里可能會說，需求1都解決了，查總數(shù)自然也就解決了，直接上select count就可以了，確實沒有錯，但是沒有那個必要，因為有個簡單公式可以直接計算

公式：總數(shù) = (右值 - 左值 - 1) / 2

例如：

行政總監(jiān)的子孫部門數(shù)?=?(18?-?9?-?1)?/?2?=?4

董事長的子孫部門數(shù)?=?(20?-?1?-?1)?/?2?=?9

會計的子部門數(shù)?=??(14?-?13?-?1)?/?2?=?0

可以數(shù)數(shù)看，確實沒錯哦～

判斷是否葉子節(jié)點

通過有了上述計算公式算總數(shù)的經驗后，現(xiàn)在判斷是否葉子節(jié)點，有的小伙伴已經知道了怎么做，那就是：

右值 - 1 == 左值那他就是葉子節(jié)點，或者左值 + 1 == 右值那他就是葉子節(jié)點，反之則不是葉子節(jié)點。

例如：

設計部，5 - 1 == 4，因此他是葉子節(jié)點。

董事長，20 - 1 != 1，因此他不是葉子節(jié)點。

至此已經完美的解決了上述需求問題，接下來再嘗試一下業(yè)務的基本操作。

我們創(chuàng)建了一個高質量的技術交流群，與優(yōu)秀的人在一起，自己也會優(yōu)秀起來，趕緊點擊加群，享受一起成長的快樂。另外，如果你最近想跳槽的話，年前我花了2周時間收集了一波大廠面經，節(jié)后準備跳槽的可以點擊這里領取！

其他基本操作

新增部門

當新增一個部門時，需要對新增節(jié)點位置的后續(xù)邊緣進行加2操作，因為每一個節(jié)點有左右兩個數(shù)值。這個操作通常需要放到事務中進行處理。例如：在研發(fā)部門下添加一個新部門：

對應sql：

SET?@lft?:=?7;/*新部門的左值*/
SET?@rgt?:=?8;/*新部門的左值*/
SET?@level?:=?5;/*新部門的層級*/
begin;
/*將插入的后續(xù)邊緣的節(jié)點左右數(shù)+2*/
UPDATE?department?SET?lft=lft+2?WHERE?lft?>?@lft;
UPDATE?department?SET?rgt=rgt+2?WHERE?rgt?>=?@lft;
/*插入數(shù)據(jù)*/
INSERT?INTO?department(name,lft,rgt,level)?VALUES('新部門',@lft,@rgt,level);
/*新增影響行數(shù)為0時，必須回滾*/
commit;
/*rollback;*/

刪除部門

刪除部門與新增部門類似，不同的是需要對刪除節(jié)點的后續(xù)邊緣節(jié)點減2操作。例如：刪除剛剛添加的新部門：

對應sql

SET?@lft?:=?7;/*要刪除的節(jié)點左值*/
SET?@rgt?:=?8;/*要刪除的節(jié)點右值*/
begin;
UPDATE?department?SET?lft=lft-2?WHERE?lft?>?@lft;
UPDATE?department?SET?rgt=rgt-2?WHERE?rgt?>?@lft;

/*刪除節(jié)點*/
DELETE?FROM?department?WHERE?lft=@lft?AND?rgt=@rgt;
/*刪除影響行數(shù)為0時，必須回滾*/
commit;
/*rollback*/

查詢直接子部門

查詢某部門的直接子部門（即不包含孫子部門），例如：查詢總經理下的直接子部門。正常需要返回產品部和行政總監(jiān)

對應的sql

SET?@level?:=?2;/*總經理的level*/
SET?@lft?:=?2;/*總經理的左值*/
SET?@rgt?:=?19;/*總經理的右值*/

SELECT?*?FROM?department?WHERE?lft?>?@lft?AND?rgt?AND?level?=?@level+1;

查詢祖鏈路徑

查詢某部門的祖鏈路徑。例如：查詢產品部的祖鏈路徑，正常需要返回董事長,總經理

SET?@lft?:=?3;/*產品部左值*/
SET?@rgt?:=?8;/*產品部右值*/

SELECT?*?FROM?department?WHERE?lft?AND?rgt?>?@rgt?ORDER?BY?lft?ASC;

樹形數(shù)據(jù)展示（JS示例）

查出的列表數(shù)據(jù)，轉成樹形結構，示例：

let?list?=?[//模擬sql查出來的列表。
????{id:1,name:'root',lft:1,rgt:8,level:1},
????{id:2,name:'child',lft:2,rgt:7,level:2},
????{id:3,name:'grandson',lft:3,rgt:4,level:3},
????{id:4,name:'grandson2',lft:5,rgt:6,level:3}
];
let?rights?=?[]?/*類似于一個棧結構（后進先出）*/
let?mp?=?{}
//list.sort((a,b)?=> a.lft - b.lft)//如果你在sql中沒有進行排序，需要在這里給他排序。
list.forEach(item?=>?{
????if(rights.length?>?0)?{
????????while(rights[rights.length-1]?????????????rights.splice(-1,?1)//從rights末尾去除
????????}
????}
????let?_level?=?rights.length;
????item._level?=?_level;
????mp[_level]?=?item.id
????item.parent_id?=?_level?-?1?in?mp???mp[_level?-?1]?:?null;//計算出上級部門編號
????item.is_leaf?=?item.lft?===?item.rgt?-?1;//判斷是否葉子部門
????rights.push(item.rgt)
})

/*上級部門計算出來了，和存parent_id的效果就一樣了，后面只需要遞歸即可*/
/*遞歸函數(shù)?示例*/
let?recursive?=?(_list,?parent_id?=?null)?=>?{
????let?_tree?=?[];
????_list.forEach(item?=>?{
????????if(item.parent_id?==?parent_id)?{
????????????let?childs?=?recursive(_list,?item.id)
????????????_tree.push({
????????????????...item,
????????????????children:?childs.length?>?0???childs?:?(item.isLeaf???null?:?[])
????????????})
????????}
????})
????return?_tree
}
console.log(recursive(list))

完結

在我目前看來，這個方法的唯一缺點就是，每一次的新增或刪除，操作節(jié)點的后續(xù)邊緣走到的節(jié)點都要加/減2操作。

歡迎指正、交流和評論，一起探討更多解決方案。。。

來源：juejin.cn/post/7076079848824766494