Trees Indexes
上一節我們介紹了 Hash Tables,由於這種資料結構是無序的,且無法支持範圍查詢,因此我們需要一種有序的資料結構來支持範圍查詢。
2020 以前的課似乎會介紹更多的資料結構 (skip list、radix tree ...),但 2020 以後的課程就只有介紹 B+ Tree。
B-Tree
B-Tree Family
B-Tree 中的 B 通常代表 Balanced,而 B-Tree 的變種有很多,例如 :
- B-Tree
- B+Tree
- B* Tree
- Tree
其中最常見的是 B+Tree,各個 DBMS 也會使用不同的 B-Tree 家族的變種。
B+Tree
B+Tree 是一種 self-balancing tree,並且在 search、insert、delete 跟 sequential access 時的時間複雜度都是 ,是一種 BST 的變種。
M-way B+Tree 的特點有 :
- 每個節點最多儲存 M 個 key,並且有 M+1 個 children
- 每個 leaf node 的深度都相同 (perfectly balanced)
- 除了 root node 以外,每個節點都至少要有 個 key (半滿)
- leaf node 會透過 doubly linked list 連接,提高 sequential access 的效率
在每個 node 中都包含了一個經過排序的 key / value pair 陣列, 其中 key 就是 index 的值,而 value 則會根據是 inner node 或 leaf node 而有所不同。
其中 inner node 的 value 就是指向下一個節點的 pointer, 而 leaf node 的 value 則有兩種不同的實作方式
- Record IDs : 直接儲存指向 tuple 的指標
- Tuple Data : 直接儲存 tuple 的資料,但對於 secondary index 來說,這樣會造成重複儲存,因此要在 leaf node 儲存 Record IDs
B+Tree Operations
有關 B+Tree 的操作,可以參考 這個網站。
B+Tree vs B-Tree
B-Tree 不會只把資料儲存在 leaf node 中,而是會把資料儲存在每個節點中,導致每個 node 能存放的資料量較少,因此 B-Tree 的高度會比 B+Tree 高, 導致 B-Tree 的查詢效率較低,並且 B-Tree 因為不會在 left node 中有 doubly linked list,因此 sequential access 的效率也較低。
Selection Conditions
B+tree 只需要 query 有任意一個 key 就可以使用 index,不需要像 hash index 需要全部的 key 才能使用。
舉例來說,如果我們有 a、b、c 三個 index,我們在搜尋 a = 1 AND b = 2
時,就可以使用到 a 和 b 的 index。
Duplicate Keys
有兩種常見的方式來處理 duplicate keys :
- Append Record ID : 把唯一的 Record ID 附加在 key 後面
- Overflow Leaf Nodes : 允許節點溢出
Clustered Indexes
有些 DBMS 會規定 table 的儲存方式,通常會按照 primary key 來排序,如果沒有就會自動生成一個來排序。
Index Scan Page Sorting
由於直接從 unclustered index 中取得資料非常沒效率,因此 DBMS 會把需要的 page id 全部取出來做排序。
B+Tree Design Choices
Node Size
通常來說, disk 的讀取速度越慢,node size 就會越大
- HDD : 1MB
- SSD : 10KB
- In-Memory : 512B
Merge Threshold
由於 B+Tree 的 merge 開銷很大,所以有些 DBMS 並不會在每次插入時都 merge,而是會由其他的 process 來定期處理 merge。也因此 postgres 會叫 B+Tree 為 nbtree (non-balanced tree)。
Variable Length Keys
處理不定長度的 key 有以下幾種方式 :
- Pointers : 儲存一個指標指向 tuple
- Variable-Length Nodes : 允許可變長度,但需要精細的記憶體管理
- Padding : 將 key 填滿到固定長度
- Key Map / Indirection : 維護 key / value 的對應表
Intra-Node Search
在節點內搜索有三種方式 :
- Linear : 線性搜索,可以用 SIMD 來加速
- Binary : 二分搜索
- Interpolation : 用 key 的分布來估計位置
Optimizations
Prefix
同一個 node 常常有相同的 key,我們可以透過 prefix 來減少儲存空間。
Deduplication
可以將重複的 key 合併。
Suffix
在 inner node 中, key 只是用來決定要往左還是往右走,因此只需要儲存可供辨識的部分。
如 key 是 abcdefgh,我們可以只儲存 abc。
Pointer Swizzing
我們需要透過 page id 來找到其他的 page,這樣就必須先訪問 page table,但如果這個 page 已經固定在 buffer pool 中,我們就使用原始指標而不需要再訪問 page table。
Bulk Insert
最快建立 B+Tree 的方法是將 key 先排好序,再從下往上建立 B+Tree,如果有大量的插入操作時可以這麼做。
Write-Optimized B+ Tree
因為分裂和合併節點在 B+Tree 中非常耗時,因此有些 B-Tree 的變體會延遲這些行為,如 -Tree,這種樹會將變動儲存在 log 檔並慢慢往下傳遞。