《MySQL實戰(zhàn)45講》學習筆記3——InnoDB為什么采用B+樹結(jié)構實現(xiàn)索引

索引的作用是提高查詢效率，其實現(xiàn)方式有很多種，常見的索引模型有哈希表、有序列表、搜索樹等。

哈希表

* 一種以key-value鍵值對的方式存儲數(shù)據(jù)的結(jié)構，通過指定的key可以找到對應的value。
*
哈希把值放在數(shù)組里，用一個哈希函數(shù)把key換算成一個確定位置，然后把value放在數(shù)組的這個位置。但是，多個key值經(jīng)過哈希函數(shù)的換算，可能會出現(xiàn)同一個值，即哈希沖突，常見的解決辦法是鏈地址法，即將所有的相同Hash值的key放在一個鏈表中，這樣，無論有多少個沖突，都只是在當前位置給單鏈表增加節(jié)點。
* 適用于只有等值查詢的場景，區(qū)間查詢會很慢。
有序列表

* 支持等值查詢和范圍查詢，但是更新數(shù)據(jù)的成本比較高。
* 適用于靜態(tài)存儲索引，比如保存的是2017年某個城市人口信息這類不會修改的數(shù)據(jù)。
樹

1.二叉樹：

* 每個節(jié)點的左兒子小于父節(jié)點，父節(jié)點小于右兒子。
* 查找、更新某個節(jié)點的時間復雜度都是O(log(N))，搜索效率最高。
2.B樹（多叉樹）：

根節(jié)點至少有兩個子節(jié)點，每個節(jié)點的子節(jié)點間，其大小都是從左到右遞增。

3.B+樹：

*
B+樹的葉子節(jié)點保存了父節(jié)點的所有鍵值和鍵值對應的數(shù)據(jù)，每個葉子節(jié)點的鍵值從小到大鏈接，但非葉子節(jié)點不保存鍵值對應的數(shù)據(jù)，這樣使得B+樹每個節(jié)點所能保存的鍵值大大增加；
* 由于B+樹的非葉子節(jié)點只進行數(shù)據(jù)索引，不會存實際的鍵值對應的數(shù)據(jù)，所有的數(shù)據(jù)必須到葉子節(jié)點才能獲取到，所以每次數(shù)據(jù)查詢的次數(shù)都一樣。
因為索引不止存在內(nèi)存中，還要寫在磁盤上，為了盡量少地讀寫磁盤，減少IO次數(shù)，所以盡管二叉樹的效率很高，大多數(shù)數(shù)據(jù)庫不會選擇二叉樹。

可以想象一下一棵 100 萬節(jié)點的平衡二叉樹，樹高 20。一次查詢可能需要訪問 20 個數(shù)據(jù)塊。在機械硬盤時代，從磁盤隨機讀一個數(shù)據(jù)塊需要 10 ms
左右的尋址時間。也就是說，對于一個 100 萬行的表，如果使用二叉樹來存儲，單獨訪問一個行可能需要 20 個 10 ms 的時間。

InnoDB使用B+樹索引模型，所有數(shù)據(jù)都存儲在B+樹中，每一個索引對應一棵B+樹。

以 InnoDB 的一個整數(shù)字段索引為例，這個 N 差不多是 1200。這棵樹高是 4 的時候，就可以存 1200 的 3 次方個值，這已經(jīng) 17
億了。考慮到樹根的數(shù)據(jù)塊總是在內(nèi)存中的，一個 10 億行的表上一個整數(shù)字段的索引，查找一個值最多只需要訪問 3
次磁盤。其實，樹的第二層也有很大概率在內(nèi)存中，那么訪問磁盤的平均次數(shù)就更少了。

結(jié)論：InnoDB采用B+樹結(jié)構，是因為B+樹能夠很好地配合磁盤的讀寫特性，減少單次查詢的磁盤訪問次數(shù)，降低IO、提升性能。

• ? 上一篇： 5W1H(六何分析法)全景洞察大數(shù)據(jù)
• ? 下一篇： 一文教會你如何寫復雜業(yè)務代碼