B+樹做索引而不用B-樹
那麼Mysql如何衡量查詢效率呢？– 磁盤IO次數。
一般來說索引非常大，尤其是關系性資料庫這種資料量大的索引能達到億級别，是以為了減少記憶體的占用，索引也會被存儲在磁盤上。
B-樹/B+樹的特點就是每層節點數目非常多，層數很少，目的就是為了減少磁盤IO次數，但是B-樹的每個節點都有data域(指針)，這無疑增大了節點大小，說白了增加了磁盤IO次數(磁盤IO一次讀出的資料量大小是固定的，單個資料變大，每次讀出的就少，IO次數增多，一次IO多耗時)， 而B+樹除了葉子節點其它節點并不存儲資料，節點小，磁盤IO次數就少。
B+樹的優點
優點一： B+樹的磁盤讀寫代價更低：B+樹隻有葉節點存放資料，其餘節點用來索引，而B-樹是每個索引節點都會有Data域。
優點二： B+樹帶有順序通路指針：B+樹所有的Data域在葉子節點，并且所有葉子節點之間都有一個鍊指針。 這樣周遊葉子節點就能獲得全部資料，這樣就能進行區間通路啦。在資料庫中基于範圍的查詢是非常頻繁的，而B樹不支援這樣的周遊操作。
優點三：B+樹的查詢效率更加穩定：由于非葉子節點并不是最終指向檔案内容的節點，而隻是葉子節點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。而B樹因為非葉子節點也存在資料Data域，有可能在非葉子節點中就可擷取資料并傳回。
B+數帶有順序通路指針的優點
一般在資料庫系統或檔案系統中使用的B+Tree結構都在經典B+Tree的基礎上進行了優化，增加了順序通路指針。在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序通路指針的B+Tree。做這個優化的目的是為了提高區間通路的性能，例如如果要查詢key為從15到60的所有資料記錄，當找到15後，隻需順着節點和指針順序周遊就可以一次性通路到所有資料節點，極大提到了區間查詢效率。
B樹的優點
對于在内部節點的資料，可直接得到，不必根據葉子節點來定位
B+樹做索引而不用紅黑樹
AVL 樹(平衡二叉樹)和紅黑樹(二叉查找樹)基本都是存儲在記憶體中才會使用的資料結構。
在大規模資料存儲的時候，紅黑樹往往出現由于樹的深度過大而造成磁盤IO讀寫過于頻繁，進而導緻效率低下的情況。
為什麼會出現這樣的情況？
我們知道要擷取磁盤上資料，必須先通過磁盤移動臂移動到資料所在的柱面，然後找到指定盤面，接着旋轉盤面找到資料所在的磁道，最後對資料進行讀寫。磁盤IO代價主要花費在查找所需的柱面上，樹的深度過大會造成磁盤IO頻繁讀寫。根據磁盤查找存取的次數往往由樹的高度所決定，是以，隻要我們通過某種較好的樹結構減少樹的結構盡量減少樹的高度，B樹可以有多個子女，從幾十到上千，但是降低樹的高度。
資料庫設計者選擇
資料庫系統的設計者巧妙利用了磁盤預讀原理，将一個節點的大小設為等于一個頁，這樣每個節點隻需要一次I/O就可以完全載入。為了達到這個目的，在實際實作B-Tree還需要使用如下技巧：每次建立節點時，直接申請一個頁的空間，這樣就保證一個節點實體上也存儲在一個頁裡，加之計算機存儲配置設定都是按頁對齊的，就實作了一個node隻需一次I/O。
B-Tree有許多變種，其中最常見的是B+Tree，例如MySQL就普遍使用B+Tree實作其索引結構。
磁盤和記憶體選擇B樹和紅黑樹的原因
B樹優點
B+樹的高度要比紅黑樹小，有效減少了磁盤的随機通路
B+樹的資料節點互相臨近，能夠發揮磁盤順序讀取的優勢(緩存)
B+樹的資料全部存于葉子結點，而其他節點産生的浪費在經濟負擔上能夠接收，紅黑樹存儲浪費小
紅黑樹優點
紅黑樹常用于存儲記憶體中的有序資料，增删很快，B+樹常用于檔案系統和資料庫索引，因為B樹的子節點大于紅黑樹，紅黑樹隻能有2個子節點，B樹子節點大于2，子節點樹多這一特點保證了存儲相同大小的資料，樹的高度更小，資料局部更加緊湊，而硬碟讀取有局部加載的優化(緊湊的好處：把要讀取資料和周圍的資料一起預先讀取)，B樹相鄰資料實體上更加緊湊這一特點符合硬碟進行io優化的特性。
B+樹在B樹基礎上進一步将資料隻存在葉子節點，非葉子節點不存值隻存儲值的指向，這使得單個節點能有更多子節點，除此之外将所有葉子節點(值存在葉子節點)放傳入連結表中，使得資料更加緊湊有序，隻需要連結清單(葉子節點)的一次周遊就能擷取所有樹上的值。
B+樹這些特性适合用于資料庫的索引，mysql底層資料結構就是B+樹。
B樹更适用于磁盤讀取，紅黑樹更适用于記憶體讀取