Entity with self-relation when storing hierarchical data,
I will introduce how to store 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加入清單內。
以上述這個例子來說，程式實際執行過程應為

[1]加入A
[2]尋找Parent為A的資料，找到兩筆(B與F)，第一筆B
[3]加入B，尋找Parent為B的資料，找到三筆(C、D、E)，第一筆C
[4]加入C，尋找Parent為C的資料，找到0筆。
[5]第二筆D，加入D，尋找Parent為D的資料，找到0筆。
[6]第三筆E，加入E，尋找Parent為E的資料，找到0筆。
[7]第二筆F，加入F，尋找Parent為F的資料，找到0筆。結束。
清單中就有A～F的node，但是這樣的資料一旦龐大，找階層式資料的effort就會爆炸性的擴大。
怎麼解決這樣的問題？我們這邊要使用的是透過interval tree(或稱為range tree)

我們先來看一下圖解：


我們給每個node兩個屬性，分別是下限與上限，下限上限屬性的規則如上圖所示，
有點類似畫圈圈的方式，把整個tree給圈起來。

當資料給定之後，DB應該會像上圖的表格一樣。

接著神奇的事情就這麼發生了，當我們要選定任意一個Node X底下的所有node集合，請跟著我這麼做：

[1]找到X的下限、上限
[2]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，
[1]找到X的下限
[2]Y的下限為X下限+1，Y的上限為X下限+2
[3]Table上下限>X.下限的資料，上下限資料都要+2
以上，是透過interval tree來篩選階層式資料的方式，
這只是最陽春的描述，table還可以搭配原本的方式來達到其他效果，例如paper上的圖

結論
沒想到上班之後還能遇到這麼有趣的資料結構，拿來處理這麼常見的需求。
在這邊分享給大家，希望可以引出更多有趣的想法。