在數(shù)據(jù)庫中存儲一棵樹，實現(xiàn)無限級分類
在一些系統(tǒng)中，對內(nèi)容進行分類是必需的功能。比如電商就需要對商品做分類處理，以便于客戶搜索；論壇也會分為很多板塊；門戶網(wǎng)站、也得對網(wǎng)站的內(nèi)容做各種分類。
分類對于一個內(nèi)容展示系統(tǒng)來說是不可缺少的，本博客也需要這么一個功能。眾所周知，分類往往具有從屬關(guān)系，比如鉛筆盒鋼筆屬于筆，筆又是文具的一種，當(dāng)然鋼筆還可以按品牌來細分，每個品牌下面還有各種系列...
這個例子中從屬關(guān)系具有5層，從上到下依次是：文具-筆-鋼筆-XX牌-A系列，但實際中分類的層數(shù)卻是無法估計的，比如生物中的界門綱目科屬種有7級。顯然對分類的級數(shù)做限制是不合理的，一個良好的分類系統(tǒng)，其應(yīng)當(dāng)能實現(xiàn)***級分類。
在寫自己的博客網(wǎng)站時，剛好需要這么一個功能，聽起來很簡單，但是在實現(xiàn)時卻發(fā)現(xiàn)，用關(guān)系數(shù)據(jù)庫存儲***級分類并非易事。
1.需求分析
首先分析一下分類之間的關(guān)系是怎樣的，很明顯，一個分類下面有好多個下級分類，比如筆下面有鉛筆和鋼筆；那么反過來，一個下級分類能夠?qū)儆趲讉€上級分類呢？這其實并不確定，取決于如何對類型的劃分。比如有辦公用品和家具，那么辦公桌可以同時屬于這兩者，不過這會帶來一些問題，比如：我要顯示從***分類到它之間的所有分類，那么這種情況下就很難決定辦公用品和家具顯示哪一個，并且如果是多對一，實現(xiàn)上將更加復(fù)雜，所以這里還是限定每個分類僅有一個上級分類。
現(xiàn)在，分類的關(guān)系可以表述為一父多子的繼承關(guān)系，正好對應(yīng)數(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è)應(yīng)用中，比如電商、博客平臺等，這些應(yīng)用里一般都有緩存機制，對于分類這種不頻繁修改的數(shù)據(jù)，即使在底層數(shù)據(jù)庫中存在緩慢的操作，只要上層緩存能夠***，一樣有很快的響應(yīng)速度。但是對于抽象的需求：在關(guān)系數(shù)據(jù)庫中存儲一棵樹，并不僅僅存在于有緩存的應(yīng)用中，所以設(shè)計一個高效的存儲方案，仍然有其意義。
下面就以這個賣文具的電商的場景為例，針對這6條需求，設(shè)計一個數(shù)據(jù)庫存儲方案（對過程沒興趣可以直接轉(zhuǎn)到第4節(jié)）。
2.一些常見設(shè)計方案的不足
2.1 直接記錄父分類的引用
在許多編程語言中，繼承關(guān)系都是一個類僅繼承于一個父類，添加這種繼承關(guān)系僅需要聲明一下父類即可，比如JAVA中extends xxx。根據(jù)這種思想，我們僅需要在每個分類上添加上直屬上級的id，即可存儲它們之間的繼承關(guān)系。
表中parent即為直屬上級分類的id，***分類設(shè)為0。這種方案簡單易懂，僅存在一張表，并且沒有冗余字段，存儲空間占用極小，在數(shù)據(jù)庫層面是一種很好的設(shè)計。
那么再看看對操作的支持情況怎么樣，***條單個增改查都是一句話完事就不多說了，刪除的話記得把下級分類的id全部改成被刪除分類的上級分類即可，也就多一個UPDATE。
第二條可就麻煩了，比如我要查文具的下級分類，預(yù)期結(jié)果是筆、鉛筆、鋼筆三個，但是并沒有辦法通過文具一次性就查到鉛筆盒鋼筆，因為這兩者的關(guān)系間接存儲在筆這個分類里，需要先查出直屬下級（筆），才能夠往下查詢，這意味著需要遞歸，性能上一下子就差了很多。
第三條同樣需要遞歸，因為通過一個分類，數(shù)據(jù)庫中只存儲了其直屬父類，需要通過遞歸到***分類才能獲取到它們之間的所有分類信息。
綜上所述，最關(guān)鍵的兩個需求都需要使用性能最差的遞歸方式,這種設(shè)計肯定是不行的。但還是繼續(xù)看看剩下的幾條吧。
第4個需求：查詢分類是哪一級的？這個還是得需要遞歸或循環(huán)，查出所有上級分類的數(shù)量即為分類的層級。
移動分類倒是非常簡單，直接更新父id即可，這也是這種方案的唯一優(yōu)勢了吧...如果你的分類修改比查詢還多不妨就這么做吧。
***一個查詢某一級的所有分類，對于這個設(shè)計簡直是災(zāi)難，它需要先找出所有一級分類，然后循環(huán)一遍，找出所有一級分類的子類就是二級分類...如此循環(huán)直到所需的級數(shù)為之。所以這種設(shè)計里，這個功能基本是廢了。
這個方式也是一開始就能想到的，在數(shù)據(jù)量不大（層級不深）的情況下，因為其簡單直觀的特點，不失為一個好的選擇，不過對于本項目來說還不夠（本項目立志成為***博客平臺?。。。?。
2.2 路徑列表
從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字段，然后在應(yīng)用層里分割一下即可獲得獲得所有上級，并且順序也能保證。
查詢某一級的分類也簡單，因為層級越深，path就越長，使用LENGTH()函數(shù)作為條件即可篩選出合適的結(jié)果。反過來，根據(jù)其長度也能夠計算出分類的級別。
移動操作需要遞歸，因為每一個分類的path都是它父類的path加上父類的id,將分類及其所有子分類的path設(shè)為其父類的path并在***追加父類的id即可。
在許多系統(tǒng)中都使用了這種方案，其各方面都具有可以接受的性能，理解起來也比較容易。但是其有兩點不足：1.就是不遵守數(shù)據(jù)庫范式，將列表數(shù)據(jù)直接作為字符串來存儲，這將導(dǎo)致一些操作需要在上層解析path字段的值；2.就是字段長度是有限的，不能真正達到***級深度，并且大字段對索引不利。如果你不在乎什么范式，分類層級也遠達不到字段長度的限制，那么這種方案是可行的。
2.3 前序遍歷樹
這是一種在數(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。下面是標(biāo)上了數(shù)字的樹，同時把遍歷的順序用箭頭標(biāo)出來了。
我們稱這些數(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字段想***種方式一樣慢慢遍歷。
綜上所述，對于本項目而言，它還不如第二種，所以這個很復(fù)雜的方案也得否決掉。
3.新方案的思考
上面幾種方案最接近理想的就是第二種，如果能解決字段長度問題和不符合范式，以及需要上層參與處理的問題就好了。不過不要急，先看看第二種方案的的優(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。
4.基于ClosureTable的***級分類存儲
ClosureTable直譯過來叫閉包表？不過不重要，ClosureTable以一張表存儲節(jié)點之間的關(guān)系、其中包含了任何兩個有關(guān)系（上下級）節(jié)點的關(guān)聯(lián)信息
定義關(guān)系表CategoryTree，其包含3個字段：
- ancestor 祖先：上級節(jié)點的id
- descendant 子代：下級節(jié)點的id
- distance 距離：子代到祖先中間隔了幾級
這三個字段的組合是唯一的，因為在樹中，一條路徑可以標(biāo)識一個節(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也是如此，***還要包含一個到自己的連接，當(dāng)然距離就是0了。
這樣一來，不盡表中包含了所有的路徑信息，還在帶上了路徑中每個節(jié)點的位置（距離），對于樹結(jié)構(gòu)常用的查詢都能夠很方便的處理。下面看看如何用用它來實現(xiàn)我們的需求。
4.1 子節(jié)點查詢
查詢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é)點。這兩個查詢都是一句完成。
4.2 路徑查詢
查詢由根節(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的值。
4.3 查詢節(jié)點所在的層級（深度）
查詢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為條件，查詢距離即可。
4.4 查詢某一層的所有節(jié)點
查詢所有第三層的節(jié)點
- SELECT descendant FROM CategoryTree WHERE ancestor=0 AND distance=3
這個就不詳細說了，非常簡單。
4.5 插入
插入和移動就不是那么方便了，當(dāng)一個節(jié)點插入到某個父節(jié)點下方時，它將具有與父節(jié)點相似的路徑，然后再加上一個自身連接即可。
所以插入操作需要兩條語句，***條復(fù)制父節(jié)點的所有記錄，并把這些記錄的distance加一，因為子節(jié)點到每個上級節(jié)點的距離都比它的父節(jié)點多一。當(dāng)然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)
4.6 移動
節(jié)點的移動沒有很好的解決方法，因為新位置所在的深度、路徑都可能不一樣，這就導(dǎo)致移動操作不是僅靠UPDATE語句能完成的，這里選擇刪除+插入實現(xiàn)移動。
另外，在有子樹的情況下，上級節(jié)點的移動還將導(dǎo)致下級節(jié)點的路徑改變，所以移動上級節(jié)點之后還需要修復(fù)下級節(jié)點的記錄，這就需要遞歸所有下級節(jié)點。
刪除id=5節(jié)點的所有記錄
- DELETE FROM CategoryTree WHERE descendant=5
然后配合上面一節(jié)的插入操作實現(xiàn)移動。具體的實現(xiàn)直接上代碼吧。
ClosureTableCategoryStore.java是主要的邏輯，這里只展示部分代碼
- /**
- * 將一個分類移動到目標(biāo)分類下面（成為其子分類）。被移動分類的子類將自動上?。ǔ蔀橹付ǚ诸?nbsp;
- * 父類的子分類），即使目標(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 被移動分類的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("不能移動到自己下面");
- }
- moveSubTree(id, categoryMapper.selectAncestor(id, 1));
- moveNode(id, target);
- }
- /**
- * 將一個分類移動到目標(biāo)分類下面（成為其子分類），被移動分類的子分類也會隨著移動。
- * 如果目標(biāo)分類是被移動分類的子類，則先將目標(biāo)分類（連帶子類）移動到被移動分類原來的
- * 的位置，再移動需要被移動的分類。
- * <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 被移動分類的id
- * @param target 目標(biāo)分類的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 {
- // 如果移動的目標(biāo)是其子類，需要先把子類移動到本類的位置
- 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ù)相同，則相當(dāng)于重建子樹，用于父節(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);
- /**
- * 復(fù)制父節(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);
5.結(jié)語
在分析推論后，終于找到了一種既有查詢簡單、效率高等優(yōu)點，也符合數(shù)據(jù)庫設(shè)計范式，而且是真正的***級分類的設(shè)計。本方案的寫入操作雖然需要遞歸，但相比于前序遍歷樹效率仍高出許多，并且在本博客系統(tǒng)中分類不會頻繁修改?？梢妼τ谠陉P(guān)系數(shù)據(jù)庫中存儲一棵樹的需求，ClosureTable是一種比較***的解決方案。
完整的JAVA實現(xiàn)代碼見 https://github.com/Kaciras/Examples-java/tree/master/ClosureTable
