T樹
在電腦科學中，T-樹是一種二元樹資料結構，被主記憶體資料庫（如 Datablitz、eXtremeDB、MySQL Cluster、Oracle TimesTen 及 MobileLite）所使用。
T-樹是一種平衡索引樹資料結構，專為索引與實際資料完全儲存於記憶體中的情況進行了最佳化，正如B-樹是為儲存於硬碟等區塊導向的次級儲存裝置上而最佳化的索引結構。T-樹試圖獲取如AVL樹等記憶體內樹狀結構的效能優勢，同時避免它們常見的巨大儲存空間開銷。
T-樹不在索引樹節點本身保留已索引資料欄位的副本。而是利用了實際資料與索引一同存放在主記憶體中的事實，因此它們只包含指向實際資料欄位的指標。
T-樹中的「T」指的是最初描述此類索引的論文中，節點資料結構的形狀。
節點結構
一個T-樹節點通常包含指向父節點、左子節點和右子節點的指標、一個有序的資料指標陣列，以及一些額外的控制資料。擁有兩個子樹的節點稱為內部節點，沒有子樹的節點稱為葉節點，而只有一個子樹的節點則稱為半葉節點。如果一個值介於某節點當前的最小值和最大值之間（包含兩者），則該節點被稱為此值的邊界節點。
對於每個內部節點，都存在包含其最小資料值的前驅（稱為最大下界）的葉節點或半葉節點，以及包含其最大資料值的後繼（稱為最小上界）的葉節點或半葉節點。葉節點和半葉節點可以包含任意數量的資料元素，從一個到資料陣列的最大容量。內部節點則將其元素數量維持在預先定義的最小和最大數量之間。
演算法
搜尋
- 搜尋從根節點開始
- 如果當前節點是搜尋值的邊界節點，則搜尋其資料陣列。若在資料陣列中未找到該值，則搜尋失敗。
- 如果搜尋值小於當前節點的最小值，則在其左子樹中繼續搜尋。若沒有左子樹，則搜尋失敗。
- 如果搜尋值大於當前節點的最大值，則在其右子樹中繼續搜尋。若沒有右子樹，則搜尋失敗。
插入
- 為新值搜尋一個邊界節點。若存在此類節點，則：
- 檢查其資料陣列中是否還有空間，若有，則插入新值並完成操作。
- 若無可用空間，則從節點的資料陣列中移除最小值，然後插入新值。接著，移至保有該新值插入節點之最大下界的節點。如果被移除的最小值仍能放入該節點，則將其添加為該節點的新最大值，否則為此節點創建一個新的右子節點。
- 如果找不到邊界節點，則將該值插入到最後搜尋的節點中（如果仍有空間）。在這種情況下，新值將成為新的最小值或最大值。如果該值已無法放入，則創建一個新的左子樹或右子樹。
如果新增了一個節點，樹可能需要如下所述進行重新平衡。
刪除
- 搜尋待刪除值的邊界節點。如果找不到邊界節點，則完成操作。
- 如果邊界節點不包含該值，則完成操作。
- 從節點的資料陣列中刪除該值。
現在我們必須按節點類型區分處理：
- 內部節點：
如果節點的資料陣列現在的元素數量少於最小數量，則將此節點的最大下界值移至其資料值中。接著，對被移除值的半葉或葉節點執行以下兩個步驟之一。
- 葉節點：
如果這是資料陣列中的唯一元素，則刪除該節點。若有需要，則重新平衡樹。
- 半葉節點：
如果該節點的資料陣列可以與其葉節點的資料陣列合併而不會溢位，則進行合併並移除該葉節點。若有需要，則重新平衡樹。
旋轉與平衡
T-樹是實作於一個底層的自我平衡二元搜尋樹之上。具體而言，Lehman和Carey的文章描述了一種像AVL樹一樣平衡的T-樹：當一個節點的子樹高度相差至少兩層時，樹就會失去平衡。這種情況可能在插入或刪除節點後發生。在插入或刪除後，會從葉節點到根節點掃描樹。如果發現不平衡，則執行一次或一對樹旋轉，這保證能平衡整棵樹。
當旋轉導致某個內部節點的項目數量少於最小數量時，會將該節點的新子節點中的項目移入該內部節點。
效能與儲存
儘管T-樹因其效能優勢曾被廣泛用於主記憶體資料庫，但近期對於超大型主記憶體資料庫的趨勢更強調配置成本。隨著現代NOSQL資料庫系統通常儲存數兆筆紀錄，僅儲存一個包含實際值的索引所需的記憶體成本就可能超過數十甚至數百TB。
參見
- 樹 (圖論)
- 樹 (集合論)
- 樹狀結構
- 指數樹
其他樹
- B-樹 (2–3樹、2–3–4樹、B+樹、B*-樹、UB-樹)
- 跳舞鏈
- Fusion tree
- k-d樹
- 八叉樹
- 四叉樹
- R-樹
- 基數樹
- Top tree
參考資料
外部連結
- Oracle TimesTen FAQ entry on index mentioning T-Trees
- Oracle Whitepaper: Oracle TimesTen Products and Technologies
- DataBlitz presentation mentioning T-Trees
- An Open-source T*-tree Library
Category:二元樹 Category:搜尋樹