在各種基于關系數據庫的應用系統開發中，我們往往需要存儲樹型結構的數據，目前有很多流行的方法，如鄰接列表模型（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;