Laurence10's blog

Models for hierarchical data from Karwin Software Solutions LLC

前一陣子工作需要在 Database 裡面儲存一棵樹的資料
在 SlideShare 上看了一篇
Models for Hierarchical Data with SQL and PHP - by Bill Karwin, Percona Inc.
覺得蠻有趣的
特別用部落格整理一下
以下的圖片都來自原作者的 slides
SQL statements 的部分有些是作者 slides 內的
有些是我自己在 sqlfiddle 上試寫的
以 SQLite 支援的語法為主

作者介紹了四種實作
分別為 Adjacency List、Path Enumeration、Nested Sets 以及 Closure Table
並且很貼心的作了一張表來比較

作者以一個 bug 回報系統的討論區來作例子
可以想成一個節點就是一篇文章
你回覆某一篇你就成為該篇的子節點
(以下把節點稱作 Node)

Adjacency List

Adjacency List 算是大部分人第一時間會想到的方式
就是每一筆記錄一個 Node
然後用一個欄位來記 parent Node的 ID

新增，刪除，移動一個 Node, 或是移動子樹都很容易

-- 新增一個 Node 到 Node 5 下
INSERT INTO Comments (parent_id, author, comment)
VALUES (5,
        'Fran',
        'I agree!');

-- 刪除 Node 7
DELETE
FROM Comments
WHERE comment_id = 7;

-- 移動 Node 6 到 Node 3 底下 (若 Node 6 不是 leaf 則會移動整個 subtree)
UPDATE Comments
SET parent_id = 3
WHERE comment_id = 6;

查詢某一個 Node 的 children (只向下一個 level) 也不難

-- 取得 Node 2 的 children
SELECT c2.*
FROM Comments c1
LEFT JOIN Comments c2 ON (c2.parent_id = c1.comment_id)
WHERE c1.comment_id = 2;

但是要取得整顆子樹就不容易，因為必須遞迴地拿 (文章有介紹寫法，有興趣的可以去看)
因此刪除子樹也不容易

Path Enumeration

Path Enumeration 紀錄更多資訊，不像 Adjacency List 只記錄 parent 的 id
這個方法紀錄了從 root 到自己的完整路徑

新增，刪除，移動一個 Node, 或是移動子樹也不難

-- 新增一個 Node 到 Node 5 下
INSERT INTO Comments (author, comment)
VALUES ('Fran',
        'I agree');

UPDATE Comments
SET path =
    (SELECT path
     FROM Comments
     WHERE comment_id = 5) || last_insert_rowid() || '/'
WHERE comment_id = last_insert_rowid();

-- 刪除 Node 7
DELETE
FROM Comments
WHERE path LIKE
        (SELECT path
         FROM Comments
         WHERE comment_id = 7) || '%';

-- 移動 Node 6 到 Node 3 底下 (若 Node 6 不是 leaf 則會移動整個 subtree)
UPDATE Comments
SET path =
    (SELECT path
     FROM Comments
     WHERE comment_id = 3) || substr(path, instr(path, '6'))
WHERE path LIKE
        (SELECT path
         FROM Comments
         WHERE comment_id = 6) || '%';

與 Adjacent List 不同的是，查詢某一個 Node 的子樹不難

-- 取得 Node 2 的 subtree
SELECT *
FROM Comments
WHERE path LIKE
        (SELECT path
         FROM Comments
         WHERE comment_id = 2) || '%/%';

雖然投影片中說查一層 children 很難
但是我試了一下好像也還好

-- 取得 Node 2 的 children
SELECT *
FROM Comments
WHERE path LIKE
        (SELECT path
         FROM Comments
         WHERE comment_id = 2) || '_/';

Nested Sets

Nested Sets 蠻特別的，每一筆資料存著左右兩個數字
左數是一個比所有子節點的數字小的一個數 (每個子節點也是會有左右兩個數字)
右數則是一個比所有子節點的數字都大的一個數
所以 root 的左數一定是所有節點的左右數中最小的
反之 root 的右數則是所有節點的數字中最大的
頭暈了吧 XDDDDD
一圖勝萬言

查子樹很容易

-- 取得 Node 2 的 subtree
SELECT descendant.comment_id
FROM Comments parent
JOIN Comments descendant ON (descendant.nsleft BETWEEN parent.nsleft AND parent.nsright)
WHERE parent.comment_id = 2
    AND descendant.comment_id <> 2;

但是新增，刪除，移動一個 Node, 或是移動子樹都不容易
因為你會必須更動很多相關連的左右數
以新增一個 Node 為例

-- 新增一個 Node 到 Node 5 下
SELECT nsleft,
       nsright
FROM Comments
WHERE comment_id = 5;
-- 把結果存在 $nsleft_5, SQLite 沒有支援 local variable

UPDATE Comments
SET nsleft = CASE
                 WHEN nsleft >= ($nsleft_5 + 1) THEN nsleft + 2
                 ELSE nsleft
             END,
             nsright = nsright + 2
WHERE nsright >= $nsleft_5;

INSERT INTO Comments (nsleft, nsright, author, comment)
VALUES ($nsleft_5 + 1,
        $nsleft_5 + 2,
        'Fran',
        'I agree!');

slides 內也說明了一下查一層 children 的困難處
其實作者也把 SQL statements 寫出來了
只是真的不是很直覺，需要稍微在腦中想一下才知道他為什麼那樣寫

Closure Table

這是唯一用到兩張表的方法
一張表存 Nodes 的資訊
以 bug 回報系統來說，就是像作者，內文之類
另一張表存每一個 Node 到它自己所有的 descendants 的路徑
一樣一圖勝萬言

說真的我第一次看到這個方法時讚嘆不已
因為沒有研究過這個問題
所以沒想到有這樣的設計方式
投影片中更提到 TreePaths 這張表可以多存一個路徑長度的資訊
這樣在作一些查詢時會更容易一點

新增 Node 的時候要到 TreePaths 的表裡面建立相對應的路徑

-- 新增一個 Node 到 Node 5 下
INSERT INTO Comments(author, comment)
VALUES ('Fran',
        'I agree!');

-- 新增 paths, 複製指到 Node 5 的所有 paths 並把 descendants 換成新的
INSERT INTO TreePaths (ancestor, descendant, length)
SELECT ancestor,
       last_insert_rowid(),
       length + 1
FROM TreePaths
WHERE descendant = 5
    UNION ALL
    SELECT last_insert_rowid(),
           last_insert_rowid(),
           0; -- 加上一條自己指自己的 path

刪除也蠻簡單的

-- 刪除 Node 7
DELETE
FROM TreePaths
WHERE descendant = 7;

DELETE
FROM Comments
WHERE comment_id = 7;

利用 TreePaths 裡的 length 欄位
在查詢子樹或是一層的 children 時很方便

-- 取得 Node 2 的 children
SELECT c.*
FROM Comments c
JOIN TreePaths t ON (c.comment_id = t.descendant)
WHERE t.ancestor = 2
    AND t.length = 1;

-- 取得 Node 2 的 subtree
SELECT c.*
FROM Comments c
JOIN TreePaths t ON (c.comment_id = t.descendant)
WHERE t.ancestor = 2
    AND t.length > 0;

移動應該是最麻煩的
因為你要先刪掉所有相關的路徑
再重新建立移動後新的路徑

-- 移動 Node 6 到 Node 3 底下 (若 Node 6 不是 leaf 則會移動整個 subtree)
DELETE
FROM TreePaths
WHERE descendant IN
        (SELECT descendant
         FROM TreePaths
         WHERE ancestor = 6 )
    AND ancestor NOT IN
        (SELECT descendant
         FROM TreePaths
         WHERE ancestor = 6);

INSERT INTO TreePaths (ancestor, descendant, length)
SELECT supertree.ancestor,
       subtree.descendant,
       supertree.length + subtree.length + 1
FROM TreePaths AS supertree
JOIN TreePaths AS subtree
WHERE subtree.ancestor = 6
    AND supertree.descendant = 3;

最後是把整棵樹從 root 開始列出來所有 Nodes

SELECT n.*,
       p.ancestor AS parent
FROM TreePaths AS t
INNER JOIN Nodes AS n ON t.descendant = n.treeNodeId
LEFT JOIN TreePaths AS p ON p.descendant = n.treeNodeId
AND p.length = 1
WHERE (t.ancestor = 1)
    AND (p.ancestor IS NOT NULL
         OR n.treeNodeId = 1)
ORDER BY t.length;

Laurence10's blog

2017/02/02

在 Database 裡面儲存樹的內容

Adjacency List

Path Enumeration

Nested Sets

Closure Table