Mysql索引為什麼要用B+樹，而不用紅黑樹

凱騰凱

當然紅黑樹為了維持自身的平衡性，會存在變色和旋轉。

B-樹

B樹是利用磁盤塊的特性來構建的樹結構，每個磁盤塊一個節點，每個節點包含很多的關鍵字，數的關鍵字增多後數的層級就會比二叉樹更少，減少了查詢的次數和複雜度。其次還利用了磁盤預讀的特性，把每個節點作為一個頁（磁盤頁大小為4K），每個節點一次I/O操作就可以完全載入。

但是由於每個節點關鍵字還和關鍵字記錄指針綁定到一起，導致一個節點不能夠存儲過多的關鍵字，所以B+樹就出現了。

B+樹

B+樹每個非葉子節點存儲關鍵字和父節點指針，關鍵字記錄的指針存儲在葉子節點，並且葉子節點有序。這樣每個非葉子節點能夠存儲更多的關鍵字，樹的層級也就下降了，查詢數據的速率變快。

為什麼要選用B+樹，而不是紅黑樹呢？

B+樹只有葉節點存放數據，其餘節點用來索引，而B-樹是每個索引節點都會有Data域。所以從Mysql（Inoodb）的角度來看，B+樹是用來充當索引的，一般來說索引非常大，尤其是關系型數據庫這種數據量大的索引能達到億級別，所以為了減少內存的占用，索引也會被存儲在磁盤上。

那麼Mysql如何衡量查詢效率呢？– 磁盤IO次數。
B-樹/B+樹 的特點就是每層節點數目非常多，層數很少，目的就是為了減少磁盤IO次數，但是B-樹的每個節點都有data域（指針），這無疑增大了節點大小，說白了增加了磁盤IO次數（磁盤IO一次讀出的數據量大小是固定的，單個數據變大，每次讀出的就少，IO次數增多，一次IO多耗時），而B+樹除了葉子節點其它節點並不存儲數據，節點小，磁盤IO次數就少。這是優點之一。

另一個優點是： B+樹所有的Data域在葉子節點，一般來說都會進行一個優化，就是將所有的葉子節點用指針串起來。這樣遍曆葉子節點就能獲得全部數據，這樣就能進行區間訪問啦。在數據庫中基於範圍的查詢是非常de頻繁的，而B樹不支持這樣的遍曆操作

紅黑樹基本都是存儲在內存中才會使用的數據結構。在大規模數據存儲的時候，紅黑樹往往出現由於樹的深度過大而造成磁盤IO讀寫過於頻繁，進而導致效率低下的情況。磁盤IO代價主要花費在查找所需的柱面上，樹的深度過大會造成磁盤IO頻繁讀寫。根據磁盤查找存取的次數往往由樹的高度所決定，所以，只要我們通過某種較好的樹結構減少樹的結構盡量減少樹的高度，B樹可以有多個子女，從幾十到上千，可以降低樹的高度。

Mysql的聚集索引

在MySQL的Innodb存儲引擎下主鍵索引稱為聚集索引，列索引稱為輔助索引，二級索引的B+樹的非葉子節點存儲的數據指針是聚集索引的主鍵。

如上圖中，id主鍵索引的葉子節點的數據區保存的就是真實的數據，在通過索引進行檢索的時候，命中葉子節點，就可以直接從葉子節點中取出行數據。主鍵索引的葉子節點保存的是真正的數據。而輔助索引葉子節點的數據區保存的是主鍵索引關鍵字的值。

假如要查詢name = C 的數據，其搜索過程如下：先在輔助索引中通過C查詢最後找到主鍵id = 9。然後在主鍵索引中搜索id為9的數據，最終在主鍵索引的葉子節點中獲取到真正的數據。所以通過輔助索引進行檢索，需要檢索兩次索引。

為什麼這樣設計呢？

原因就是：如果和MyISAM一樣在主鍵索引和輔助索引的葉子節點中都存放數據行指針，一旦數據發生遷移，則需要去重新組織維護所有的索引。

我是凱騰凱，互聯網浪潮下一枚苟且偷生的程序仔