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

先介紹下紅黑樹、B樹、B+樹。

紅黑樹

個人認為紅黑樹其實蠻難的，畢竟HashMap在JDK1。8中才使用了紅黑樹。

紅黑樹的特性：

節點存在邏輯上的顏色：黑色和紅色，根節點為黑色，

葉子節點為黑色的空節點，紅色節點下的子節點一定為黑色節點。

從根節點到葉子節點所有的路徑上存在相同數目的黑色節點。

紅黑樹的這些特性導致紅黑樹的平衡性，從根節點到葉子節點的最長路徑不會超過最短路徑的2倍。

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

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+樹的非葉子節點儲存的資料指標是聚集索引的主鍵。