摘要：第三條同樣需要遞歸，因為通過一個分類，數(shù)據(jù)庫中只存儲了其直屬父類，需要通過遞歸到頂級分類才能獲取到它們之間的所有分類信息。

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

在一些系統(tǒng)中，對內(nèi)容進行分類是必需的功能。比如電商就需要對商品做分類處理，以便于客戶搜索；論壇也會分為很多板塊；門戶網(wǎng)站、也得對網(wǎng)站的內(nèi)容做各種分類。

分類對于一個內(nèi)容展示系統(tǒng)來說是不可缺少的，本博客也需要這么一個功能。眾所周知，分類往往具有從屬關(guān)系，比如鉛筆盒鋼筆屬于筆，筆又是文具的一種，當然鋼筆還可以按品牌來細分，每個品牌下面還有各種系列...

這個例子中從屬關(guān)系具有5層，從上到下依次是：文具-筆-鋼筆-XX牌-A系列，但實際中分類的層數(shù)卻是無法估計的，比如生物中的界門綱目科屬種有7級。顯然對分類的級數(shù)做限制是不合理的，一個良好的分類系統(tǒng)，其應當能實現(xiàn)無限級分類。

在寫自己的博客網(wǎng)站時，剛好需要這么一個功能，聽起來很簡單，但是在實現(xiàn)時卻發(fā)現(xiàn)，用關(guān)系數(shù)據(jù)庫存儲無限級分類并非易事。

首先分析一下分類之間的關(guān)系是怎樣的，很明顯，一個分類下面有好多個下級分類，比如筆下面有鉛筆和鋼筆；那么反過來，一個下級分類能夠?qū)儆趲讉€上級分類呢？這其實并不確定，取決于如何對類型的劃分。比如有辦公用品和家具，那么辦公桌可以同時屬于這兩者，不過這會帶來一些問題，比如：我要顯示從頂級分類到它之間的所有分類，那么這種情況下就很難決定辦公用品和家具顯示哪一個，并且如果是多對一，實現(xiàn)上將更加復雜，所以這里還是限定每個分類僅有一個上級分類。

現(xiàn)在，分類的關(guān)系可以表述為一父多子的繼承關(guān)系，正好對應數(shù)據(jù)結(jié)構(gòu)中的樹，那么問題就轉(zhuǎn)化成了如何在數(shù)據(jù)庫中存儲一棵樹，并且對分類所需要的操作有較好的支持。

對于本博客來說，分類至少需要以下操作：

對單個分類的增刪改查等基本操作

查詢一個分類的直屬下級和所有下級，在現(xiàn)實某一分類下所有文章時需要使用

查詢出由頂級分類到文章所在分類之間的所有分類，并且是有序的，用于顯示在博客首頁文章的簡介的左下角

查詢分類是哪一級的，比如頂級分類是1，頂級分類的直屬下級是2，再往下依次遞增

移動一個分類，換句話說就是把一個子樹（或者僅單個節(jié)點）移動到另外的節(jié)點下面，這個在分類結(jié)構(gòu)不合理，需要修改時使用

查詢某一級的所有分類

在性能的衡量上，這些操作并不是平等的。查詢操作使用的更加頻繁，畢竟分類不會沒事就改著玩，性能考慮要以查詢操作優(yōu)先，特別是2和3分別用于搜索文章和在文章簡介中顯示其分類，所以是重中之重。

另外，每個分類除了繼承關(guān)系外，還有名字，簡介等屬性，也需要存儲在數(shù)據(jù)庫中。每個分類都有一個id，由數(shù)據(jù)庫自動生成（自增主鍵）。

無限級多分類多存在于企業(yè)應用中，比如電商、博客平臺等，這些應用里一般都有緩存機制，對于分類這種不頻繁修改的數(shù)據(jù)，即使在底層數(shù)據(jù)庫中存在緩慢的操作，只要上層緩存能夠命中，一樣有很快的響應速度。但是對于抽象的需求：在關(guān)系數(shù)據(jù)庫中存儲一棵樹，并不僅僅存在于有緩存的應用中，所以設(shè)計一個高效的存儲方案，仍然有其意義。

下面就以這個賣文具的電商的場景為例，針對這6條需求，設(shè)計一個數(shù)據(jù)庫存儲方案（對過程沒興趣可以直接轉(zhuǎn)到第4節(jié)）。

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

表中parent即為直屬上級分類的id，頂級分類設(shè)為0。這種方案簡單易懂，僅存在一張表，并且沒有冗余字段，存儲空間占用極小，在數(shù)據(jù)庫層面是一種很好的設(shè)計。

那么再看看對操作的支持情況怎么樣，第一條單個增改查都是一句話完事就不多說了，刪除的話記得把下級分類的id全部改成被刪除分類的上級分類即可，也就多一個UPDATE。

第二條可就麻煩了，比如我要查文具的下級分類，預期結(jié)果是筆、鉛筆、鋼筆三個，但是并沒有辦法通過文具一次性就查到鉛筆盒鋼筆，因為這兩者的關(guān)系間接存儲在筆這個分類里，需要先查出直屬下級（筆），才能夠往下查詢，這意味著需要遞歸，性能上一下子就差了很多。

第三條同樣需要遞歸，因為通過一個分類，數(shù)據(jù)庫中只存儲了其直屬父類，需要通過遞歸到頂級分類才能獲取到它們之間的所有分類信息。

綜上所述，最關(guān)鍵的兩個需求都需要使用性能最差的遞歸方式,這種設(shè)計肯定是不行的。但還是繼續(xù)看看剩下的幾條吧。

第4個需求：查詢分類是哪一級的？這個還是得需要遞歸或循環(huán)，查出所有上級分類的數(shù)量即為分類的層級。

移動分類倒是非常簡單，直接更新父id即可，這也是這種方案的唯一優(yōu)勢了吧...如果你的分類修改比查詢還多不妨就這么做吧。

最后一個查詢某一級的所有分類，對于這個設(shè)計簡直是災難，它需要先找出所有一級分類，然后循環(huán)一遍，找出所有一級分類的子類就是二級分類...如此循環(huán)直到所需的級數(shù)為之。所以這種設(shè)計里，這個功能基本是廢了。

這個方式也是一開始就能想到的，在數(shù)據(jù)量不大（層級不深）的情況下，因為其簡單直觀的特點，不失為一個好的選擇，不過對于本項目來說還不夠（本項目立志成為一流博客平臺！！！）。

從2.1節(jié)中可以看出，__之所以速度慢，就是因為在分類中僅僅存儲了直屬上級的關(guān)系，而需求卻要查詢出非直屬上級。__針對這一點，我們的表中不僅僅記錄父節(jié)點id，而是將它到頂級分類之間所有分類的id都保存下來。這個字段所保存的信息就像文件樹里的路徑一樣，所以就叫做path吧。

如圖所示，每個分類保存了它所有上級分類的列表，用逗號隔開，從左往右依次是從頂級分類到父分類的id。

查詢下級時使用Like運算符來查找，比如查出所有筆的下級:

SELECT id,name FROM pathlist WHERE path LIKE "1,%"

一句話搞定，LIKE的右邊是筆的path字段的值加上模糊匹配，并且左聯(lián)接能夠使用索引，的效率也過得去。

查詢筆的直屬下級也同樣可以用LIKE搞定：

SELECT id,name FROM pathlist WHERE path LIKE "%2"

而找出所有上級分類這個需求，直接查出path字段，然后在應用層里分割一下即可獲得獲得所有上級，并且順序也能保證。

查詢某一級的分類也簡單，因為層級越深，path就越長，使用LENGTH()函數(shù)作為條件即可篩選出合適的結(jié)果。反過來，根據(jù)其長度也能夠計算出分類的級別。

移動操作需要遞歸，因為每一個分類的path都是它父類的path加上父類的id,將分類及其所有子分類的path設(shè)為其父類的path并在最后追加父類的id即可。

在許多系統(tǒng)中都使用了這種方案，其各方面都具有可以接受的性能，理解起來也比較容易。但是其有兩點不足：1.就是不遵守數(shù)據(jù)庫范式，將列表數(shù)據(jù)直接作為字符串來存儲，這將導致一些操作需要在上層解析path字段的值；2.就是字段長度是有限的，不能真正達到無限級深度，并且大字段對索引不利。如果你不在乎什么范式，分類層級也遠達不到字段長度的限制，那么這種方案是可行的。

這是一種在數(shù)據(jù)庫里存儲一棵樹的解決方案。它的思想不是直接存儲父節(jié)點的id，而是以前序遍歷中的順序來判斷分類直接的關(guān)系。

假設(shè)從根節(jié)點開始以前序遍歷的方式依次訪問這棵樹中的節(jié)點，最開始的節(jié)點（“Food”）第一個被訪問，將它左邊設(shè)為1，然后按照順序到了第二個階段“Fruit”，給它的左邊寫上2，每訪問一個節(jié)點數(shù)字就遞增，訪問到葉節(jié)點后返回，在返回的過程中將訪問過的節(jié)點右邊寫也寫上數(shù)字。這樣，在遍歷中給每個節(jié)點的左邊和右邊都寫上了數(shù)字。最后，我們回到了根節(jié)點“Food”在右邊寫上18。下面是標上了數(shù)字的樹，同時把遍歷的順序用箭頭標出來了。

我們稱這些數(shù)字為左值和右值（如，“Meat”的左值是12，右值是17），這些數(shù)字包含了節(jié)點之間的關(guān)系。因為“Red”有3和6兩個值，所以，它是有擁有1-18值的“Food”節(jié)點的后續(xù)。同樣的，可以推斷所有左值大于2并且右值小于11的節(jié)點，都是有2-11的“Fruit” 節(jié)點的后續(xù)。這樣，樹的結(jié)構(gòu)就通過左值和右值儲存下來了。

這里就不貼表結(jié)構(gòu)了，這種方式不如前面兩種直觀。效率上，查詢?nèi)肯录壍男枨蟊缓芎玫慕鉀Q，而直屬下級也可以通過添加父節(jié)點id的parent字段來解決。

因為左值更大右值更小的節(jié)點是下級節(jié)點，反之左值更小、右值更大的就是上級，故需求3：查詢兩個分類直接的所有分類可以通過左右值作為條件來解決，同樣是一次查詢即可。

添加新分類和刪除分類需要修改在前序遍歷中所有在指定節(jié)點之后的節(jié)點，甚至包括非父子節(jié)點。而移動分類也是如此，這個特性就非常不友好，在數(shù)據(jù)量大的情況下，改動一下可是很要命的。

查詢某一級的所有分類，和查詢分類是哪一級的，這兩個需求無法解決，只能通過parent字段想第一種方式一樣慢慢遍歷。

綜上所述，對于本項目而言，它還不如第二種，所以這個很復雜的方案也得否決掉。

上面幾種方案最接近理想的就是第二種，如果能解決字段長度問題和不符合范式，以及需要上層參與處理的問題就好了。不過不要急，先看看第二種方案的的優(yōu)缺點的本質(zhì)是什么。

在分析第二種方案的開頭就提到，要確保效率，必須要在分類的信息中包含所有上級分類的信息，而不能僅僅只含有直屬上級，所以才有了用一個varchar保存列表的字段。但反過來想想，數(shù)據(jù)庫的表本身不就是用來保存列表這樣結(jié)構(gòu)化數(shù)據(jù)集合的工具嗎，為何不能做一張關(guān)聯(lián)表來代替path字段呢？

在路徑列表的設(shè)計中，關(guān)鍵字段path的本質(zhì)是存儲了兩種信息：一是所有上級分類的id，二是從頂級分類到每個父分類的距離。 所以另增一張表，含有三個字段：一個是本分類的所有上級的id，一個是本分類的id，再加上該分類到每個上級分類的距離。這樣這張表就能夠起到與path字段相同的作用，而且還不違反數(shù)據(jù)庫范式，最關(guān)鍵的是它不存在字段長度的限制！

經(jīng)過一番折騰，終于找到了這個比較完美的方案。事實上在之后的查閱資料中，發(fā)現(xiàn)這個方案早就在一些系統(tǒng)中使用了，名叫ClosureTable。

ClosureTable直譯過來叫閉包表？不過不重要，ClosureTable以一張表存儲節(jié)點之間的關(guān)系、其中包含了任何兩個有關(guān)系（上下級）節(jié)點的關(guān)聯(lián)信息

定義關(guān)系表CategoryTree，其包含3個字段：

ancestor 祖先：上級節(jié)點的id

descendant 子代：下級節(jié)點的id

distance 距離：子代到祖先中間隔了幾級

這三個字段的組合是唯一的，因為在樹中，一條路徑可以標識一個節(jié)點，所以可以直接把它們的組合作為主鍵。以圖為例，節(jié)點6到它上一級的節(jié)點(節(jié)點4)距離為1在數(shù)據(jù)庫中存儲為ancestor=4,descendant=6,distance=1，到上兩級的節(jié)點(節(jié)點1)距離為2,于是有ancestor=1,descendant=6,distance=2，到根節(jié)點的距離為3也是如此，最后還要包含一個到自己的連接，當然距離就是0了。

這樣一來，不盡表中包含了所有的路徑信息，還在帶上了路徑中每個節(jié)點的位置（距離），對于樹結(jié)構(gòu)常用的查詢都能夠很方便的處理。下面看看如何用用它來實現(xiàn)我們的需求。

查詢id為5的節(jié)點的直屬子節(jié)點：

SELECT descendant FROM CategoryTree WHERE ancestor=5 AND distance=1

查詢所有子節(jié)點：

SELECT descendant FROM CategoryTree WHERE ancestor=5 AND distance>0

查詢某個上級節(jié)點的子節(jié)點，換句話說就是查詢具有指定上級節(jié)點的節(jié)點，也就是ancestor字段等于上級節(jié)點id即可，第二個距離distance決定了查詢的對象是由上級往下那一層的，等于1就是往下一層（直屬子節(jié)點），大于0就是所有子節(jié)點。這兩個查詢都是一句完成。

查詢由根節(jié)點到id為10的節(jié)點之間的所有節(jié)點，按照層級由小到大排序

SELECT ancestor FROM CategoryTree WHERE descendant=10 ORDER BY distance DESC

查詢id為10的節(jié)點（含）到id為3的節(jié)點（不含）之間的所有節(jié)點，按照層級由小到大排序

SELECT ancestor FROM CategoryTree WHERE descendant=10 AND 
distance<(SELECT distance FROM CategoryTree WHERE descendant=10 AND ancestor=3) 
ORDER BY distance DESC

查詢路徑，只需要知道descendant即可，因為descendant字段所在的行就是記錄這個節(jié)點與其上級節(jié)點的關(guān)系。如果要過濾掉一些則可以限制distance的值。

查詢id為5的節(jié)點是第幾級的

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

查詢id為5的節(jié)點是id為10的節(jié)點往下第幾級

SELECT distance FROM CategoryTree WHERE descendant=5 AND ancestor=10

查詢層級（深度）非常簡單，因為distance字段就是。直接以上下級的節(jié)點id為條件，查詢距離即可。

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

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

這個就不詳細說了，非常簡單。

插入和移動就不是那么方便了，當一個節(jié)點插入到某個父節(jié)點下方時，它將具有與父節(jié)點相似的路徑，然后再加上一個自身連接即可。

所以插入操作需要兩條語句，第一條復制父節(jié)點的所有記錄，并把這些記錄的distance加一，因為子節(jié)點到每個上級節(jié)點的距離都比它的父節(jié)點多一。當然descendant也要改成自己的。

例如把id為10的節(jié)點插入到id為5的節(jié)點下方（這里用了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é)點的移動沒有很好的解決方法，因為新位置所在的深度、路徑都可能不一樣，這就導致移動操作不是僅靠UPDATE語句能完成的，這里選擇刪除+插入實現(xiàn)移動。

另外，在有子樹的情況下，上級節(jié)點的移動還將導致下級節(jié)點的路徑改變，所以移動上級節(jié)點之后還需要修復下級節(jié)點的記錄，這就需要遞歸所有下級節(jié)點。

刪除id=5節(jié)點的所有記錄

DELETE FROM CategoryTree WHERE descendant=5

然后配合上面一節(jié)的插入操作實現(xiàn)移動。具體的實現(xiàn)直接上代碼吧。

ClosureTableCategoryStore.java是主要的邏輯，這里只展示部分代碼

    /**
     * 將一個分類移動到目標分類下面（成為其子分類）。被移動分類的子類將自動上浮（成為指定分類
     * 父類的子分類），即使目標是指定分類原本的父類。
     * 

     * 例如下圖(省略頂級分類)：
     *       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 被移動分類的id
     * @param target 目標分類的id
     * @throws IllegalArgumentException 如果id或target所表示的分類不存在、或id==target
     */
    public void move(int id, int target) {
        if(id == target) {
            throw new IllegalArgumentException("不能移動到自己下面");
        }
        moveSubTree(id, categoryMapper.selectAncestor(id, 1));
        moveNode(id, target);
    }

    /**
     * 將一個分類移動到目標分類下面（成為其子分類），被移動分類的子分類也會隨著移動。
     * 如果目標分類是被移動分類的子類，則先將目標分類（連帶子類）移動到被移動分類原來的
     * 的位置，再移動需要被移動的分類。
     * 

     * 例如下圖(省略頂級分類)：
     *       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 被移動分類的id
     * @param target 目標分類的id
     * @throws IllegalArgumentException 如果id或target所表示的分類不存在、或id==target
     */
    public void moveTree(int id, int target) {
        /* 移動分移到自己子樹下和無關(guān)節(jié)點下兩種情況 */
        Integer distance = categoryMapper.selectDistance(id, target);
        if (distance == null) {
            // 移動到父節(jié)點或其他無關(guān)系節(jié)點，不需要做額外動作
        } else if (distance == 0) {
            throw new IllegalArgumentException("不能移動到自己下面");
        } else {
            // 如果移動的目標是其子類，需要先把子類移動到本類的位置
            int parent = categoryMapper.selectAncestor(id, 1);
            moveNode(target, parent);
            moveSubTree(target, target);
        }

        moveNode(id, target);
        moveSubTree(id, id);
    }

    /**
     * 將指定節(jié)點移動到另某節(jié)點下面，該方法不修改子節(jié)點的相關(guān)記錄，
     * 為了保證數(shù)據(jù)的完整性，需要與moveSubTree()方法配合使用。
     *
     * @param id 指定節(jié)點id
     * @param parent 某節(jié)點id
     */
    private void moveNode(int id, int parent) {
        categoryMapper.deletePath(id);
        categoryMapper.insertPath(id, parent);
        categoryMapper.insertNode(id);
    }

    /**
     * 將指定節(jié)點的所有子樹移動到某節(jié)點下
     * 如果兩個參數(shù)相同，則相當于重建子樹，用于父節(jié)點移動后更新路徑
     *
     * @param id     指定節(jié)點id
     * @param parent 某節(jié)點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，這里只展示部分代碼

    /**
     * 查詢某個節(jié)點的第N級父節(jié)點。如果id指定的節(jié)點不存在、操作錯誤或是數(shù)據(jù)庫被外部修改，
     * 則可能查詢不到父節(jié)點，此時返回null。
     *
     * @param id 節(jié)點id
     * @param n 祖先距離（0表示自己，1表示直屬父節(jié)點）
     * @return 父節(jié)點id，如果不存在則返回null
     */
    @Select("SELECT ancestor FROM CategoryTree WHERE descendant=#{id} AND distance=#{n}")
    Integer selectAncestor(@Param("id") int id, @Param("n") int n);

    /**
     * 復制父節(jié)點的路徑結(jié)構(gòu),并修改descendant和distance
     *
     * @param id 節(jié)點id
     * @param parent 父節(jié)點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)系表中插入對自身的連接
     *
     * @param id 節(jié)點id
     */
    @Insert("INSERT INTO CategoryTree(ancestor,descendant,distance) VALUES(#{id},#{id},0)")
    void insertNode(int id);

    /**
     * 從樹中刪除某節(jié)點的路徑。注意指定的節(jié)點可能存在子樹，而子樹的節(jié)點在該節(jié)點之上的路徑并沒有改變，
     * 所以使用該方法后還必須手動修改子節(jié)點的路徑以確保樹的正確性
     *
     * @param id 節(jié)點id
     */
    @Delete("DELETE FROM CategoryTree WHERE descendant=#{id}")
    void deletePath(int id);

在分析推論后，終于找到了一種既有查詢簡單、效率高等優(yōu)點，也符合數(shù)據(jù)庫設(shè)計范式，而且是真正的無限級分類的設(shè)計。本方案的寫入操作雖然需要遞歸，但相比于前序遍歷樹效率仍高出許多，并且在本博客系統(tǒng)中分類不會頻繁修改。可見對于在關(guān)系數(shù)據(jù)庫中存儲一棵樹的需求，ClosureTable是一種比較完美的解決方案。

完整的JAVA實現(xiàn)代碼見 https://github.com/Kaciras/ClosureTableCateogryStore