圖文詳解！吃透 MySQL中處理分層數據的模型手冊，只需半小時

IT界的奮鬥者

前言

大多數用戶都曾在數據庫中處理過分層數據(hierarchical data)，認為分層數據的管理不是關系數據庫的目的。之所以這麼認為，是因為關系數據庫中的表沒有層次關系，只是簡單的平面化的列表；而分層數據具有父－子關系，顯然關系數據庫中的表不能自然地表現出其分層的特性。

我們認為，分層數據是每項只有一個父項和零個或多個子項（根項除外，根項沒有父項）的數據集合。分層數據存在於許多基於數據庫的應用程序中，包括論壇和郵件列表中的分類、商業組織圖表、內容管理系統的分類、產品分類。我們打算使用下面一個虛構的電子商店的產品分類：

這些分類層次與上面提到的一些例子中的分類層次是相類似的。在本文中我們將從傳統的鄰接表(adjacency list)模型出發，闡述 2種在MySQL中處理分層數據的模型。

鄰接表模型

上述例子的分類數據將被存儲在下面的數據表中（我給出了全部的數據表創建、數據插入的代碼，可以跟著寫：

在鄰接表模型中，數據表中的每項包含了指向其父項的指示器。在此例中，最上層項的父項為空值(NULL)。鄰接表模型的優勢在於它很簡單，可以很容易地看出 FLASH是MP3 PLAYERS的子項，哪個是portable electronics的子項，哪個是electronics的子項。雖然，在客戶端編碼中鄰接表模型處理起來也相當的簡單，但是如果是純 SQL編碼的話，該模型會有很多問題。

檢索整樹

通常在處理分層數據時首要的任務是，以某種縮進形式來呈現一棵完整的樹。為此，在純SQL編碼中通常的做法是使用自連接(self-join)：

檢索所有葉子節點

我們可以用左連接(LEFT JOIN)來檢索出樹中所有葉子節點(沒有孩子節點的節點）：

檢索單一 路徑

通過自連接，我們也可以檢索出單一路徑：

這種方法的主要局限是你需要為每層數據添加一個自連接，隨著層次的增加，自連接變得越來越複雜，檢索的性能自然而然的也就下降了。

鄰接表 模型 的 局限 性

用純SQL 編碼實現鄰接表模型有一定的難度。在我們檢索某分類的路徑之前，我們需要知道該分類所在的層次。另外，我們在刪除節點的時候要特別小心，因為潛在的可能會孤立一棵子樹（當刪除portable electronics 分類時，所有他的子分類都成了孤兒）。部分局限性可以通過使用客戶端代碼或者存儲過程來解決，我們可以從樹的底部開始向上迭代來獲得一顆樹或者單一路徑，我們也可以在刪除節點的時候使其子節點指向一個新的父節點，來防止孤立子樹的產生。

嵌套 集合 (Nested Set) 模型

我想在這篇文章中重點闡述一種不同的方法，俗稱為 嵌套 集合模型。在嵌套集合模型中，我們將以一種新的方式來看待我們的分層數據，不再是線與點了，而是嵌套容器。我試著以嵌套容器的方式畫出了electronics 分類圖：

從上圖可以看出我們依舊保持了數據的層次，父分類包圍了其子分類。在數據表中，我們通過使用表示節點的嵌套關系的左值(left value)和右值(right value)來表現嵌套集合模型中數據的分層特性：

我們使用了lft 和rgt來代替 left和 right，是因為在MySQL中left 和right是保留字。

當我們為樹狀的結構編號時，我們從左到右，一次一層，為節點賦右值前先從左到右遍曆其子節點給其子節點賦左右值。這種方法被稱作改進的先 序 遍曆 算法。

檢索整樹

我們可以通過自連接把父節點連接到子節點上來檢索整樹，是因為子節點的 lft值總是在其父節點的 lft 值和r rg gt t值之間：

不像先前鄰接表模型的例子，這個查詢語句不管樹的層次有多深都能很好的工作。在

BETWEEN的子句中我們沒有去關心 node的rgt值，是因為使用 node的rgt值得出的父節點總是和使用lft 值得出的是相同的。

檢索所有葉子節點

檢索出所有的葉子節點，使用嵌套集合模型的方法比鄰接表模型的 LEFT JOIN方法簡單多了。如果你仔細得看了nested_category 表，你可能已經注意到葉子節點的左右值是連續的。要檢索出葉子節點，我們只要查找滿足 rgt=lft+1 的節點：

檢索單一路徑

在嵌套集合模型中，我們可以不用多個自連接就可以檢索出單一路徑：

檢索節點的深度

我們已經知道怎樣去呈現一棵整樹，但是為了更好的標識出節點在樹中所處層次，我們怎樣才能檢索出節點在樹中的深度呢？我們可以在先前的查詢語句上增加 COUNT函數和GROUP BY

子句來實現：

我們可以根據depth 值來縮進分類名字，使用CONCAT和REPEAT 字符串函數 1 ：

當然，在客戶端應用程序中你可能會用 depth值來直接展示數據的層次。Web開發者會遍曆該樹，隨著depth 值的增加和減少來添加<li></li>和<ul></ul>標簽。

檢索子樹的深度

當我們需要子樹的深度信息時，我們不能限制自連接中的 node或parent，因為這麼做會打亂數據集的順序。因此，我們添加了第三個自連接作為子查詢，來得出子樹新起點的深度值：

這個查詢語句可以檢索出任一節點子樹的深度值，包括根節點。這裏的深度值跟你指定的節點有關。

檢索節點的直接子節點

可以想象一下，你在零售網站上呈現電子產品的分類。當用戶點擊分類後，你將要呈現該分類下的產品，同時也需列出該分類下的直接子分類，而不是該分類下的全部分類。為此，我們只呈現該節點及其直接子節點，不再呈現更深層次的節點。例如，當呈現 PORTABLE

ELECTRONICS分類時，我們同時只呈現MP3 PLAYERS、CD PLAYERS和2 WAY RADIOS分類，而不呈現FLASH 分類。

要實現它非常的簡單，在先前的查詢語句上添加 HAVING子句：

如果你不希望呈現父節點，你可以更改 HA VIN NG G depth <= 1 1為 HA VIN NG G depth = = 1。

嵌套 集合模型中集合 函 數的應用

讓我們添加一個產品表，我們可以使用它來示例集合函數的應用：

現在，讓我們寫一個查詢語句，在檢索分類樹的同時，計算出各分類下的產品數量：

這條查詢語句在檢索整樹的查詢語句上增加了 COUNT和GROUP BY子句，同時在WHERE 子句中引用了product 表和一個自連接。

新增節點

到現在，我們已經知道了如何去查詢我們的樹，是時候去關注一下如何增加一個新節點來更新我們的樹了。讓我們再一次觀察一下我們的嵌套集合圖：

當我們想要在TELEVISIONS 和PORTABLE ELECTRONICS節點之間新增一個節點，新節點的 lft和r rg gt t 的 值為10和 11，所有該節點的右邊節點的 lft和rgt值都將加2，之後我們再添加新節點並賦相應的lft 和rgt值。在 MySQL 5 中可以使用存儲過程來完成，我假設當前大部分讀者使用的是MySQL 4.1 版本，因為這是最新的穩定版本。所以，我使用了鎖表（LOCKTABLES）語句來隔離查詢：

我們可以檢驗一下新節點插入的正確性：

如果我們想要在葉子節點下增加節點，我們得稍微修改一下查詢語句。讓我們在 2 WAYRADIOS葉子節點下添加 FRS節點吧：

在這個例子中，我們擴大了新產生的父節點(2 WAY RADIOS 節點）的右值及其所有它的右邊節點的左右值，之後置新增節點於新父節點之下。正如你所看到的，我們新增的節點已經完全融入了嵌套集合中：

刪 除節點

最後還有個基礎任務，刪除節點。刪除節點的處理過程跟節點在分層數據中所處的位置有關，刪除一個葉子節點比刪除一個子節點要簡單得多，因為刪除子節點的時候，我們需要去處理孤立節點。

刪除一個葉子節點的過程正好是新增一個葉子節點的逆過程，我們在刪除節點的同時該節點右邊所有節點的左右值和該父節點的右值都會減去該節點的寬度值 2 ：

我們再一次檢驗一下節點已經成功刪除,而且沒有打亂數據的層次：

這個方法可以完美地刪除節點及其子節點：

有時，我們只刪除該節點，而不刪除該節點的子節點。在一些情況下，你希望改變其名字為占位符，直到替代名字的出現，比如你開除了一個主管（需要更換主管）。在另外一些情況下，你希望子節點掛到該刪除節點的父節點下：

在這個例子中，我們對該節點所有右邊節點的左右值都減去了 2（因為不考慮其子節點，該節點的寬度為2），對該節點的子節點的左右值都減去了1（彌補由於失去父節點的左值造成的裂縫）。我們再一次確認，那些節點是否都晉升了：

有時，當刪除節點的時候，把該節點的一個子節點掛載到該節點的父節點下，而其他節點掛到該節點父節點的兄弟節點下。

本篇內容比較多，看到最後的小夥伴可以關注轉發，私信領取福利