[[目錄]]
1. 表索引#
表索引是表屬性的副本，主要用於加速。
表索引主要權衡兩個方面的因素
- 維護的代價
- 加速的效果
2. B+ 樹#
B+ 樹是一種自平衡的數據結構，查找插入等操作的時間複雜度通常在 $O (\log {n})$ ，並且這種數據結構針對比較大的數據塊做了優化。
B+ 樹是一個 M- 叉搜索樹有以下的特徵：
- 完美平衡（所有的葉子節點的層數都相同）
- 除了根節點外，左右節點的有
M/2-1 <= #keys <= M-1 - 所有有
k個 key 的節點都有k+1個非空子節點。
在 B+ 樹中，葉子節點是存儲最後我們需要的 key 的地方。因此我們如果要依據葉子節點去尋找最終的 val 的話，有以下兩種方法。
- 將 val 存在的地方用一個指針記錄下地址
- 直接存儲在葉子節點中。
B-Tree VS. B+Tree#
B - 樹和 B + 樹最主要區別是，B - 樹的 key 也存在於非葉子節點。因此 B - 樹在利用存儲空間上無疑相較於 B + 樹更為優秀。
因此可能存在以下的一些問題。
- B - 樹在遍歷的時候不得不在各個節點中來回跳躍。而 B + 樹則可以直接掃描。
- B - 樹，在使用將 val 存儲在節點中的方法可能會導致查詢過慢。
可視化#
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
插入#
找到一個葉子節點進行插入。按照大小插入。
如果該節點有足夠的空間容納，那麼則插入停止。如果沒有足夠的空間那麼有以下兩步操作。
- 將該節點以中間值對半分為兩個節點。
- 將該中間值向上推給父節點。若沒有父節點，則創造父節點。然後對父節點執行同樣的操作。
刪除#
找到葉子節點進行刪除。
如果該葉子節點刪除了該 key 之後至少有一半的容量，那麼刪除停止。
如果該葉子節點只有 M/2-1 個 key 了，那麼有以下兩種策略
- 嘗試將隔壁節點的值拿過來。
- 如果嘗試失敗那麼則嘗試將兩個節點合併。
查詢條件#
具有與樹結構查詢的優缺點。
重複的 keys#
有兩種方式來解決重複的 keys
- 在所有的 key 後面加入 recorid ID 來確保每個 key 都是獨一無二的。
- 使用一個可以溢出的節點來保存這些重複的信息。
聚集索引#
表通常依照 primary key 進行索引。
不過有一些數據庫採用聚集索引，會為表加上一個隱藏的 primary key。別的數據庫通常無法使用這個索引
3. B+ 樹設計選擇#
節點大小#
通常是存儲設備越慢，採用的節點大小越大。
- HDD: ~1MB
- SSD: ~10KB
- In-Memory: ~512B
合併閾值#
一些 DBMS 不會總是合併那些 half full 狀態的節點。
因為，如果延遲合併操作的話，那麼可能會減少重新平衡的開銷。
維持一些比較小的節點並且週期性的重構樹可能會更好。
可變長 keys#
- 採用指針的方法，即在 B + 樹中僅僅存儲指向值的指針。
- 採用可變長的節點。
- 將所有的值強制以一個固定大小存儲在 B+ 樹中。
- 採用 map 的形式來進行存儲
節點內搜索#
- 線性
- 線性的掃描節點
- 可以採用 SIMD 的技術增加掃描的數據量。
- 二分
採用二分法進行查找 - 插值
通過值，從而知道位置在哪。
4. 優化#
前綴壓縮#
通過提取出相同前綴的方式來進行壓縮。
重複消除#
在 index 不一定都是獨一無二的所有的值中，可以通過將這些值合併為一個 key 。
後綴截斷#
這種方式是通過在節點中選出可以進行區分比較的小的前綴長度，從而達到查找的目的。
指針替換#
將 B+ 樹中的 page id 固定在 buffer pool 中，可以避免重複的讀 disk 進而加快速度。然後將 page id 的指針替換為在 memory 中的真實的值，這樣就可以繞過 buffer pool 的轉換，進行直接訪問。
批量插入#
重建一個 b+ 樹的方法最快的方法是從底層向上建樹