存儲引擎
存儲引擎是數據庫管理系統（DBMS）或鍵值存儲系統的核心組件，它定義了數據在持久化存儲介質上如何組織、存儲、檢索和管理。不同的存儲引擎針對特定負載（如讀密集型、寫密集型、混合型）和數據模型（如關系型、鍵值型、文檔型）進行優化。
目前常見的存儲引擎使用的存儲數據結構有如下幾種。
1）哈希表（Hash Table）：提供O(1)平均時間復雜度的單點查詢（精確鍵匹配）。非常適合鍵值（Key-Value）存儲，但天然不支持范圍查詢或有序遍歷（除非對整個數據集掃描）。
2）B+樹（Balance+ Tree）：為磁盤I/O優化的多路平衡搜索樹。廣泛用于關系型數據庫（如MySQL InnoDB, PostgreSQL）的索引和數據存儲。支持高效的單點查詢、范圍查詢和有序遍歷。對讀密集型和混合型負載友好。
3）LSM樹（Log-Structured Merge Tree）：專為高寫入吞吐量設計的結構。通過將隨機寫轉換為內存中的有序寫入和磁盤上的順序批量寫入來優化寫性能。廣泛應用于寫密集型的NoSQL數據庫（如Google Bigtable, Apache HBase, Cassandra, RocksDB, LevelDB）。

MySQL B+樹

MySQL的存儲引擎，主要分InnoDB和MyISAM。InnoDB是MySQL的默認引擎，InnoDB使用B+樹存儲數據。表中的數據（主鍵索引）和輔助索引最終都會使用 B+ 樹來存儲，其中前者會以 <id, row> 的方式存儲，而后者會以 <index, id> 的方式進行存儲。

為了分析 InnoDB 選擇 B+ 樹作為其索引結構的原因，可以將其與 B 樹和哈希表進行對比。隨著互聯網的快速發展，數據存儲規模已攀升至千萬甚至億級，而典型的互聯網應用場景往往是讀多寫少。例如，熱點新聞的訪問、商品列表的展示以及基于價格、地理位置等條件的智能化推薦排序，都需要高效的數據查詢和排序能力。因此，數據存儲結構需要滿足以下核心需求。
1）高效的查詢性能：尤其是在范圍查詢和排序操作上，需要具備優異的性能表現。
2）充分利用順序 I/O 和 Page Cache 機制：通過優化 I/O 性能，減少磁盤訪問的延遲。
3）支持大規模數據存儲：在保證高效查詢的同時，盡可能減少寫入操作的 I/O 開銷。

由于哈希映射關系，哈希表在查找單條數據時候，能保證O(1)的時間復雜讀。但哈希表在范圍查詢和排序遍歷時候，只能進行全表掃描并依次判斷是否滿足條件。全表掃描對數據庫的性能影響非常大。比如如下的SQL語句：

SELECT * FROM commodity WHERE price > 10 AND price < 100
SELECT * FROM commodity WHERE ORDER BY price DESC

平均時間復雜度比O(1)稍慢的是O(logn)，這類數據結構有平衡二叉樹(AVL Tree)，紅黑樹(RB Tree)、B樹(B Tree)、B+樹(B+ Tree)等。他們天然就支持排序、范圍查找操作。

平衡二叉樹在一般情況下查詢性能非常好，但平衡二叉樹單個節點只能保存一個數據，因此當覆蓋大量數據時候，平衡二叉樹的樹高度很高。這意味著當需要通過遍歷獲取存儲在硬盤上的數據時候，需要更多次的I/O操作。硬盤讀取時間遠遠超過數據在內存中比較的時間，這將導致程序大部分時間會阻塞在硬盤 I/O 上。

B樹
跟平衡二叉樹的不同是，B樹是一種多叉樹。階數m決定了B樹的節點大小和樹的高度。較大的階數可以容納更多的鍵值對，減少樹的高度和硬盤訪問次數。
B樹中每個節點都存放著索引和數據，從下圖可見，查詢索引為 50 的節點就在第一層，B樹只需一次硬盤 I/O 即可完成查找。因此B樹的查詢最好時間復雜度是 O(1)。

B+樹
B+樹是B樹的一種變種，它與B樹的區別是：
葉子節點保存了完整的索引和數據，而非葉子節點只保存索引值。所以查詢索引為 50的數據，必須要遍歷到葉子節點才能取到，因此查詢時間固定為 O(logn)。
常見的B+樹階數可以是100或更大，以適應硬盤上的大量數據。

數據查詢
B樹的范圍查詢，比如上圖要查詢“大于10小于30的數據”，需要進行4次硬盤的隨機 I/O 。范圍查詢的隨機 I/O次數不穩定和放大，也是 B 樹最大的性能問題：
1）遍歷根節點的第一個元素是25，大于 10。
2）遍歷左子節點的元素，找到第一個大于10的數據是11。
3）重新遍歷根節點，發現不包含小于30的數據。
4）遍歷載右子節點的元素，找到最后一個小于30的數據是27。
而B+樹葉子節點保存指向下一個葉子節點的指針，葉子節點之間類似于單鏈表連接起來，因此葉子節點的數據在硬盤里是順序存儲的。當讀到某個葉子節點數據時候，硬盤根據局部性原理會提前將相關的數據都讀進內存，這使得范圍查詢和排序很高效。
操作系統在讀文件時，根據Page Cache機制將數據加載到頁緩存中，頁的默認大小是4KB。由于B+樹非葉子節點都只是索引值，這就意味B+樹一次I/O，相比于B樹能讀出的索引值更多，從而減少查詢時候需要的I/O次數。
不同于操作系統，InnoDB引擎的頁大小默認是16KB，如下估算：
1）非葉子節點存放（key，pointer），假設主鍵ID為bigint類型，長度為8字節，而指針在InnoDB源碼中為6字節，一共14字節，即非葉子節點能存放 16KB/14 左右的（key，pointer）。
2）葉子節點中保存的一行記錄的數據大小為1KB，大約可以存儲16K/1K = 16記錄數。
如果B+樹高度為2，那么存放總記錄數為：根節點指針數單個葉子節點記錄行數 = 16KB/14 * 16 大約 1.8w+ 數據。
如果B+樹高度為3，那么存放總記錄數為：根節點指針數單個葉子節點記錄行數 = 16KB/14 * 16KB/14 * 16 大約2kw+數據。

數據寫入
相比于數據讀取場景，B+樹在寫密集型場景的性能并不理想。這主要原因是：B+樹在寫入（插入、刪除、更新）時，為維持樹的平衡，可能觸發節點分裂、合并。這些操作可能涉及多個磁盤頁的修改，導致隨機I/O，且需要更新Page Cache中的對應頁，使其失效。因此，在寫密集型場景下，B+樹性能不如專為寫入優化的結構。

因此B+樹也通過一些優化策略來提高寫操作的性能。比如使用寫緩沖區（Write Buffer）來緩存寫操作，然后定期將緩沖區中的數據批量刷入硬盤，將隨機I/O合并為后續的順序I/O。此外可以使用多版本并發控制機制（MVCC）來減少寫入時候的鎖競爭和提高并發性能。

未完待續

很高興與你相遇！如果你喜歡本文內容，記得關注哦！！！