InnoDB 為什么使用 B+樹實現索引？說到這個話題，就需要先聊一聊 InnoDB 的索引類型有哪些？

InnoDB 中的索引類型

InnoDB 存儲引擎支持兩種常見的索引數據結構：B+樹索引和哈希索引，其中 B+樹索引是目前關系型數據庫系統中最為常見、最為高效的索引之一。

數據庫中的 B+樹索引可分為聚簇索引和非聚簇索引。聚簇索引按照每張表的主鍵構建一個 B+樹，其葉子節點記錄著表中每行記錄的所有值。只需訪問葉子節點即可獲取整行記錄的信息。非聚簇索引的葉子節點中并不包含完整的行記錄信息，而僅包含索引值和對應的主鍵值。

根據索引的唯一性，索引可分為唯一索引和普通索引。唯一索引要求索引列的值必須唯一，不可重復。

此外，在 MySQL 5.6 版本中引入了全文索引，在 5.7 版本及以后，通過使用 ngram 插件開始支持中文全文搜索。

B+樹的特點

首先來看一下 B+樹的特點：

1. B+樹是一棵平衡樹，每個葉子節點到根節點的路徑長度相同，從而提高了查找效率；
2. 所有關鍵字都存儲在 B+樹的葉子節點上，因此進行范圍查詢時只需遍歷一次葉子節點即可；
3. 葉子節點按照關鍵字大小順序存放，因此能夠快速支持按關鍵字大小進行排序；
4. 非葉子節點不存儲實際數據，這使得可以存儲更多的索引數據；
5. 非葉子節點使用指針連接子節點，從而能夠迅速支持范圍查詢和倒序查詢；
6. 葉子節點之間通過雙向鏈表連接，便于進行范圍查詢。

圖片

使用 B+樹實現索引具有以下幾個優點：

1. 支持范圍查詢：B+樹在執行范圍查找時，只需從根節點遍歷至葉子節點，因為數據存儲在葉子節點上，并且葉子節點之間有指針連接，便于進行范圍查找。
2. 支持排序：B+樹的葉子節點按關鍵字順序存儲，能夠快速支持排序操作，提升排序效率。
3. 存儲更多的索引數據：由于非葉子節點僅存儲索引關鍵字而不存儲實際數據，可容納更多索引數據。
4. 減少 IO 操作：B+樹的葉子節點大小固定，一般設置為一頁大小，使得節點分裂和合并時的 IO 操作較少，只需讀取和寫入一頁。
5. 利用磁盤預讀：節點大小固定有利于利用磁盤預讀特性，一次性讀取多個節點到內存中，減少 IO 操作次數，提高查詢效率。
6. 優化緩存利用：B+樹的非葉子節點僅存儲指向子節點的指針，不存儲數據，可使緩存容納更多索引數據，提高緩存命中率，加速查詢速度。

為什么不用紅黑樹或者 B 樹？

因為 B+樹的特點是只有葉子節點存儲數據，而非葉子節點不存儲數據，并且節點大小固定，葉子節點之間通過雙向鏈表鏈接，所以，使用 B+樹實現索引具有諸多優勢，比如支持范圍查詢、有利于磁盤預讀、優化排序等等。而這些是紅黑樹和 B 樹無法實現的。

B+樹索引和 Hash 索引有什么區別？

B+樹索引和哈希索引是常見的數據庫索引結構，它們之間存在以下幾個主要區別：

B+樹索引將索引列的值按大小排序后存儲，因此適合范圍查找和排序操作；而哈希索引則通過哈希函數計算索引列的值，得到一個桶的編號，然后將桶內記錄保存在鏈表或樹結構中。因此，哈希索引適合等值查詢，但不適合范圍查詢和排序操作。

在插入和刪除數據時，B+樹索引需要調整索引結構，可能涉及頁分裂和頁合并等操作，因此維護成本較高；而哈希索引只需計算哈希值并操作鏈表中的記錄，維護成本相對較低。

B+樹索引在磁盤上有序存儲，可利用磁盤預讀提高區間查詢效率；而哈希索引在磁盤上無序存儲，可能需要隨機訪問磁盤，導致查詢效率下降。

由于 B+樹索引在節點中存儲多個鍵值對，能充分利用磁盤塊空間，提高空間利用率；而哈希索引需要額外存儲哈希值和指針，空間利用率相對較低。