在各種基于關系數據庫的應用系統開發中，我們往往需要存儲樹型結構的數據，目前有很多流行的方法，如鄰接列表模型（The Adjacency List Model），在此基礎上也有很多人針對不同的需求做了相應的改進，但總是在某些方面存在的各種各樣的缺陷。
那么理想中的樹型結構應具備哪些特點呢？數據存儲冗余小、直觀性強；方便返回整個樹型結構數據；可以很輕松的返回某一子樹（方便分層加載）；快整獲以某節 點的祖譜路徑；插入、刪除、移動節點效率高等等。帶著這些需求我查找了很多資料，發現了一種理想的樹型結構數據存儲及操作算法，改進的前序遍歷樹模型 （The Nested Set Model）。
一、數據
在本文中，舉一個在線食品店樹形圖的例子。這個食品店通過類別、顏色和品種來組織食品。樹形圖如下：
二、鄰接列表模型（The Adjacency List Model）
在這種模型下，上述數據在關系數據庫的表結構數據通常如下圖所示：
由于該模型比較簡單，在此不再詳細介紹其算法，下面列出它的一些不足：
在大多數編程語言中，他運行很慢，效率很差。這主要是“遞歸”造成的。我們每次查詢節點都要訪問數據庫。每次數據庫查詢都要花費一些時間，這讓函數處理龐 大的樹時會十分慢。造成這個函數不是太快的第二個原因可能是你使用的語言。不像Lisp這類語言，大多數語言不是針對遞歸函數設計的。對于每個節點造成這 個函數不是太快的第二個原因可能是你使用的語言。不像Lisp這類語言，大多數語言不是針對遞歸函數設計的。對于每個節點，函數都要調用他自己，產生新的 實例。這樣，對于一個4層的樹，你可能同時要運行4個函數副本。對于每個函數都要占用一塊內存并且需要一定的時間初始化，這樣處理大樹時遞歸就很慢了。
三、改進的前序遍歷樹模型（The Nested Set Model）
原理：
我們先把樹按照水平方式擺開。從根節點開始（“Food”），然后他的左邊寫上1。然后按照樹的順序（從上到下）給“Fruit”的左邊寫上2。這樣，你 沿著樹的邊界走啊走（這就是“遍歷”），然后同時在每個節點的左邊和右邊寫上數字。最后，我們回到了根節點“Food”在右邊寫上18。下面是標上了數字 的樹，同時把遍歷的順序用箭頭標出來了。
我們稱這些數字為左值和右值（如，“Food”的左值是1，右值是18）。正如你所見，這些數字按時了每個節點之間的關系。因為“Red”有3和6兩個 值，所以，它是有擁有1-18值的“Food”節點的后續。同樣的，我們可以推斷所有左值大于2并且右值小于11的節點，都是有2-11的“Fruit” 節點的后續。這樣，樹的結構就通過左值和右值儲存下來了。這種數遍整棵樹算節點的方法叫做“改進前序遍歷樹”算法。
表結構設計：
常用的操作：
下面列出一些常用操作的SQL語句
返回完整的樹（Retrieving a Full Tree）
SELECT node.name
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.name = 'electronics'
ORDER BY node.lft
返回某結點的子樹（Find the Immediate Subordinates of a Node）
SELECT V.*
FROM (SELECT node.name,
(COUNT(parent.name) - (AVG(sub_tree.depth) + 1)) depth
FROM nested_category node,
nested_category parent,
nested_category sub_parent,
(SELECT V.*
FROM (SELECT node.name, (COUNT(parent.name) - 1) depth
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'portable electronics'
GROUP BY node.name) V,
nested_category T
WHERE V.name = T.name
ORDER BY T.lft) sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name) V,
nested_category T
WHERE V.name = T.name
and V.depth <= 1
and V.depth > 0
ORDER BY T.Lft
返回某結點的祖譜路徑（Retrieving a Single Path）
SELECT parent.name
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'flash'
ORDER BY node.lft
返回所有節點的深度（Finding the Depth of the Nodes）
SELECT V.*
FROM (SELECT node.name, (COUNT(parent.name) - 1) depth
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name) V,
nested_category T
WHERE V.name = T.name
ORDER BY T.Lft
返回子樹的深度（Depth of a Sub-Tree）
SELECT V.*
FROM (SELECT node.name,
(COUNT(parent.name) - (AVG(sub_tree.depth) + 1)) depth
FROM nested_category node,
nested_category parent,
nested_category sub_parent,
(SELECT V.*
FROM (SELECT node.name, (COUNT(parent.name) - 1) depth
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'portable electronics'
GROUP BY node.name) V,
nested_category T
WHERE V.name = T.name
ORDER BY T.lft) sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name) V,
nested_category T
WHERE V.name = T.name
ORDER BY T.Lft
返回所有的葉子節點（Finding all the Leaf Nodes）
SELECT name FROM nested_category WHERE rgt = lft + 1
插入節點（Adding New Nodes）
LOCK TABLE nested_category WRITE;
SELECT @myRight := rgt FROM nested_category WHERE name = 'TELEVISIONS';
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO nested_category
(name, lft, rgt)
VALUES
('GAME CONSOLES', @myRight + 1, @myRight + 2);
UNLOCK TABLES;
刪除節點（Deleting Nodes）
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'GAME CONSOLES';
DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
UNLOCK TABLES;