是說，因為Joomla!本身就有內建的關係，已經用了很久的 Nested set model 了，最近才發現其實中文環境下對這類用法的討論不是很多。簡體的文章倒是有個兩三篇，不如來寫個繁體版的吧。
Nested set model 是一個用來方便處理樹狀節點資料結構的資料模型，可以讓我們在不需要遍歷整顆樹的情況下，用極少的主機資源獲取節點、計算節點數量或是映射關連資料表。
臨接表模型
首先我們來談談傳統處理巢狀結構的資料設計，下面是一個採用 parent_id 處理樹狀結構的資料表。
Table: `tree`
| id | parent_id | title |
|----|-----------|-------|
| 1 | 0 | ROOT |
| 2 | 1 | four |
| 3 | 1 | node |
| 4 | 2 | node |
| 5 | 2 | node |
| 6 | 3 | node |
我們可以看到每筆資料都有一個 parent_id 指向父節點。當我們需要取得子節點的時候，SQL 可以這樣下：
SELECT * FROM `tree` WHERE `parent_id` = 1;
這樣寫法的優點是簡潔明瞭，代碼可讀性高。當然缺點就是如果我們想要一次獲取多層次資料，或者想要計算節點數量時，必然得要用遞迴的方式持續跑下去，對資料庫的使用會非常吃重。
前序遍歷樹
而 Nested set model 就是一種不錯的解決辦法（大陸翻譯叫前序遍歷樹）。
我們先來看看 Nested set model 的樹狀原理，每個節點有一個左鍵與右鍵，我們通常替他命名為 lft 與 rgt。假設一開始有一個主節點 A
A (1,2)
當我加入 B 節點在 A 下面時，會變成
A (1,4)
|
|
B (2,3)
接著再加入 C 節點:
A (1,6)
|
---------------
| |
B (2,3) C (4,5)
於是，很明顯的，B與C的左右鍵數字都被包在A裡面，如果我想要取得B與C，SQL 可以這樣下：
# 假設一般的程式運作流程，我們可能先用 ORM 之類的取得 A 的資料
SELECT * FROM `tree` WHERE `id` = 1;
# 取得 A 之後，用 A 的 lft, rgt 來query
SELECT * FROM `tree` WHERE `lft` > 1 AND `rgt` < 6
# 如果想要包含 A 一起的話
SELECT * FROM `tree` WHERE `lft` >= 1 AND `rgt` <= 6
# 以上寫法可以用任何一個語言實現
這樣的好處應該很明顯了，參考下圖：
我只要用 lft > 1 AND rgt < 22 就能一口氣抓出所有的節點，若是原有的臨接表模型，可能要執行 5 次查詢才能取得或計算所有子節點。
如何初始化一棵樹
Nested set 最重要的一點在於，一定要有一個根節點，作為所有節點的起始，而且通常這個節點是不被使用的。一開始，我們要建立一個含有 parent_id, lft, rgt 的表。 parent_id 是用在向上查詢用的。另外為了方便控制查詢層級，我們還可以加一個 level 來記錄目前的層級。
一個分類表的初始化
| id | parent_id | title | lft | rgt | level |
|----|-----------|-------|-----|-----|-------|
| 1 | 0 | ROOT | 1 | 2 | 1 |
下面這是簡單的產生語法：
CREATE TABLE IF NOT EXISTS `categories` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`parent_id` int(10) UNSIGNED NOT NULL DEFAULT '0',
`lft` int(11) NOT NULL DEFAULT '0',
`rgt` int(11) NOT NULL DEFAULT '0',
`level` int(10) UNSIGNED NOT NULL DEFAULT '0',
`title` varchar(255) NOT NULL,
PRIMARY KEY (`id`),
KEY `idx_left_right` (`lft`,`rgt`)
) DEFAULT CHARSET=utf8;
INSERT INTO `categories` VALUE (1, 0, 'ROOT', 1, 2, 1);
準備範例資料
這裡我們準備一個範例資料，包含分類表與文章表：
分類 category
| id | parent_id | title | lft | rgt | level |
|----|-----------|-------|-----|-----|-------|
| 1 | 0 | ROOT | 1 | 10 | 1 |
| 2 | 1 | A | 2 | 7 | 2 |
| 3 | 2 | B | 3 | 4 | 3 |
| 4 | 2 | C | 5 | 6 | 3 |
| 5 | 1 | D | 8 | 9 | 2 |
文章 articles
| id | title | catid |
|----|------------|-------|
| 1 | Article 1 | 1 |
| 2 | Article 2 | 2 |
| 3 | Article 3 | 3 |
| 4 | Article 4 | 3 |
| 5 | Article 5 | 4 |
| 6 | Article 6 | 5 |
一些簡單的查詢範例
取得 A 分類下所有分類的所有文章 （部落格分類很好用）
SELECT `a`.*, `b`.*
FROM `articlea` AS `a`
LEFT JOIN `categories` AS b ON `a`.`catid` = `b`.`id`
WHERE
`b`.`lft` >= 2 AND `b`.`rgt` <= 7
# 或
`b`.`lft` BETWEEN 2 AND 7
限制層次
SELECT `a`.*, `b`.*
FROM `articles` AS `a`
LEFT JOIN `categories` AS b ON `a`.`catid` = `b`.`id`
WHERE
`b`.`lft` >= 2 AND `b`.`rgt` <= 7
AND
`b`.`level` < 2
反向查詢 B 節點的所有父代節點
SELECT `categories`.*
FROM `categories` AS `node`, `categories` AS `parent`
WHERE
`node`.`lft` BETWEEN `parent`.`lft` AND `parent`.`rgt`
AND `node`.`id` = 3
增加一個節點在 B 前面
-- 先空出位置，所有 rgt, lft + 2
UPDATE `categories` SET
`rgt` = `rgt` + 2,
`lft` = `lft` + 2
where
`lft` > 2
-- 再插入節點
INSERT INTO `categories` VALUE ({id}, 'New Article', 2, 3, 4, 3);
大概先介紹到此，用任何語言應該都可以輕易實現，另外還可以加很多欄位來延伸各種功能，例如 joomla 就加了一個 path 欄位，內容長得像這樣 parent/parent2/child/child2 ，用在應用程式本身要快速比對節點層次時就很容易。
當然 Nested set 的缺點就是用新增或移動節點時，必須要遍歷整張樹來重建索引，效能上不是很好。不過對於一般應用來說，等同是用後台儲存操作的效能來換取前台讀取的效能，在高流量系統上也不失為一種解決辦法。
