分類樹這種結(jié)構(gòu)存在于頁面菜單、行政區(qū)劃、部門層級(jí)、用戶組等場景中，特點(diǎn)是有明確的上下級(jí)覆蓋關(guān)系，本質(zhì)數(shù)據(jù)結(jié)構(gòu)是N叉樹。

一、基礎(chǔ)實(shí)現(xiàn)

分類樹的基礎(chǔ)實(shí)現(xiàn)是遞歸查詢。在數(shù)據(jù)表中增加一個(gè)pid字段，儲(chǔ)存當(dāng)前記錄的上級(jí)id。通過遞歸查詢pid的方法將子節(jié)點(diǎn)集合從數(shù)據(jù)表中查出來放入children列表中，通過這種方式建成一棵樹。

二、優(yōu)化基礎(chǔ)實(shí)現(xiàn)

遞歸查詢建立分類樹的方式有查詢擴(kuò)散問題，就是不知道遞歸深度有多少，數(shù)據(jù)庫交互次數(shù)無法控制。針對(duì)這個(gè)問題，后來又出現(xiàn)了添加樹深度字段deep、添加樹路徑字段path等方法，通過冗余字段來降低分類樹的使用難度。

但是冗余字段造成一個(gè)問題——修改擴(kuò)散。例如當(dāng)分類樹中的一條記錄被修改，其深度發(fā)生變化時(shí)，那么它的子節(jié)點(diǎn)深度也會(huì)發(fā)生變化，它子節(jié)點(diǎn)的子節(jié)點(diǎn)深度亦發(fā)生變化，路徑字段也是同理。一個(gè)修改導(dǎo)致多個(gè)修改，進(jìn)而導(dǎo)致更多修改，其最終修改范圍無法控制，可能遍布全表，這就是修改擴(kuò)散。

三、非遞歸實(shí)現(xiàn)

遞歸查詢會(huì)發(fā)生查詢擴(kuò)散、修改擴(kuò)散。我意在構(gòu)想一種算法，構(gòu)建樹的查詢次數(shù)與樹深度無關(guān)，修改擴(kuò)散范圍可控，不會(huì)無限波及。

遞歸的層數(shù)是無法預(yù)知的，所以我放棄用遞歸實(shí)現(xiàn)。

首先，我構(gòu)造這樣的一個(gè)表，除節(jié)點(diǎn)本身信息之外，其結(jié)構(gòu)信息有主鍵id、子節(jié)點(diǎn)主鍵集合children、祖先節(jié)點(diǎn)主鍵集合ancestors。子節(jié)點(diǎn)主鍵集合children我采用Set避免重復(fù)。

在這里，我劃分分類樹為兩類，一類是葉子只有唯一父節(jié)點(diǎn)的singleTree，一類是子節(jié)點(diǎn)允許多個(gè)父節(jié)點(diǎn)的crossTree。singleTree的祖先節(jié)點(diǎn)主鍵集合ancestors我采用List，以便記錄其順序，此時(shí)ancestors可以當(dāng)作路徑path用。crossTree的祖先節(jié)點(diǎn)主鍵集合ancestors我采用Set，因其多父節(jié)點(diǎn)有可能會(huì)有同一源頭，采用Set去重。crossTree的優(yōu)勢在于，相同節(jié)點(diǎn)不必重復(fù)創(chuàng)建，可以復(fù)用節(jié)點(diǎn)，例如指向同一個(gè)頁面的菜單項(xiàng)可以同時(shí)掛在不同的父菜單下，該菜單項(xiàng)地址修改時(shí)只需修改該項(xiàng)，不必像singleTree同名菜單項(xiàng)全部去改一遍。除此之外兩類分類樹使用是非常相似的。

children、ancestors兩個(gè)字段，在數(shù)據(jù)庫中用表示數(shù)組的字符串存儲(chǔ)，其格式形如：[]或["id1","id2"]。

現(xiàn)在，我詳細(xì)解釋如何解決上面提到的查詢擴(kuò)散、修改擴(kuò)散問題。

1、查詢擴(kuò)散

查詢之所以會(huì)擴(kuò)散，是因?yàn)闊o法穿透查詢隔代節(jié)點(diǎn)。

但是現(xiàn)在向下查詢各節(jié)點(diǎn)都有ancestors字段記錄全部祖先，通過ancestors like '%"rootId"%'就可以一次性查到所有子孫節(jié)點(diǎn)的列表，不論子孫節(jié)點(diǎn)跟查詢節(jié)點(diǎn)隔了幾代。

向上查詢的話，查詢節(jié)點(diǎn)的ancestors字段本身就記載了所有關(guān)聯(lián)的祖先，不會(huì)擴(kuò)散到此范圍之外。

2、修改擴(kuò)散

將一個(gè)新節(jié)點(diǎn)node插入樹中時(shí)，首先取得插入點(diǎn)的父節(jié)點(diǎn)parent。新節(jié)點(diǎn)的ancestors字段，就是parent.ancestors以及parent.id，這是singleTree的情況。如果是crossTree且node.ancestors原來就有內(nèi)容，即還掛在別的父節(jié)點(diǎn)下，那除了parent.ancestors和parent.id之外，還要再加上node.ancestors原有內(nèi)容，其是Set會(huì)自動(dòng)去重。接著在parent.children集合中添加node自身id。

接著，根據(jù)node.children取得所有直接子節(jié)點(diǎn)，以及直接子節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)。這次查詢的結(jié)果列表就是所有ancestors字段需要修改的范圍。在所有子孫節(jié)點(diǎn)的祖先主鍵集合ancestors中，添加node.ancestors以及node.id。

修改、刪除節(jié)點(diǎn)也是同理。

綜上，修改一個(gè)節(jié)點(diǎn)，所要關(guān)聯(lián)修改的所有其他記錄為其父節(jié)點(diǎn)、滿足ancestors like '%"nodeId"%'的節(jié)點(diǎn)，不會(huì)擴(kuò)散到此范圍之外。

四、優(yōu)化非遞歸實(shí)現(xiàn)

以上實(shí)現(xiàn)因?yàn)槭褂昧薼ike條件，在表規(guī)模較小時(shí)尚無問題，規(guī)模大了就有可能出現(xiàn)查詢性能問題，因?yàn)閘ike條件中的id不確定位于字符串何處，無法使用索引。

既然如此，當(dāng)表規(guī)模膨脹了，可以將children字段和ancestors字段改為兩個(gè)新表記錄這兩種關(guān)聯(lián)關(guān)系，對(duì)childrenId和ancestorsId建立索引。這種改造對(duì)非樹形表也同樣可行，不需要修改原表結(jié)構(gòu)。