0.參考資料
程序猿DD：《深入理解 B 樹：現代數據庫背後的數據結構》 https://www.bilibili.com/video/BV1FH4y1G7V3?spm_id_from=333.788.videopod.sections&vd_source=b1a84eb14c28200ba91b487ad665c3f4 藍不過海呀：《數據結構合集 - B+樹》 https://www.bilibili.com/video/BV1bs421u7pY/?spm_id_from=333.337.search-card.all.click&vd_source=b1a84eb14c28200ba91b487ad665c3f4
1.B樹是解決什麼問題的
B樹中的“B”最普遍的理解是Balanced，彰顯了其作為平衡樹的本質。B樹是一種多路平衡搜索樹（m-way balanced search tree），與二叉搜索樹不同，它的一個節點可以擁有多於兩個的key和多於兩個的子樹。這使它具備了一個關鍵優勢：非常“矮胖”。 當數據量巨大，無法全部裝入內存時，必須將大部分數據存放在磁盤上。磁盤讀寫（特別是尋道操作）的速度遠慢於內存操作，因此減少磁盤I/O次數就成了提升性能的關鍵。B樹通過以下設計完美應對了這一挑戰： 降低樹的高度：通過增加每個節點的分支數量（即增大階數m），B樹可以顯著降低自身的高度。例如，一個包含百萬數據的B樹，可能只需要2-3層就能覆蓋，這意味着查找一條記錄最多隻需要2-3次磁盤I/O。 節點大小與磁盤塊匹配：B樹的節點大小通常被設計為與磁盤塊的大小相匹配。這樣，每次讀取一個節點（一次磁盤I/O）就能加載大量相關信息，充分利用了磁盤的塊讀取特性，極大地提高了效率。
2.B+樹相對於B樹有哪些不同
B+樹是在B樹基礎上為數據庫、文件系統等需要高效處理大規模數據的場景量身定製的數據結構。它通過一系列精巧的設計，顯著提升了綜合性能，特別是範圍查詢和磁盤I/O效率。 下表清晰地對比了B樹與B+樹的核心差異。
| 特性 | B樹 | B+樹 |
|---|---|---|
| 數據存儲位置 | 所有節點（包括非葉子節點）都可能存儲數據 | 僅葉子節點存儲數據，非葉子節點只存儲鍵（索引） |
| 葉子節點結構 | 葉子節點之間是獨立的 | 所有葉子節點通過指針串聯成有序雙向鏈表 |
| 非葉子節點結構 | 數據可以存在非葉子節點，同一個數據不能同時存在於非葉子節點和葉子節點 | 非葉子節點元素為子樹元素最大值，即同一個元素可能同時存在於多級非葉子節點和葉子節點 |
| 搜索性能 | 搜索可能在非葉子節點命中，效率不穩定 | 任何搜索都必須走到葉子節點，效率穩定 |
| 範圍查詢與遍歷 | 效率低，需要進行復雜的中序遍歷 | 效率極高，通過葉子節點鏈表順序遍歷即可 |
| 空間利用率 | 每個節點都存儲數據，空間利用率相對較低 | 非葉子節點更“瘦”，能容納更多鍵，樹更矮，空間利用率更高 |
3.B+樹的改進解決了哪些核心問題？
B+樹的每一項改進都直指數據庫和文件系統在處理海量數據時的核心瓶頸。 （1）更優的磁盤I/O性能 數據庫索引通常存儲在磁盤上，磁盤I/O（讀取磁盤數據）是主要性能瓶頸。B+樹非葉子節點不存儲實際數據，意味着單個節點可以容納更多的鍵（索引），從而大大增加了樹的“階數”（m值）。這直接導致整棵樹的高度更低，因為節點能指向更多的子節點。對於億萬級的數據，B+樹可能只需要3-4層，這意味着查找任何一條記錄最多隻需要3-4次磁盤I/O，效率顯著提升。
非葉子節點存放索引，也是按照磁盤塊大小來設計的，因為只存放索引，所以一個磁盤塊能存放更多的索引（索引佔用空間比數據要小）
（2）革命性的範圍查詢能力 這是B+樹相比B樹的“殺手鐗”改進。由於所有葉子節點被串聯成一個有序鏈表，進行範圍查詢（如查找價格在100到200元的所有商品）時，系統只需定位到範圍的下界，然後順着鏈表掃描即可，非常高效。而在B樹中，進行同樣的操作需要對樹進行復雜的中序遍歷，會產生大量隨機的磁盤I/O，性能差距巨大。 （3）更穩定的查詢效率和更高的空間利用率 在B+樹中，每一次查詢的路徑長度都是相同的（從根到葉），這使得查詢時間非常穩定，便於系統進行性能優化。同時，因為非葉子節點只存索引，結構更緊湊，在內存有限的情況下，可以緩存更多的非葉子節點，進一步減少磁盤I/O。 總而言之，B+樹並非要替代B樹的所有功能，而是專門為解決磁盤讀寫速度遠慢於內存速度這一核心矛盾而生的。它通過 “犧牲”非葉子節點存儲數據的能力，換來了更矮的樹、更少的I/O、更強的範圍查詢和順序處理能力。
