CMU15-445 數據庫系統播客：B+樹索引 - 結構與優化
B+ 樹的核心特性
B+ 樹是一種 M-way 搜索樹，它通過一系列精巧的設計，實現了在對數時間復雜度 內完成查找、范圍掃描、插入和刪除操作。其關鍵特性如下：
- 高度平衡與多路設計 ：B+ 樹是完美平衡的，所有葉子節點都處于相同的深度。這保證了查詢性能的穩定性。同時，它是一個“多路”樹，意味著每個內部節點可以擁有多個子節點（最多 M 個），這使得樹的高度非常低，從而顯著減少了從磁盤讀取數據塊（Node）的次數，這對于磁盤I/O是主要瓶頸的系統至關重要。
- 有序性與范圍查詢 ：B+ 樹內部的所有節點中的鍵都保持有序存儲。它的葉子節點之間通過指針串聯，形成一個有序鏈表。這一特性使得 B+ 樹不僅擅長單點查找，還極為高效地支持范圍查詢。當需要查找一個范圍的數據時，DBMS 只需定位到范圍的起始葉子節點，然后通過葉子節點間的指針順序向后遍歷即可。
- 節點功能分離
- 內部節點 ：僅存儲“路由”信息，即用于導向的鍵（Keys）和指向下一層節點的指針（Pointers）。它們不存儲具體的數據值，唯一的任務就是“指路”。
- 葉子節點 ：存儲了索引的鍵以及對應的值。這個“值”通常有兩種實現方式。
記錄標識 (Record IDs) ：值是指向表中實際數據行物理位置的指針。這是 PostgreSQL 等數據庫采用的方式，有時被稱為“非聚簇索引”。
元組數據 (Tuple Data) ：值直接就是數據行的完整內容。MySQL 的 InnoDB 存儲引擎的主鍵索引就是這樣實現的，稱為“聚簇索引”。在這種模式下，二級索引的葉子節點存儲的則是主鍵的值，因此通過二級索引查找數據時，需要先找到主鍵，再通過主鍵索引找到完整數據，這個過程即為“回表”。
插入與刪除操作
B+ 樹的自平衡特性是通過其插入和刪除算法實現的。
插入
- 首先，查找到應該插入新鍵的葉子節點 L。
- 將新條目按序插入 L。
- 如果 L 還有空間，操作完成。如果 L 已滿，則需要進行 分裂 ：將 L 分裂成兩個節點 L 和 L2，并將原節點中的一半條目移動到新節點 L2 中。同時，將 L2 的第一個鍵（即中間鍵）復制并提升（Copy Up）到父節點中，以作為指向 L2 的路標。
- 如果父節點也因此變滿，分裂過程會向上傳遞，最壞情況下可能一直傳遞到根節點，導致樹的高度增加一層。
刪除
- 首先，查找到包含該鍵的葉子節點 L 并移除條目。
- 如果 L 在刪除后所含的鍵數量仍然滿足要求（通常是至少半滿），則操作完成。
- 如果 L 的鍵數量低于閾值，系統會嘗試從相鄰的兄弟節點“借”一個鍵來進行 重新分配 (Redistribution) 。
- 如果兄弟節點也沒有富余的鍵可借，則會將 L 與其兄弟節點進行 合并 (Merge) 。 合并后，父節點中指向被合并節點的鍵也需要被刪除，這個過程同樣可能向上傳遞。
B+ 樹的設計考量
1. 節點大小 (Node Size)
節點大小是一個關鍵的設計決策。傳統上，對于機械硬盤（HDD），節點大小傾向于設置得更大（如幾 MB）。這是因為 HDD 的尋道時間很長，隨機讀寫性能差。通過一次讀取一個大的數據塊，可以將這次昂貴的 I/O 成本分攤到更多的鍵值對上，從而提高效率。
而對于固態硬盤（SSD），其隨機讀寫性能遠超 HDD。因此，節點大小的設計有了不同的考量。雖然一次讀取更大塊仍然有優勢，但過大的節點也存在弊端。較小的節點（如幾十或幾百 KB）有以下好處：
- 緩存效率更高 ：更小的節點意味著在有限的內存（Buffer Pool）中可以緩存更多的節點，從而提高緩存命中率。
- 更新成本更低 ：當一個節點需要被修改（分裂或合并）時，需要加鎖并寫入磁盤。節點越小，鎖定的粒度越小，寫入的數據量也越少，這在高并發寫入場景下可以減少爭用并提升性能。
- 減少內部碎片 ：對于變長鍵，小節點能更靈活地適應，減少節點內的空間浪費。
2. 變長鍵的處理
當索引的鍵是變長的字符串時，直接存儲會使節點內布局變得復雜。最常見的處理方法是采用類似“頁槽”（Slotted Page）的機制，也稱為 鍵位圖 (Key Map) 。節點內部會維護一個指針數組，每個指針指向一個鍵值對的實際存儲位置。這種方式可以高效地管理節點內的可變空間。
3. 非唯一索引
如果索引列的值不唯一，B+ 樹有兩種處理方式：
- 存儲重復鍵 ：直接在葉子節點中多次存儲相同的鍵。
- 值列表 ：每個鍵只存儲一次，但其對應的值是一個包含所有重復條目記錄ID的鏈表或集合。
4. 節點內查找策略
在一個節點內部快速定位鍵也至關重要。常見方法包括：
- 線性掃描 ：從頭到尾依次比較，簡單但對有序性沒有要求。
- 二分查找 ：要求節點內鍵有序，通過在中間點不斷分割查找范圍來快速定位。
- 插值查找 ：基于節點內鍵的分布來預測目標鍵可能的位置，然后從該位置開始線性掃描，也要求鍵有序。
B+ 樹的優化技術
為了進一步提升性能和空間效率，現代 B+ 樹實現中還包含了很多高級優化：
- 前綴壓縮 (Prefix Compression) ：在葉子節點中，相鄰的鍵通常有相同的前綴。通過只存儲它們的共同前綴一次，然后為每個鍵存儲其獨特的后綴，可以顯著節省存儲空間。
- 后綴截斷 (Suffix Truncation) ：內部節點的鍵只用于“指路”，因此不需要存儲完整的鍵。只需存儲能夠區分左右子樹的最短前綴即可。例如，如果要區分 "Apple" 和 "Apply"，在內部節點中可能只需要存儲 "Appli" 就足夠了。
- 批量加載 (Bulk Loading) ：當需要為一張已有大量數據的大表創建新索引時，逐條插入的效率很低，因為會觸發大量的節點分裂和重組。最高效的方式是先將所有鍵進行排序，然后從底層開始自底向上地構建 B+ 樹。這樣可以一次性確定每層節點的布局，完全避免了分裂和合并操作，速度快得多。
- 指針旋轉 (Pointer Swizzling) ：這是一個更高級的內存管理技術，可以簡單理解為：當一個磁盤上的節點被讀入內存時，其內部存儲的磁盤地址（Disk Pointers）會被轉換成內存地址（Memory Pointers）。這樣，在內存中對樹進行遍歷時，就可以直接通過內存地址訪問子節點，避免了將磁盤地址轉換回內存地址的開銷，從而加快速度。當節點被寫回磁盤時，內存指針又會被“反向旋轉”回磁盤地址。
通過這些精心設計和優化的特性，B+ 樹成為了支撐現代高性能數據庫不可或缺的基石。
