[Data Structure]Storing Hierarchical Data by Interval Tree
前言
在每個系統裡面，很容易遇到階層式的資料，什麼叫做階層式的資料呢？
例如我們有個Entity叫做Department，這個Entity是有self-relation，如圖所示：
實際的資料則可能長這樣：
而這樣階層式的資料在系統內，很常有一個需求就是要把某個node底下所有node篩選出來，
例如「技術支援處」底下有哪一些相關單位，例如「台北分公司」底下有哪一些部門，諸如此類的資料。
Solution
這邊舉的例子使用樹狀結構來modeling 階層式的資料，
通常遇到這樣的資料，要設計出self-relation的data model，我們最常採用Parent欄位來表示node與node之間的階層關係，如下圖所示：
如何找出node A底下所有node，以這樣的資料結構，程式實作來說，
步驟1：把自己ID記到Array中
步驟2：把資料表中，Parent欄位為自己ID的資料篩選出來
- 2.1：當資料筆數大於0，每一筆資料再呼叫一次步驟1與步驟2
- 2.2：當資料筆數等於0，則結束。
所以要走遍某個node底下所有的node，就需要透過for loop+遞迴的方式來設計，才能將所有node加入清單內。
以上述這個例子來說，程式實際執行過程應為
- 加入A
- 尋找Parent為A的資料，找到兩筆(B與F)，第一筆B
- 加入B，尋找Parent為B的資料，找到三筆(C、D、E)，第一筆C
- 加入C，尋找Parent為C的資料，找到0筆。
- 第二筆D，加入D，尋找Parent為D的資料，找到0筆。
- 第三筆E，加入E，尋找Parent為E的資料，找到0筆。
- 第二筆F，加入F，尋找Parent為F的資料，找到0筆。結束。
清單中就有A～F的node，但是這樣的資料一旦龐大，找階層式資料的effort就會爆炸性的擴大。
怎麼解決這樣的問題？我們這邊要使用的是透過interval tree(或稱為range tree)
Interval Tree
這個方式的出處是一篇paper，Storing Hierarchical Data in a Database, Gijs Van Tulder, http://www.sitepoint.com/print/hierarchical-data-database/
(我也沒對這篇paper徹底研究，不過它的核心觀念實在是太簡單了，所以希望可以拋出來引起大家的共鳴。)
我們先來看一下圖解：
我們給每個node兩個屬性，分別是下限與上限，下限上限屬性的規則如上圖所示，
有點類似畫圈圈的方式，把整個tree給圈起來。
當資料給定之後，DB應該會像右上圖的表格一樣。
接著神奇的事情就這麼發生了，當我們要選定任意一個Node X底下的所有node集合，請跟著我這麼做：
- 找到X的下限、上限
- Select ID Form Table
Where [下限] > X.下限
And [上限] < X.上限
就這樣一行select from+where搞定。以A為例，就尋找table中上下限介於1～12的資料。
什麼？人客想要找end node有哪一些?
沒問題，只要找下限上限差1的資料就可以了。
當新增一個node G在E底下時，邏輯也相當簡單，
我們看下一張圖：
插入新Node Y於X node，
- 找到X的下限
- Y的下限為X下限+1，Y的上限為X下限+2
- Table上下限>X.下限的資料，上下限資料都要+2
以上，是透過interval tree來篩選階層式資料的方式，
這只是最陽春的描述，table還可以搭配原本的方式來達到其他效果，例如paper上的圖
結論
沒想到上班之後還能遇到這麼有趣的資料結構，拿來處理這麼常見的需求。
在這邊分享給大家，希望可以引出更多有趣的想法。
blog 與課程更新內容，請前往新站位置：http://tdd.best/
