最近在開(kāi)發(fā)jSqlBox過(guò)程中，研究樹(shù)形結(jié)構(gòu)的操作，突然發(fā)現(xiàn)一種簡(jiǎn)單的樹(shù)結(jié)構(gòu)數(shù)據(jù)庫(kù)存儲(chǔ)方案，在網(wǎng)上找了一下，沒(méi)有找到雷同的（也可能是花的時(shí)間不夠），現(xiàn)介紹如下:

目前常見(jiàn)的樹(shù)形結(jié)構(gòu)數(shù)據(jù)庫(kù)存儲(chǔ)方案有以下四種，但是都存在一定問(wèn)題:

1)Adjacency List:：記錄父節(jié)點(diǎn)。優(yōu)點(diǎn)是簡(jiǎn)單，缺點(diǎn)是訪問(wèn)子樹(shù)需要遍歷，發(fā)出許多條SQL，對(duì)數(shù)據(jù)庫(kù)壓力大。

2)Path Enumerations：用一個(gè)字符串記錄整個(gè)路徑。優(yōu)點(diǎn)是查詢方便，缺點(diǎn)是插入新記錄時(shí)要手工更改此節(jié)點(diǎn)以下所有路徑，很容易出錯(cuò)。

3)Closure Table：專門一張表維護(hù)Path，缺點(diǎn)是占用空間大，操作不直觀。

4)Nested Sets：記錄左值和右值，缺點(diǎn)是復(fù)雜難操作。

以上方法都存在一個(gè)共同缺點(diǎn)：操作不直觀，不能直接看到樹(shù)結(jié)構(gòu)，不利于開(kāi)發(fā)和調(diào)試。

本文介紹的第一種方法我暫稱它為“簡(jiǎn)單粗暴多列存儲(chǔ)法”或稱為"朱氏深度樹(shù)V1.0法"(如已有人發(fā)明過(guò),刪掉頭兩個(gè)字就好了）,因?yàn)橄旅孢€有改進(jìn)版。它與Path-Enumerations模式有點(diǎn)類似，但區(qū)別是用很多的數(shù)據(jù)庫(kù)列來(lái)存儲(chǔ)一個(gè)占位符(1或空值)，如下圖(https://github.com/drinkjava2/Multiple-Columns-Tree/blob/master/treemapping.jpg) 左邊的樹(shù)結(jié)構(gòu)，映射在數(shù)據(jù)庫(kù)里的結(jié)構(gòu)見(jiàn)右圖表格：

各種SQL操作如下：

```

1.獲取(或刪除)指定節(jié)點(diǎn)下所有子節(jié)點(diǎn)，已知節(jié)點(diǎn)的行號(hào)為"X",列名"cY":

select *(or delete) from tb where

line>=X and line<(select min(line) from tb where line>X and? (cY=1 or c(Y-1)=1 or c(Y-2)=1 ... or c1=1))

例如獲取D節(jié)點(diǎn)及其所有子節(jié)點(diǎn)：

select * from tb where line>=7 and line< (select min(line) from tb where line>7 and (c2=1 or c1=1))

刪除D節(jié)點(diǎn)及其所有子節(jié)點(diǎn)：

delete from tb where line>=7 and line< (select min(line) from tb where line>7 and (c2=1 or c1=1))

僅獲取D節(jié)點(diǎn)的次級(jí)所有子節(jié)點(diǎn)：

select * from tb where line>=7 and c3=1 and line< (select min(line) from tb where line>7 and (c2=1 or c1=1))

2.查詢指定節(jié)點(diǎn)的根節(jié)點(diǎn), 已知節(jié)點(diǎn)的行號(hào)為"X",列名"cY":

select * from tb where line=(select max(line) from tb where line<=X and c1=1)

例如查I節(jié)點(diǎn)的根節(jié)點(diǎn)：

select * from tb where line=(select max(line) from tb where line<=12 and c1=1)

3.查詢指定節(jié)點(diǎn)的上一級(jí)父節(jié)點(diǎn), 已知節(jié)點(diǎn)的行號(hào)為"X",列名"cY":

select * from tb where line=(select max(line) from tb where line

例如查L(zhǎng)節(jié)點(diǎn)的上一級(jí)父節(jié)點(diǎn)：

select * from tb where line=(select max(line) from tb where line<11 and c3=1)

3.查詢指定節(jié)點(diǎn)的所有父節(jié)點(diǎn), 已知節(jié)點(diǎn)的行號(hào)為"X",列名"cY":

select * from tb where line=(select max(line) from tb where line

union select * from tb where line=(select max(line) from tb where line

...

union select * from tb where line=(select max(line) from tb where line

例如查I節(jié)點(diǎn)的所有父節(jié)點(diǎn)：

select * from tb where line=(select max(line) from tb where line<12 and c2=1)

union? select * from tb where line=(select max(line) from tb where line<12 and c1=1)

4.插入新節(jié)點(diǎn)：

視需求而定，例如在J和K之間插入一個(gè)新節(jié)點(diǎn)T：

update tb set line=line+1 where line>=10;

insert into tb (line,id,c4) values (10,'T',1)

這是與Path Enumerations模式最大的區(qū)別，插入非常方便，只需要利用SQL將后面的所有行號(hào)加1即可，無(wú)須花很大精力維護(hù)path字串，

不容易出錯(cuò)。

另外如果表非常大，為了避免update tb set line=line+1 造成全表更新，影響性能，可以考慮增加

一個(gè)GroupID字段，同一個(gè)根節(jié)點(diǎn)下的所有節(jié)點(diǎn)共用一個(gè)GroupID，所有操作均在groupID組內(nèi)進(jìn)行，例如插入新節(jié)點(diǎn)改為:

update tb set line=line+1 where groupid=2 and line>=8;

insert into tb (groupid,line,c4) values (2, 8,'T')

因?yàn)橐粋€(gè)groupid下的操作不會(huì)影響到其它groupid,對(duì)于復(fù)雜的增刪改操作甚至可以在內(nèi)存中完成操作后，一次性刪除整個(gè)group的內(nèi)容

并重新插入一個(gè)新group即可。

```

總結(jié)：

以上介紹的這種方法優(yōu)點(diǎn)有：

1）直觀易懂，方便調(diào)試，是所有樹(shù)結(jié)構(gòu)數(shù)據(jù)庫(kù)方案中唯一所見(jiàn)即所得，能夠直接看到樹(shù)的形狀的方案，空值的采用使得樹(shù)形結(jié)構(gòu)一目了然。

2）SQL查詢、刪除、插入非常方便，沒(méi)有用到Like語(yǔ)法。

3）只需要一張表

4） 兼容所有數(shù)據(jù)庫(kù)

5）占位符即為實(shí)際要顯示的內(nèi)容應(yīng)出現(xiàn)的地方，方便編寫(xiě)Grid之類的表格顯示控件

缺點(diǎn)有

1)不是無(wú)限深度樹(shù)，數(shù)據(jù)庫(kù)最大允許列數(shù)有限制，通常最多為1000，這導(dǎo)致了樹(shù)的深度不能超過(guò)1000，而且考慮到列數(shù)過(guò)多對(duì)性能也有影響, 使用時(shí)建議定一個(gè)比較小的深度限制例如100。

2)SQL語(yǔ)句比較長(zhǎng)，很多時(shí)候會(huì)出現(xiàn)c9=1 or c8=1? or c7=1 ... or c1=1這種n階乘式的查詢條件

3)樹(shù)的節(jié)點(diǎn)整體移動(dòng)操作比較麻煩，需要將整個(gè)子樹(shù)平移或上下稱動(dòng)，當(dāng)節(jié)點(diǎn)須要經(jīng)常移動(dòng)時(shí)，不建議采用這種方案。對(duì)于一些只增減，不常移動(dòng)節(jié)點(diǎn)的應(yīng)用如論壇貼子和評(píng)論倒比較合適。

4)列非常多時(shí)，空間占用有點(diǎn)大。

##以下為改進(jìn)版，是建立在前述基礎(chǔ)上，一種更簡(jiǎn)單的無(wú)限深度樹(shù)方案

上面第一種方法比較笨拙，如果不用多列而是只用一個(gè)列來(lái)存儲(chǔ)一個(gè)深度等級(jí)數(shù)值，則可以不受數(shù)據(jù)庫(kù)列數(shù)限制，從而進(jìn)化為無(wú)限深度樹(shù)，雖然不再具有所見(jiàn)即所得的效果，但是在性能和簡(jiǎn)單性上要遠(yuǎn)遠(yuǎn)超過(guò)上述“簡(jiǎn)單粗暴多列存儲(chǔ)法”，暫時(shí)給它取名"朱氏深度樹(shù)V2.0法"(呵呵如果沒(méi)人發(fā)明過(guò)的話），介紹如下：

如下圖 (https://github.com/drinkjava2/Multiple-Columns-Tree/blob/master/treemappingv2.png) 左邊的樹(shù)結(jié)構(gòu)，映射在數(shù)據(jù)庫(kù)里的結(jié)構(gòu)見(jiàn)右圖表格，注意每個(gè)表格的最后一行必須有一個(gè)END標(biāo)記，level設(shè)為0：

```

1.獲取指定節(jié)點(diǎn)下所有子節(jié)點(diǎn)，已知節(jié)點(diǎn)的行號(hào)為X,level為Y, groupID為Z

select * from tb2 where groupID=Z and

line>=X and line<(select min(line) from tb where line>X and level<=Y and groupID=Z)

例如獲取D節(jié)點(diǎn)及其所有子節(jié)點(diǎn)：

select * from tb2 where groupID=1 and

line>=7 and line< (select min(line) from tb2 where groupid=1 and line>7 and level<=2)

刪除和獲取相似，只要將sql中select * 換成delete即可。

僅獲取D節(jié)點(diǎn)的次級(jí)所有子節(jié)點(diǎn)：(查詢條件加一個(gè)level=Y+1即可)：

select * from tb2 where groupID=1 and

line>=7 and level=3 and line< (select min(line) from tb2 where groupid=1 and line>7 and level<=2)

2.查詢?nèi)我夤?jié)點(diǎn)的根節(jié)點(diǎn), 已知節(jié)點(diǎn)的groupid為Z

select * from tb2 where groupID=Z and line=1 (或level=1)

3.查詢指定節(jié)點(diǎn)的上一級(jí)父節(jié)點(diǎn), 已知節(jié)點(diǎn)的行號(hào)為X,level為Y, groupID為Z

select * from tb2 where groupID=Z and

line=(select max(line) from tb2 where groupID=Z and line

例如查L(zhǎng)節(jié)點(diǎn)的上一級(jí)父節(jié)點(diǎn)：

select * from tb2 where groupID=1

and line=(select max(line) from tb2 where groupID=1 and line<11 and level=3)

4.查詢指定節(jié)點(diǎn)的所有父節(jié)點(diǎn), 已知節(jié)點(diǎn)的line=X,level=Y:

select * from tb2 where groupID=Z and

line=(select max(line) from tb2 where groupID=Z and line

union select * from tb2 where groupID=Z and

line=(select max(line) from tb2 where groupID=Z and line

...

union select * from tb2 where groupID=Z and

line=(select max(line) from tb2 where groupID=Z and line

例如查I節(jié)點(diǎn)的所有父節(jié)點(diǎn)：

select * from tb2 where groupID=1 and

line=(select max(line) from tb2 where groupID=1 and line<12 and level=2)

union? select * from tb2 where groupID=1 and

line=(select max(line) from tb2 where groupID=1 and line<12 and level=1)

5.插入新節(jié)點(diǎn)：例如在J和K之間插入一個(gè)新節(jié)點(diǎn)T：

update tb2 set line=line+1 where? groupID=1 and line>=10;

insert into tb (groupid,line,id,level) values (1,10,'T',4);

```

總結(jié)：

此方法優(yōu)點(diǎn)有：

1） 是無(wú)限深度樹(shù)

2） 雖然不象第一種方案那樣具有所見(jiàn)即所得的效果，但是依然具有直觀易懂，方便調(diào)試的特點(diǎn)。

3） 能充分利用SQL，查詢、刪除、插入非常方便，SQL比第一種方案簡(jiǎn)單多了，也沒(méi)有用到like模糊查詢語(yǔ)法。

4） 只需要一張表。

5） 兼容所有數(shù)據(jù)庫(kù)。

6） 占用空間小

缺點(diǎn)有:

1)樹(shù)的節(jié)點(diǎn)整體移動(dòng)操作有點(diǎn)麻煩, 適用于一些只增減，不常移動(dòng)節(jié)點(diǎn)的場(chǎng)合如論壇貼子和評(píng)論等。當(dāng)確實(shí)需要進(jìn)行復(fù)雜的移動(dòng)節(jié)點(diǎn)操作時(shí)，一種方案是在內(nèi)存中進(jìn)行整個(gè)樹(shù)的操作并完成排序，操作完成后刪除整個(gè)舊group再整體將新group一次性批量插入數(shù)據(jù)庫(kù)。

2017年1月22日補(bǔ)充1：

節(jié)點(diǎn)的移動(dòng)操作有點(diǎn)麻煩，只是相對(duì)于查詢/刪除/插入來(lái)說(shuō)，并不是說(shuō)難上天了。例如在MySQL下移動(dòng)整個(gè)B節(jié)點(diǎn)樹(shù)到H節(jié)點(diǎn)下，并位于J和K之間的操作如下：

updatetb2settempno=line*1000000wheregroupid=1;set@nextNodeLine=(selectmin(line)fromtb2wheregroupid=1andline>2andlevel<=2);updatetb2settempno=9*1000000+line,level=level+2wheregroupID=1andline>=2andline<@nextNodeLine;set@mycnt=0;updatetb2setline=(@mycnt:=@mycnt+1)wheregroupid=1orderbytempno;

上例需要在表中新增一個(gè)名為tempno的整數(shù)類型列， 這是個(gè)懶人算法，雖然簡(jiǎn)單明了，但是對(duì)整棵樹(shù)進(jìn)行了重新排序，所以效率并不高。 在需要頻繁移動(dòng)節(jié)點(diǎn)的場(chǎng)合下，用Adjacency List方案可能更合適一些。

2017年1月22日補(bǔ)充2：

如果需要頻繁移動(dòng)節(jié)點(diǎn)的場(chǎng)合，又想保留方案2高效查詢的優(yōu)點(diǎn)，還有一種方案就是再添加一個(gè)父節(jié)點(diǎn)pid字段和兩個(gè)輔助字段tempno和 temporder用于排序，(暫時(shí)稱其為“深度樹(shù)V3.0法"), 這樣相當(dāng)于V2.0法和Adjacency List模式的合并了，優(yōu)點(diǎn)是每次移動(dòng)節(jié)點(diǎn)，只需要更改PID即可，不需要復(fù)雜的算法，一次可以任意移動(dòng)、增加、刪除多個(gè)節(jié)點(diǎn)，最后統(tǒng)一調(diào)用以下算法簡(jiǎn)單 地進(jìn)行一下重排序即可，下面這個(gè)示例完整演示了一個(gè)Adjacency List模式到V2.0模式的轉(zhuǎn)換，這相當(dāng)于一個(gè)重新給樹(shù)建查詢索引的過(guò)程：

createtabletb3(idvarchar(10),commentsvarchar(55),pidvarchar(10),lineinteger,levelinteger,tempnobigint,temporderinteger)insertintotreetest(id,comments,Pid)values('A','found a bug',null);insertintotreetest(id,comments,Pid)values('B','is a worm?','A');insertintotreetest(id,comments,Pid)values('E','no','B');insertintotreetest(id,comments,Pid)values('F','is a bug','B');insertintotreetest(id,comments,Pid)values('C','oh, a bug','A');insertintotreetest(id,comments,Pid)values('G','need solve it','C');insertintotreetest(id,comments,Pid)values('D','careful it bites','A');insertintotreetest(id,comments,Pid)values('H','it does not bite','D');insertintotreetest(id,comments,Pid)values('J','found the reason','H');insertintotreetest(id,comments,Pid)values('K','solved','H');insertintotreetest(id,comments,Pid)values('L','uploaded','H');insertintotreetest(id,comments,Pid)values('I','well done!','D');set@mycnt=0;updatetb3setline=0,level=0, tempno=0, temporder=(@mycnt:=@mycnt+1)orderbyid;updatetb3setlevel=1, line=1wherepidisnull;updatetb3settempno=line*10000000whereline>0;updatetb3 a, tb3 bseta.level=2, a.tempno=b.tempno+a.temporderwherea.level=0anda.pid=b.idandb.level=1;set@mycnt=0;updatetb3setline=(@mycnt:=@mycnt+1)wherelevel>0orderbytempno;updatetb3settempno=line*10000000whereline>0;updatetb3 a, tb3 bseta.level=3, a.tempno=b.tempno+a.temporderwherea.level=0anda.pid=b.idandb.level=2;set@mycnt=0;updatetb3setline=(@mycnt:=@mycnt+1)wherelevel>0orderbytempno;updatetb3settempno=line*10000000whereline>0;updatetb3 a, tb3 bseta.level=4, a.tempno=b.tempno+a.temporderwherea.level=0anda.pid=b.idandb.level=3;set@mycnt=0;updatetb3setline=(@mycnt:=@mycnt+1)wherelevel>0orderbytempno;

以上算法利用了SQL的功能，將原來(lái)可能需要非常多SQL遞歸查詢的過(guò)程轉(zhuǎn)變成了有限次數(shù)(=樹(shù)最大深度)的SQL操作，為了突出算法，以上示例 假設(shè)只有一個(gè)根節(jié)點(diǎn),刪除了groupid和endtag，實(shí)際使用中要完善一下這個(gè)細(xì)節(jié), order by id也可改成以其它字段排序。因時(shí)間關(guān)系我就不給出V2.0模式到Adjacency List模式逆推的算法了（也即pid為空，根據(jù)V2.0表格倒過(guò)來(lái)給pid賦值的過(guò)程），不過(guò)這個(gè)算法倒不重要，因?yàn)橥ǔ3.0表中每一行會(huì)一直保存 著一個(gè)pid)。

總結(jié)一下：

Adjacency List模式:移/增/刪節(jié)點(diǎn)方便，查詢不方便

深度樹(shù)V2.0法:查詢方便，增/刪節(jié)點(diǎn)方便，但存在效率問(wèn)題，移動(dòng)節(jié)點(diǎn)不方便

深度樹(shù)V3.0法:移/增/刪節(jié)點(diǎn)方便，查詢方便，缺點(diǎn)是每次移/增/刪節(jié)點(diǎn)后要重建line和level值以供查詢用。它是結(jié)合了前面兩種模式的合并體，并可以根據(jù)側(cè)重，隨時(shí)在這兩種模式(修改模式和查詢模式)間切換。v3.0法相當(dāng)于給Adjacency List模式設(shè)計(jì)了一個(gè)查詢索引。