嵌套集模型（樹）

名詞解釋

Nested set model

維基百科對「Nested set model」的解釋：

The nested set model is a particular technique for representing nested sets (also known as trees or hierarchies) in relational databases.

簡單講，即關係型數據庫里的樹形結構。

應用舉例

具體開發里遇到的具有嵌套的層級結構，諸如: 分類表、菜單表、有歸屬關係的用戶表，都可以基於樹實現。

下面以簡單的分類表作為示例，實現如下圖的結構(1-16為树遍历分配的编号)：

數據表結構

categories(id, name, _lft, _rgt, parent_id, created_at, updated_at)

categories 表大致的字段如上，與樹形結構相關的字段為 _lft , _rgt , parent_id ： _lft 和 _rgt 用於存儲節點的編號， parent_id 用於存儲父節點的 id 。

詳細的表結構和示例數據參見附件 👉 categories.sql

ID	name	_lft	_rgt	parent_id
1	技術	1	16	NULL
2	前端	2	9	1
3	JavaScript	3	4	2
4	CSS	5	6	2
5	HTML	7	8	2
6	後端	10	15	1
7	SQL	11	12	6
8	PHP	13	14	6

查詢 SQL

插入後代節點

往節點「後端」插入多一個子節點「Linux」：

按圖中遍歷順序，在「後端」節點後面才遍歷到的兄弟／父親節點左右編號需要調整，插入最好在一個事務里操作。

update `categories` set  
    `_lft` = case 
        when `_lft` >= 15 then `_lft`+2 
        else `_lft` end, 
    `_rgt` = case 
        when `_rgt` >= 15 then `_rgt`+2 
        else `_rgt` end 
    where 
        (`_lft` >= 15 or `_rgt` >= 15);

insert into `categories` 
    (`name`, `parent_id`, `_lft`, `_rgt`, `created_at`) 
values 
    ("Linux", 6, 15, 16, "2018-01-28 10:10:00");

查詢後代節點

以節點「後端」為例，查詢子節點：

select * from `categories` 
where `_lft` between 10 and 17 and id <>6;

查詢祖先節點

以節點「後端」為例，查詢其祖先節點：

select * from `categories` 
  where 
    (select `_`.`_rgt` from `categories` as `_` 
         where `id` = 6 limit 1) 
    between `_lft` and `_rgt`
  and 
    `id` <> 6;

樹的深度（分類級別）

記根節點所在的層深度為 0 ，則其子節點深度為 1 ，依次類推。查詢節點「後端」的深度：

select count(*) from `categories` as `_d` 
  where 
    (10 between `_d`.`_lft` and `_d`.`_rgt`)
  and 
     `_d`.`_lft` <> 10;