在數(shù)據(jù)庫(kù)中存儲(chǔ)一棵樹(shù)，實(shí)現(xiàn)無(wú)限級(jí)分類
在一些系統(tǒng)中，對(duì)內(nèi)容進(jìn)行分類是必需的功能。比如電商就需要對(duì)商品做分類處理，以便于客戶搜索；論壇也會(huì)分為很多板塊；門(mén)戶網(wǎng)站、也得對(duì)網(wǎng)站的內(nèi)容做各種分類。
分類對(duì)于一個(gè)內(nèi)容展示系統(tǒng)來(lái)說(shuō)是不可缺少的，本博客也需要這么一個(gè)功能。眾所周知，分類往往具有從屬關(guān)系，比如鉛筆盒鋼筆屬于筆，筆又是文具的一種，當(dāng)然鋼筆還可以按品牌來(lái)細(xì)分，每個(gè)品牌下面還有各種系列...
這個(gè)例子中從屬關(guān)系具有5層，從上到下依次是：文具-筆-鋼筆-XX牌-A系列，但實(shí)際中分類的層數(shù)卻是無(wú)法估計(jì)的，比如生物中的界門(mén)綱目科屬種有7級(jí)。顯然對(duì)分類的級(jí)數(shù)做限制是不合理的，一個(gè)良好的分類系統(tǒng)，其應(yīng)當(dāng)能實(shí)現(xiàn)***級(jí)分類。
在寫(xiě)自己的博客網(wǎng)站時(shí)，剛好需要這么一個(gè)功能，聽(tīng)起來(lái)很簡(jiǎn)單，但是在實(shí)現(xiàn)時(shí)卻發(fā)現(xiàn)，用關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)***級(jí)分類并非易事。
1.需求分析
首先分析一下分類之間的關(guān)系是怎樣的，很明顯，一個(gè)分類下面有好多個(gè)下級(jí)分類，比如筆下面有鉛筆和鋼筆；那么反過(guò)來(lái)，一個(gè)下級(jí)分類能夠?qū)儆趲讉€(gè)上級(jí)分類呢？這其實(shí)并不確定，取決于如何對(duì)類型的劃分。比如有辦公用品和家具，那么辦公桌可以同時(shí)屬于這兩者，不過(guò)這會(huì)帶來(lái)一些問(wèn)題，比如：我要顯示從***分類到它之間的所有分類，那么這種情況下就很難決定辦公用品和家具顯示哪一個(gè)，并且如果是多對(duì)一，實(shí)現(xiàn)上將更加復(fù)雜，所以這里還是限定每個(gè)分類僅有一個(gè)上級(jí)分類。
現(xiàn)在，分類的關(guān)系可以表述為一父多子的繼承關(guān)系，正好對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)中的樹(shù)，那么問(wèn)題就轉(zhuǎn)化成了如何在數(shù)據(jù)庫(kù)中存儲(chǔ)一棵樹(shù)，并且對(duì)分類所需要的操作有較好的支持。
對(duì)于本博客來(lái)說(shuō)，分類至少需要以下操作：
- 對(duì)單個(gè)分類的增刪改查等基本操作
- 查詢一個(gè)分類的直屬下級(jí)和所有下級(jí)，在現(xiàn)實(shí)某一分類下所有文章時(shí)需要使用
- 查詢出由***分類到文章所在分類之間的所有分類，并且是有序的，用于顯示在博客首頁(yè)文章的簡(jiǎn)介的左下角
- 查詢分類是哪一級(jí)的，比如***分類是1，***分類的直屬下級(jí)是2，再往下依次遞增
- 移動(dòng)一個(gè)分類，換句話說(shuō)就是把一個(gè)子樹(shù)（或者僅單個(gè)節(jié)點(diǎn)）移動(dòng)到另外的節(jié)點(diǎn)下面，這個(gè)在分類結(jié)構(gòu)不合理，需要修改時(shí)使用
- 查詢某一級(jí)的所有分類
在性能的衡量上，這些操作并不是平等的。查詢操作使用的更加頻繁，畢竟分類不會(huì)沒(méi)事就改著玩，性能考慮要以查詢操作優(yōu)先，特別是2和3分別用于搜索文章和在文章簡(jiǎn)介中顯示其分類，所以是重中之重。
另外，每個(gè)分類除了繼承關(guān)系外，還有名字，簡(jiǎn)介等屬性，也需要存儲(chǔ)在數(shù)據(jù)庫(kù)中。每個(gè)分類都有一個(gè)id，由數(shù)據(jù)庫(kù)自動(dòng)生成（自增主鍵）。
***級(jí)多分類多存在于企業(yè)應(yīng)用中，比如電商、博客平臺(tái)等，這些應(yīng)用里一般都有緩存機(jī)制，對(duì)于分類這種不頻繁修改的數(shù)據(jù)，即使在底層數(shù)據(jù)庫(kù)中存在緩慢的操作，只要上層緩存能夠***，一樣有很快的響應(yīng)速度。但是對(duì)于抽象的需求：在關(guān)系數(shù)據(jù)庫(kù)中存儲(chǔ)一棵樹(shù)，并不僅僅存在于有緩存的應(yīng)用中，所以設(shè)計(jì)一個(gè)高效的存儲(chǔ)方案，仍然有其意義。
下面就以這個(gè)賣文具的電商的場(chǎng)景為例，針對(duì)這6條需求，設(shè)計(jì)一個(gè)數(shù)據(jù)庫(kù)存儲(chǔ)方案（對(duì)過(guò)程沒(méi)興趣可以直接轉(zhuǎn)到第4節(jié)）。
2.一些常見(jiàn)設(shè)計(jì)方案的不足
2.1 直接記錄父分類的引用
在許多編程語(yǔ)言中，繼承關(guān)系都是一個(gè)類僅繼承于一個(gè)父類，添加這種繼承關(guān)系僅需要聲明一下父類即可，比如JAVA中extends xxx。根據(jù)這種思想，我們僅需要在每個(gè)分類上添加上直屬上級(jí)的id，即可存儲(chǔ)它們之間的繼承關(guān)系。
表中parent即為直屬上級(jí)分類的id，***分類設(shè)為0。這種方案簡(jiǎn)單易懂，僅存在一張表，并且沒(méi)有冗余字段，存儲(chǔ)空間占用極小，在數(shù)據(jù)庫(kù)層面是一種很好的設(shè)計(jì)。
那么再看看對(duì)操作的支持情況怎么樣，***條單個(gè)增改查都是一句話完事就不多說(shuō)了，刪除的話記得把下級(jí)分類的id全部改成被刪除分類的上級(jí)分類即可，也就多一個(gè)UPDATE。
第二條可就麻煩了，比如我要查文具的下級(jí)分類，預(yù)期結(jié)果是筆、鉛筆、鋼筆三個(gè)，但是并沒(méi)有辦法通過(guò)文具一次性就查到鉛筆盒鋼筆，因?yàn)檫@兩者的關(guān)系間接存儲(chǔ)在筆這個(gè)分類里，需要先查出直屬下級(jí)（筆），才能夠往下查詢，這意味著需要遞歸，性能上一下子就差了很多。
第三條同樣需要遞歸，因?yàn)橥ㄟ^(guò)一個(gè)分類，數(shù)據(jù)庫(kù)中只存儲(chǔ)了其直屬父類，需要通過(guò)遞歸到***分類才能獲取到它們之間的所有分類信息。
綜上所述，最關(guān)鍵的兩個(gè)需求都需要使用性能最差的遞歸方式,這種設(shè)計(jì)肯定是不行的。但還是繼續(xù)看看剩下的幾條吧。
第4個(gè)需求：查詢分類是哪一級(jí)的？這個(gè)還是得需要遞歸或循環(huán)，查出所有上級(jí)分類的數(shù)量即為分類的層級(jí)。
移動(dòng)分類倒是非常簡(jiǎn)單，直接更新父id即可，這也是這種方案的唯一優(yōu)勢(shì)了吧...如果你的分類修改比查詢還多不妨就這么做吧。
***一個(gè)查詢某一級(jí)的所有分類，對(duì)于這個(gè)設(shè)計(jì)簡(jiǎn)直是災(zāi)難，它需要先找出所有一級(jí)分類，然后循環(huán)一遍，找出所有一級(jí)分類的子類就是二級(jí)分類...如此循環(huán)直到所需的級(jí)數(shù)為之。所以這種設(shè)計(jì)里，這個(gè)功能基本是廢了。
這個(gè)方式也是一開(kāi)始就能想到的，在數(shù)據(jù)量不大（層級(jí)不深）的情況下，因?yàn)槠浜?jiǎn)單直觀的特點(diǎn)，不失為一個(gè)好的選擇，不過(guò)對(duì)于本項(xiàng)目來(lái)說(shuō)還不夠（本項(xiàng)目立志成為***博客平臺(tái)?。。。?。
2.2 路徑列表
從2.1節(jié)中可以看出，__之所以速度慢，就是因?yàn)樵诜诸愔袃H僅存儲(chǔ)了直屬上級(jí)的關(guān)系，而需求卻要查詢出非直屬上級(jí)。__針對(duì)這一點(diǎn)，我們的表中不僅僅記錄父節(jié)點(diǎn)id，而是將它到***分類之間所有分類的id都保存下來(lái)。這個(gè)字段所保存的信息就像文件樹(shù)里的路徑一樣，所以就叫做path吧。
如圖所示，每個(gè)分類保存了它所有上級(jí)分類的列表，用逗號(hào)隔開(kāi)，從左往右依次是從***分類到父分類的id。
查詢下級(jí)時(shí)使用Like運(yùn)算符來(lái)查找，比如查出所有筆的下級(jí):
- SELECT id,name FROM pathlist WHERE path LIKE '1,%'
一句話搞定，LIKE的右邊是筆的path字段的值加上模糊匹配，并且左聯(lián)接能夠使用索引，的效率也過(guò)得去。
查詢筆的直屬下級(jí)也同樣可以用LIKE搞定：
- SELECT id,name FROM pathlist WHERE path LIKE '%2'
而找出所有上級(jí)分類這個(gè)需求，直接查出path字段，然后在應(yīng)用層里分割一下即可獲得獲得所有上級(jí)，并且順序也能保證。
查詢某一級(jí)的分類也簡(jiǎn)單，因?yàn)閷蛹?jí)越深，path就越長(zhǎng)，使用LENGTH()函數(shù)作為條件即可篩選出合適的結(jié)果。反過(guò)來(lái)，根據(jù)其長(zhǎng)度也能夠計(jì)算出分類的級(jí)別。
移動(dòng)操作需要遞歸，因?yàn)槊恳粋€(gè)分類的path都是它父類的path加上父類的id,將分類及其所有子分類的path設(shè)為其父類的path并在***追加父類的id即可。
在許多系統(tǒng)中都使用了這種方案，其各方面都具有可以接受的性能，理解起來(lái)也比較容易。但是其有兩點(diǎn)不足：1.就是不遵守?cái)?shù)據(jù)庫(kù)范式，將列表數(shù)據(jù)直接作為字符串來(lái)存儲(chǔ)，這將導(dǎo)致一些操作需要在上層解析path字段的值；2.就是字段長(zhǎng)度是有限的，不能真正達(dá)到***級(jí)深度，并且大字段對(duì)索引不利。如果你不在乎什么范式，分類層級(jí)也遠(yuǎn)達(dá)不到字段長(zhǎng)度的限制，那么這種方案是可行的。
2.3 前序遍歷樹(shù)
這是一種在數(shù)據(jù)庫(kù)里存儲(chǔ)一棵樹(shù)的解決方案。它的思想不是直接存儲(chǔ)父節(jié)點(diǎn)的id，而是以前序遍歷中的順序來(lái)判斷分類直接的關(guān)系。
假設(shè)從根節(jié)點(diǎn)開(kāi)始以前序遍歷的方式依次訪問(wèn)這棵樹(shù)中的節(jié)點(diǎn)，最開(kāi)始的節(jié)點(diǎn)（“Food”）***個(gè)被訪問(wèn)，將它左邊設(shè)為1，然后按照順序到了第二個(gè)階段“Fruit”，給它的左邊寫(xiě)上2，每訪問(wèn)一個(gè)節(jié)點(diǎn)數(shù)字就遞增，訪問(wèn)到葉節(jié)點(diǎn)后返回，在返回的過(guò)程中將訪問(wèn)過(guò)的節(jié)點(diǎn)右邊寫(xiě)也寫(xiě)上數(shù)字。這樣，在遍歷中給每個(gè)節(jié)點(diǎn)的左邊和右邊都寫(xiě)上了數(shù)字。***，我們回到了根節(jié)點(diǎn)“Food”在右邊寫(xiě)上18。下面是標(biāo)上了數(shù)字的樹(shù)，同時(shí)把遍歷的順序用箭頭標(biāo)出來(lái)了。
我們稱這些數(shù)字為左值和右值（如，“Meat”的左值是12，右值是17），這些數(shù)字包含了節(jié)點(diǎn)之間的關(guān)系。因?yàn)?ldquo;Red”有3和6兩個(gè)值，所以，它是有擁有1-18值的“Food”節(jié)點(diǎn)的后續(xù)。同樣的，可以推斷所有左值大于2并且右值小于11的節(jié)點(diǎn)，都是有2-11的“Fruit” 節(jié)點(diǎn)的后續(xù)。這樣，樹(shù)的結(jié)構(gòu)就通過(guò)左值和右值儲(chǔ)存下來(lái)了。
這里就不貼表結(jié)構(gòu)了，這種方式不如前面兩種直觀。效率上，查詢?nèi)肯录?jí)的需求被很好的解決，而直屬下級(jí)也可以通過(guò)添加父節(jié)點(diǎn)id的parent字段來(lái)解決。
因?yàn)樽笾蹈笥抑蹈〉墓?jié)點(diǎn)是下級(jí)節(jié)點(diǎn)，反之左值更小、右值更大的就是上級(jí)，故需求3：查詢兩個(gè)分類直接的所有分類可以通過(guò)左右值作為條件來(lái)解決，同樣是一次查詢即可。
添加新分類和刪除分類需要修改在前序遍歷中所有在指定節(jié)點(diǎn)之后的節(jié)點(diǎn)，甚至包括非父子節(jié)點(diǎn)。而移動(dòng)分類也是如此，這個(gè)特性就非常不友好，在數(shù)據(jù)量大的情況下，改動(dòng)一下可是很要命的。
查詢某一級(jí)的所有分類，和查詢分類是哪一級(jí)的，這兩個(gè)需求無(wú)法解決，只能通過(guò)parent字段想***種方式一樣慢慢遍歷。
綜上所述，對(duì)于本項(xiàng)目而言，它還不如第二種，所以這個(gè)很復(fù)雜的方案也得否決掉。
3.新方案的思考
上面幾種方案最接近理想的就是第二種，如果能解決字段長(zhǎng)度問(wèn)題和不符合范式，以及需要上層參與處理的問(wèn)題就好了。不過(guò)不要急，先看看第二種方案的的優(yōu)缺點(diǎn)的本質(zhì)是什么。
在分析第二種方案的開(kāi)頭就提到，要確保效率，必須要在分類的信息中包含所有上級(jí)分類的信息，而不能僅僅只含有直屬上級(jí)，所以才有了用一個(gè)varchar保存列表的字段。但反過(guò)來(lái)想想，數(shù)據(jù)庫(kù)的表本身不就是用來(lái)保存列表這樣結(jié)構(gòu)化數(shù)據(jù)集合的工具嗎，為何不能做一張關(guān)聯(lián)表來(lái)代替path字段呢？
在路徑列表的設(shè)計(jì)中，關(guān)鍵字段path的本質(zhì)是存儲(chǔ)了兩種信息：一是所有上級(jí)分類的id，二是從***分類到每個(gè)父分類的距離。 所以另增一張表，含有三個(gè)字段：一個(gè)是本分類的所有上級(jí)的id，一個(gè)是本分類的id，再加上該分類到每個(gè)上級(jí)分類的距離。這樣這張表就能夠起到與path字段相同的作用，而且還不違反數(shù)據(jù)庫(kù)范式，最關(guān)鍵的是它不存在字段長(zhǎng)度的限制！
經(jīng)過(guò)一番折騰，終于找到了這個(gè)比較***的方案。事實(shí)上在之后的查閱資料中，發(fā)現(xiàn)這個(gè)方案早就在一些系統(tǒng)中使用了，名叫ClosureTable。
4.基于ClosureTable的***級(jí)分類存儲(chǔ)
ClosureTable直譯過(guò)來(lái)叫閉包表？不過(guò)不重要，ClosureTable以一張表存儲(chǔ)節(jié)點(diǎn)之間的關(guān)系、其中包含了任何兩個(gè)有關(guān)系（上下級(jí)）節(jié)點(diǎn)的關(guān)聯(lián)信息
定義關(guān)系表CategoryTree，其包含3個(gè)字段：
- ancestor 祖先：上級(jí)節(jié)點(diǎn)的id
- descendant 子代：下級(jí)節(jié)點(diǎn)的id
- distance 距離：子代到祖先中間隔了幾級(jí)
這三個(gè)字段的組合是唯一的，因?yàn)樵跇?shù)中，一條路徑可以標(biāo)識(shí)一個(gè)節(jié)點(diǎn)，所以可以直接把它們的組合作為主鍵。以圖為例，節(jié)點(diǎn)6到它上一級(jí)的節(jié)點(diǎn)(節(jié)點(diǎn)4)距離為1在數(shù)據(jù)庫(kù)中存儲(chǔ)為ancestor=4,descendant=6,distance=1，到上兩級(jí)的節(jié)點(diǎn)(節(jié)點(diǎn)1)距離為2,于是有ancestor=1,descendant=6,distance=2，到根節(jié)點(diǎn)的距離為3也是如此，***還要包含一個(gè)到自己的連接，當(dāng)然距離就是0了。
這樣一來(lái)，不盡表中包含了所有的路徑信息，還在帶上了路徑中每個(gè)節(jié)點(diǎn)的位置（距離），對(duì)于樹(shù)結(jié)構(gòu)常用的查詢都能夠很方便的處理。下面看看如何用用它來(lái)實(shí)現(xiàn)我們的需求。
4.1 子節(jié)點(diǎn)查詢
查詢id為5的節(jié)點(diǎn)的直屬子節(jié)點(diǎn)：
- SELECT descendant FROM CategoryTree WHERE ancestor=5 AND distance=1
查詢所有子節(jié)點(diǎn)：
- SELECT descendant FROM CategoryTree WHERE ancestor=5 AND distance>0
查詢某個(gè)上級(jí)節(jié)點(diǎn)的子節(jié)點(diǎn)，換句話說(shuō)就是查詢具有指定上級(jí)節(jié)點(diǎn)的節(jié)點(diǎn)，也就是ancestor字段等于上級(jí)節(jié)點(diǎn)id即可，第二個(gè)距離distance決定了查詢的對(duì)象是由上級(jí)往下那一層的，等于1就是往下一層（直屬子節(jié)點(diǎn)），大于0就是所有子節(jié)點(diǎn)。這兩個(gè)查詢都是一句完成。
4.2 路徑查詢
查詢由根節(jié)點(diǎn)到id為10的節(jié)點(diǎn)之間的所有節(jié)點(diǎn)，按照層級(jí)由小到大排序
- SELECT ancestor FROM CategoryTree WHERE descendant=10 ORDER BY distance DESC
查詢id為10的節(jié)點(diǎn)（含）到id為3的節(jié)點(diǎn)（不含）之間的所有節(jié)點(diǎn)，按照層級(jí)由小到大排序
- SELECT ancestor FROM CategoryTree WHERE descendant=10 AND
- distance<(SELECT distance FROM CategoryTree WHERE descendant=10 AND ancestor=3)
- ORDER BY distance DESC
查詢路徑，只需要知道descendant即可，因?yàn)閐escendant字段所在的行就是記錄這個(gè)節(jié)點(diǎn)與其上級(jí)節(jié)點(diǎn)的關(guān)系。如果要過(guò)濾掉一些則可以限制distance的值。
4.3 查詢節(jié)點(diǎn)所在的層級(jí)（深度）
查詢id為5的節(jié)點(diǎn)是第幾級(jí)的
- SELECT distance FROM CategoryTree WHERE descendant=5 AND ancestor=0
查詢id為5的節(jié)點(diǎn)是id為10的節(jié)點(diǎn)往下第幾級(jí)
- SELECT distance FROM CategoryTree WHERE descendant=5 AND ancestor=10
查詢層級(jí)（深度）非常簡(jiǎn)單，因?yàn)閐istance字段就是。直接以上下級(jí)的節(jié)點(diǎn)id為條件，查詢距離即可。
4.4 查詢某一層的所有節(jié)點(diǎn)
查詢所有第三層的節(jié)點(diǎn)
- SELECT descendant FROM CategoryTree WHERE ancestor=0 AND distance=3
這個(gè)就不詳細(xì)說(shuō)了，非常簡(jiǎn)單。
4.5 插入
插入和移動(dòng)就不是那么方便了，當(dāng)一個(gè)節(jié)點(diǎn)插入到某個(gè)父節(jié)點(diǎn)下方時(shí)，它將具有與父節(jié)點(diǎn)相似的路徑，然后再加上一個(gè)自身連接即可。
所以插入操作需要兩條語(yǔ)句，***條復(fù)制父節(jié)點(diǎn)的所有記錄，并把這些記錄的distance加一，因?yàn)樽庸?jié)點(diǎn)到每個(gè)上級(jí)節(jié)點(diǎn)的距離都比它的父節(jié)點(diǎn)多一。當(dāng)然descendant也要改成自己的。
例如把id為10的節(jié)點(diǎn)插入到id為5的節(jié)點(diǎn)下方（這里用了Mysql的方言）
- INSERT INTO CategoryTree(ancestor,descendant,distance) (SELECT ancestor,10,distance+1 FROM CategoryTree WHERE descendant=5)
然后就是加入自身連接的記錄。
- INSERT INTO CategoryTree(ancestor,descendant,distance) VALUES(10,10,0)
4.6 移動(dòng)
節(jié)點(diǎn)的移動(dòng)沒(méi)有很好的解決方法，因?yàn)樾挛恢盟诘纳疃取⒙窂蕉伎赡懿灰粯?，這就導(dǎo)致移動(dòng)操作不是僅靠UPDATE語(yǔ)句能完成的，這里選擇刪除+插入實(shí)現(xiàn)移動(dòng)。
另外，在有子樹(shù)的情況下，上級(jí)節(jié)點(diǎn)的移動(dòng)還將導(dǎo)致下級(jí)節(jié)點(diǎn)的路徑改變，所以移動(dòng)上級(jí)節(jié)點(diǎn)之后還需要修復(fù)下級(jí)節(jié)點(diǎn)的記錄，這就需要遞歸所有下級(jí)節(jié)點(diǎn)。
刪除id=5節(jié)點(diǎn)的所有記錄
- DELETE FROM CategoryTree WHERE descendant=5
然后配合上面一節(jié)的插入操作實(shí)現(xiàn)移動(dòng)。具體的實(shí)現(xiàn)直接上代碼吧。
ClosureTableCategoryStore.java是主要的邏輯，這里只展示部分代碼
- /**
- * 將一個(gè)分類移動(dòng)到目標(biāo)分類下面（成為其子分類）。被移動(dòng)分類的子類將自動(dòng)上浮（成為指定分類
- * 父類的子分類），即使目標(biāo)是指定分類原本的父類。
- * <p>
- * 例如下圖(省略***分類)：
- * 1 1
- * | / | \
- * 2 3 4 5
- * / | \ move(2,7) / \
- * 3 4 5 ---------------> 6 7
- * / \ / / | \
- * 6 7 8 9 10 2
- * / / \
- * 8 9 10
- *
- * @param id 被移動(dòng)分類的id
- * @param target 目標(biāo)分類的id
- * @throws IllegalArgumentException 如果id或target所表示的分類不存在、或id==target
- */
- public void move(int id, int target) {
- if(id == target) {
- throw new IllegalArgumentException("不能移動(dòng)到自己下面");
- }
- moveSubTree(id, categoryMapper.selectAncestor(id, 1));
- moveNode(id, target);
- }
- /**
- * 將一個(gè)分類移動(dòng)到目標(biāo)分類下面（成為其子分類），被移動(dòng)分類的子分類也會(huì)隨著移動(dòng)。
- * 如果目標(biāo)分類是被移動(dòng)分類的子類，則先將目標(biāo)分類（連帶子類）移動(dòng)到被移動(dòng)分類原來(lái)的
- * 的位置，再移動(dòng)需要被移動(dòng)的分類。
- * <p>
- * 例如下圖(省略***分類)：
- * 1 1
- * | |
- * 2 7
- * / | \ moveTree(2,7) / | \
- * 3 4 5 ---------------> 9 10 2
- * / \ / | \
- * 6 7 3 4 5
- * / / \ |
- * 8 9 10 6
- * |
- * 8
- *
- * @param id 被移動(dòng)分類的id
- * @param target 目標(biāo)分類的id
- * @throws IllegalArgumentException 如果id或target所表示的分類不存在、或id==target
- */
- public void moveTree(int id, int target) {
- /* 移動(dòng)分移到自己子樹(shù)下和無(wú)關(guān)節(jié)點(diǎn)下兩種情況 */
- Integer distance = categoryMapper.selectDistance(id, target);
- if (distance == null) {
- // 移動(dòng)到父節(jié)點(diǎn)或其他無(wú)關(guān)系節(jié)點(diǎn)，不需要做額外動(dòng)作
- } else if (distance == 0) {
- throw new IllegalArgumentException("不能移動(dòng)到自己下面");
- } else {
- // 如果移動(dòng)的目標(biāo)是其子類，需要先把子類移動(dòng)到本類的位置
- int parent = categoryMapper.selectAncestor(id, 1);
- moveNode(target, parent);
- moveSubTree(target, target);
- }
- moveNode(id, target);
- moveSubTree(id, id);
- }
- /**
- * 將指定節(jié)點(diǎn)移動(dòng)到另某節(jié)點(diǎn)下面，該方法不修改子節(jié)點(diǎn)的相關(guān)記錄，
- * 為了保證數(shù)據(jù)的完整性，需要與moveSubTree()方法配合使用。
- *
- * @param id 指定節(jié)點(diǎn)id
- * @param parent 某節(jié)點(diǎn)id
- */
- private void moveNode(int id, int parent) {
- categoryMapper.deletePath(id);
- categoryMapper.insertPath(id, parent);
- categoryMapper.insertNode(id);
- }
- /**
- * 將指定節(jié)點(diǎn)的所有子樹(shù)移動(dòng)到某節(jié)點(diǎn)下
- * 如果兩個(gè)參數(shù)相同，則相當(dāng)于重建子樹(shù)，用于父節(jié)點(diǎn)移動(dòng)后更新路徑
- *
- * @param id 指定節(jié)點(diǎn)id
- * @param parent 某節(jié)點(diǎn)id
- */
- private void moveSubTree(int id, int parent) {
- int[] subs = categoryMapper.selectSubId(id);
- for (int sub : subs) {
- moveNode(sub, parent);
- moveSubTree(sub, sub);
- }
- }
其中的categoryMapper 是Mybatis的Mapper，這里只展示部分代碼
- /**
- * 查詢某個(gè)節(jié)點(diǎn)的第N級(jí)父節(jié)點(diǎn)。如果id指定的節(jié)點(diǎn)不存在、操作錯(cuò)誤或是數(shù)據(jù)庫(kù)被外部修改，
- * 則可能查詢不到父節(jié)點(diǎn)，此時(shí)返回null。
- *
- * @param id 節(jié)點(diǎn)id
- * @param n 祖先距離（0表示自己，1表示直屬父節(jié)點(diǎn)）
- * @return 父節(jié)點(diǎn)id，如果不存在則返回null
- */
- @Select("SELECT ancestor FROM CategoryTree WHERE descendant=#{id} AND distance=#{n}")
- Integer selectAncestor(@Param("id") int id, @Param("n") int n);
- /**
- * 復(fù)制父節(jié)點(diǎn)的路徑結(jié)構(gòu),并修改descendant和distance
- *
- * @param id 節(jié)點(diǎn)id
- * @param parent 父節(jié)點(diǎn)id
- */
- @Insert("INSERT INTO CategoryTree(ancestor,descendant,distance) " +
- "(SELECT ancestor,#{id},distance+1 FROM CategoryTree WHERE descendant=#{parent})")
- void insertPath(@Param("id") int id, @Param("parent") int parent);
- /**
- * 在關(guān)系表中插入對(duì)自身的連接
- *
- * @param id 節(jié)點(diǎn)id
- */
- @Insert("INSERT INTO CategoryTree(ancestor,descendant,distance) VALUES(#{id},#{id},0)")
- void insertNode(int id);
- /**
- * 從樹(shù)中刪除某節(jié)點(diǎn)的路徑。注意指定的節(jié)點(diǎn)可能存在子樹(shù)，而子樹(shù)的節(jié)點(diǎn)在該節(jié)點(diǎn)之上的路徑并沒(méi)有改變，
- * 所以使用該方法后還必須手動(dòng)修改子節(jié)點(diǎn)的路徑以確保樹(shù)的正確性
- *
- * @param id 節(jié)點(diǎn)id
- */
- @Delete("DELETE FROM CategoryTree WHERE descendant=#{id}")
- void deletePath(int id);
5.結(jié)語(yǔ)
在分析推論后，終于找到了一種既有查詢簡(jiǎn)單、效率高等優(yōu)點(diǎn)，也符合數(shù)據(jù)庫(kù)設(shè)計(jì)范式，而且是真正的***級(jí)分類的設(shè)計(jì)。本方案的寫(xiě)入操作雖然需要遞歸，但相比于前序遍歷樹(shù)效率仍高出許多，并且在本博客系統(tǒng)中分類不會(huì)頻繁修改?？梢?jiàn)對(duì)于在關(guān)系數(shù)據(jù)庫(kù)中存儲(chǔ)一棵樹(shù)的需求，ClosureTable是一種比較***的解決方案。
完整的JAVA實(shí)現(xiàn)代碼見(jiàn) https://github.com/Kaciras/Examples-java/tree/master/ClosureTable
