摘要：第三條同樣需要遞歸，因?yàn)橥ㄟ^(guò)一個(gè)分類，數(shù)據(jù)庫(kù)中只存儲(chǔ)了其直屬父類，需要通過(guò)遞歸到頂級(jí)分類才能獲取到它們之間的所有分類信息。

原文發(fā)表于我的博客： https://blog.kaciras.net/article/36

在一些系統(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)無(wú)限級(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ǔ)無(wú)限級(jí)分類并非易事。

首先分析一下分類之間的關(guān)系是怎樣的，很明顯，一個(gè)分類下面有好多個(gè)下級(jí)分類，比如筆下面有鉛筆和鋼筆；那么反過(guò)來(lái)，一個(gè)下級(jí)分類能夠?qū)儆趲讉€(gè)上級(jí)分類呢？這其實(shí)并不確定，取決于如何對(duì)類型的劃分。比如有辦公用品和家具，那么辦公桌可以同時(shí)屬于這兩者，不過(guò)這會(huì)帶來(lái)一些問(wèn)題，比如：我要顯示從頂級(jí)分類到它之間的所有分類，那么這種情況下就很難決定辦公用品和家具顯示哪一個(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í)需要使用

查詢出由頂級(jí)分類到文章所在分類之間的所有分類，并且是有序的，用于顯示在博客首頁(yè)文章的簡(jiǎn)介的左下角

查詢分類是哪一級(jí)的，比如頂級(jí)分類是1，頂級(jí)分類的直屬下級(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)生成（自增主鍵）。

無(wú)限級(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è)賣(mài)文具的電商的場(chǎng)景為例，針對(duì)這6條需求，設(shè)計(jì)一個(gè)數(shù)據(jù)庫(kù)存儲(chǔ)方案（對(duì)過(guò)程沒(méi)興趣可以直接轉(zhuǎn)到第4節(jié)）。

在許多編程語(yǔ)言中，繼承關(guān)系都是一個(gè)類僅繼承于一個(gè)父類，添加這種繼承關(guān)系僅需要聲明一下父類即可，比如JAVA中extends xxx。根據(jù)這種思想，我們僅需要在每個(gè)分類上添加上直屬上級(jí)的id，即可存儲(chǔ)它們之間的繼承關(guān)系。

表中parent即為直屬上級(jí)分類的id，頂級(jí)分類設(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ò)遞歸到頂級(jí)分類才能獲取到它們之間的所有分類信息。

綜上所述，最關(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.1節(jié)中可以看出，__之所以速度慢，就是因?yàn)樵诜诸愔袃H僅存儲(chǔ)了直屬上級(jí)的關(guān)系，而需求卻要查詢出非直屬上級(jí)。__針對(duì)這一點(diǎn)，我們的表中不僅僅記錄父節(jié)點(diǎn)id，而是將它到頂級(jí)分類之間所有分類的id都保存下來(lái)。這個(gè)字段所保存的信息就像文件樹(shù)里的路徑一樣，所以就叫做path吧。

如圖所示，每個(gè)分類保存了它所有上級(jí)分類的列表，用逗號(hào)隔開(kāi)，從左往右依次是從頂級(jí)分類到父分類的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á)到無(wú)限級(jí)深度，并且大字段對(duì)索引不利。如果你不在乎什么范式，分類層級(jí)也遠(yuǎn)達(dá)不到字段長(zhǎng)度的限制，那么這種方案是可行的。

這是一種在數(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)椤癛ed”有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ù)雜的方案也得否決掉。

上面幾種方案最接近理想的就是第二種，如果能解決字段長(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，二是從頂級(jí)分類到每個(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。

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)我們的需求。

查詢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è)查詢都是一句完成。

查詢由根節(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)?b>descendant字段所在的行就是記錄這個(gè)節(jié)點(diǎn)與其上級(jí)節(jié)點(diǎn)的關(guān)系。如果要過(guò)濾掉一些則可以限制distance的值。

查詢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)?b>distance字段就是。直接以上下級(jí)的節(jié)點(diǎn)id為條件，查詢距離即可。

查詢所有第三層的節(jié)點(diǎn)

SELECT descendant FROM CategoryTree WHERE ancestor=0 AND distance=3

這個(gè)就不詳細(xì)說(shuō)了，非常簡(jiǎn)單。

插入和移動(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)

節(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)是指定分類原本的父類。
     * 

     * 例如下圖(省略頂級(jí)分類)：
     *       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)的分類。
     * 

     * 例如下圖(省略頂級(jí)分類)：
     *       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);

在分析推論后，終于找到了一種既有查詢簡(jiǎn)單、效率高等優(yōu)點(diǎn)，也符合數(shù)據(jù)庫(kù)設(shè)計(jì)范式，而且是真正的無(wú)限級(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/ClosureTableCateogryStore