前言
本文是在講述什麼樣的資料結構适合作為索引，以及其适合作為索引的原因。而閱讀本文需要對B樹和B+樹結構有稍微的了解。以及需要對磁盤操作知識有稍微的了解。
什麼是索引
索引（Index）是幫助資料庫高效擷取資料的資料結構。索引是在基于資料庫表建立的，它包含一個表中某些列的值以及記錄對應的位址，并且把這些值存儲在一個資料結構中。最常見的就是使用哈希表、B+樹作為索引。
為什麼要使用索引
我們知道，資料庫查詢是資料庫最主要的功能之一。而查詢速度當然是越快越好。而當資料量越來越大的時候，查詢花費的時間會随之增長。而索引，可以加速資料的查詢。因為索引是有序排列的。
資料庫中使用什麼資料結構作為索引
我們知道，數組+二分查找的效率是O(lgn)，但是數組的插入元素以及删除元素的效率很低，是以使用數組做為索引結構并不合适。
另外，在選擇資料庫索引的結構的時候，要考慮到另一個問題。索引是存在于磁盤中，當索引非常大的時候，達到幾個G的時候，無法一次加載到記憶體中。
考慮到上面兩個因素，資料庫中索引使用的是樹形結構。
各種樹的名字
有這麼幾種樹：
B-Tree
B+-Tree
B*-Tree
首先要明白三種樹名中的“-”起到的是分隔的作用，并不是“減”的意思。
是以正确的翻譯應該是B樹，B+樹，B*樹。而不是B-樹，B+樹，B*樹。是以，當你聽到别人說“B減樹”的時候，要明白它指的是B-Tree。即B樹和B-樹是同一種樹。
二叉樹
即二叉搜尋樹：
1.所有非葉子結點至多擁有兩個兒子（Left和Right）；
2.所有結點存儲一個關鍵字；
3.非葉子結點的左指針指向小于其關鍵字的子樹，右指針指向大于其關鍵字的子樹；
如：
二叉樹的搜尋，從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那麼就命中；否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字；
如果二叉樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那麼二叉樹的搜尋性能逼近二分查找；但它比連續記憶體空間的二分查找的優點是，改變二叉樹結構（插入與删除結點）不需要移動大段的記憶體資料，甚至通常是常數開銷；
如：
但二叉樹在經過多次插入與删除後，有可能導緻不同的結構：
右邊也是一個平衡二叉樹，但它的搜尋性能已經是線性的了；同樣的關鍵字集合有可能導緻不同的樹結構索引；是以，使用二叉樹樹還要考慮盡可能讓二叉樹保持左圖的結構，和避免右圖的結構，也就是所謂的“平衡”問題；
實際使用的二叉樹都是在原二叉樹的基礎上加上平衡算法，即“平衡二叉樹”；如何保持二叉樹結點分布均勻的平衡算法是平衡二叉樹的關鍵；平衡算法是一種在二叉樹中插入和删除結點的政策。常見的平衡二叉樹有：AVL，RBT，Treap，Splay Tree。
B-樹
是一種多路搜尋樹（并不是二叉的）：
1.定義任意非葉子結點最多隻有M個兒子；且M>2；
2.根結點的兒子數為[2, M]；
3.除根結點以外的非葉子結點的兒子數為[M/2,M]；
4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；
6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
8.所有葉子結點位于同一層；
如：（M=3）
B-樹的搜尋，從根結點開始，對結點内的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬範圍的兒子結點；重複，直到所對應的兒子指針為空，或已經是葉子結點；
B-樹的特性：
1.關鍵字集合分布在整顆樹中；
2.任何一個關鍵字出現且隻出現在一個結點中；
3.搜尋有可能在非葉子結點結束；
4.其搜尋性能等價于在關鍵字全集内做一次二分查找；
5.自動層次控制；
由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確定了結點的至少使用率，其最底搜尋性能為：
其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；
是以B-樹的性能總是等價于二分查找（與M值無關），也就沒有B樹平衡的問題；
由于M/2的限制，在插入結點時，如果結點已滿，需要将結點分裂為兩個各占M/2的結點；删除結點時，需将兩個不足M/2的兄弟結點合并；
B+樹
B+樹是B-樹的變體，也是一種多路搜尋樹：
1.其定義基本與B-樹同，除了：
2.非葉子結點的子樹指針與關鍵字個數相同；
3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區間）；
5.為所有葉子結點增加一個鍊指針；
6.所有關鍵字都在葉子結點出現；
如：（M=3）
B+的搜尋與B-樹也基本相同，差別是B+樹隻有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；
B+的特性：
1.所有關鍵字都出現在葉子結點的連結清單中（稠密索引），且連結清單中的關鍵字恰好是有序的；
2.不可能在非葉子結點命中；
3.非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）資料的資料層；
4.更适合檔案索引系統；
B*樹
是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；
B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）；
B+樹的分裂：當一個結點滿時，配置設定一個新的結點，并将原結點中1/2的資料複制到新結點，最後在父結點中增加新結點的指針；B+樹的分裂隻影響原結點和父結點，而不會影響兄弟結點，是以它不需要指向兄弟的指針；
B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那麼将一部分資料移到兄弟結點中，再在原結點插入關鍵字，最後修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字範圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各複制1/3的資料到新結點，最後在父結點增加新結點的指針；
是以，B*樹配置設定新結點的機率比B+樹要低，空間使用率更高；
平衡二叉樹
樹形結構是計算機系統裡最重要的資料結構。
我們知道，二叉樹的查找的時間複雜度是O(log2N)，其查找效率與深度有關，而普通的二叉樹可能由于内部節點排列問題退化成連結清單，這樣查找效率就會很低。是以平衡二叉樹是更好的選擇，因為它保持平衡，即通過旋轉調整結構保持最小的深度。其查找的時間複雜度也是O(log2N)。
但實際上，資料庫中索引的結構也并非AVL樹或更優秀的紅黑樹，盡管它的查詢的時間複雜度很低。
為什麼平衡二叉樹也不适合作為索引
索引是存在于索引檔案中，是存在于磁盤中的。因為索引通常是很大的，是以無法一次将全部索引加載到記憶體當中，是以每次隻能從磁盤中讀取一個磁盤頁的資料到記憶體中。而這個磁盤的讀取的速度較記憶體中的讀取速度而言是差了好幾個級别。
注意，我們說的平衡二叉樹結構，指的是邏輯結構上的平衡二叉樹，其實體實作是數組。然後由于在邏輯結構上相近的節點在實體結構上可能會差很遠。是以，每次讀取的磁盤頁的資料中有許多是用不上的。是以，查找過程中要進行許多次的磁盤讀取操作。
而适合作為索引的結構應該是盡可能少的執行磁盤IO操作，因為執行磁盤IO操作非常的耗時。是以，平衡二叉樹并不适合作為索引結構。
B-Tree适合作為索引
平衡二叉樹不适合作為索引。那麼什麼才适合作為索引——B樹。
平衡二叉樹沒能充分利用磁盤預讀功能，而B樹是為了充分利用磁盤預讀功能來而建立的一種資料結構，也就是說B樹就是為了作為索引才被發明出來的的。
來看看關于“局部性原理與磁盤預讀”的知識：
局部性原理與磁盤預讀：
由于存儲媒體的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，是以為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使隻需要一個位元組，磁盤也會從這個位置開始，順序向後讀取一定長度的資料放入記憶體。這樣做的理論依據是計算機科學中著名的局部性原理：
當一個資料被用到時，其附近的資料也通常會馬上被使用。
程式運作期間所需要的資料通常比較集中。
由于磁盤順序讀取的效率很高（不需要尋道時間，隻需很少的旋轉時間），是以對于具有局部性的程式來說，預讀可以提高I/O效率。
搞清楚上面的意思。磁盤預讀是具體實作，其理論依據是局部性原理。
為什麼說紅黑樹沒能充分利用磁盤預讀功能，引用一篇博文的一段話：
紅黑樹這種結構，h明顯要深的多。由于邏輯上很近的節點（父子）實體上可能很遠，無法利用局部性，是以紅黑樹的I/O漸進複雜度也為O(h)，效率明顯比B-Tree差很多。
也就是說，使用紅黑樹（平衡二叉樹）結構的話，每次磁盤預讀中的很多資料是用不上的資料。是以，它沒能利用好磁盤預讀的提供的資料。然後又由于深度大（較B樹而言），是以進行的磁盤IO操作更多。
B樹的每個節點可以存儲多個關鍵字，它将節點大小設定為磁盤頁的大小，充分利用了磁盤預讀的功能。每次讀取磁盤頁時就會讀取一整個節點。也正因每個節點存儲着非常多個關鍵字，樹的深度就會非常的小。進而要執行的磁盤讀取操作次數就會非常少，更多的是在記憶體中對讀取進來的資料進行查找。
B樹的查詢，主要發生在記憶體中，而平衡二叉樹的查詢，則是發生在磁盤讀取中。是以，雖然B樹查詢查詢的次數不比平衡二叉樹的次數少，但是相比起磁盤IO速度，記憶體中比較的耗時就可以忽略不計了。是以，B樹更适合作為索引。
比B樹更适合作為索引的結構——B+樹
比B樹更适合作為索引的結構是B+樹。MySQL中也是使用B+樹作為索引。它是B樹的變種，是以是基于B樹來改進的。為什麼B+樹會比B樹更加優秀呢？
B樹：有序數組+平衡多叉樹；
B+樹：有序數組連結清單+平衡多叉樹；
B+樹的關鍵字全部存放在葉子節點中，非葉子節點用來做索引，而葉子節點中有一個指針指向一下個葉子節點。做這個優化的目的是為了提高區間通路的性能。而正是這個特性決定了B+樹更适合用來存儲外部資料。
引用一段話：
走進搜尋引擎的作者梁斌老師針對B樹、B+樹給出了他的意見（為了真實性，特引用其原話，未作任何改動）： “B+樹還有一個最大的好處，友善掃庫，B樹必須用中序周遊的方法按序掃庫，而B+樹直接從葉子結點挨個掃一遍就完了，B+樹支援range-query非常友善，而B樹不支援。這是資料庫選用B+樹的最主要原因。
比如要查 5-10之間的，B+樹一把到5這個标記，再一把到10，然後串起來就行了，B樹就非常麻煩。B樹的好處，就是成功查詢特别有利，因為樹的高度總體要比B+樹矮。不成功的情況下，B樹也比B+樹稍稍占一點點便宜。
B樹比如你的例子中查，17的話，一把就得到結果了，
有很多基于頻率的搜尋是選用B樹，越頻繁query的結點越往根上走，前提是需要對query做統計，而且要對key做一些變化。
另外B樹也好B+樹也好，根或者上面幾層因為被反複query，是以這幾塊基本都在記憶體中，不會出現讀磁盤IO，一般已啟動的時候，就會主動換入記憶體。”
資料庫索引采用B+樹的主要原因是B樹在提高了磁盤IO性能的同時并沒有解決元素周遊的效率低下的問題。正是為了解決這個問題，B+樹應運而生。B+樹隻要周遊葉子節點就可以實作整棵樹的周遊。而且在資料庫中基于範圍的查詢是非常頻繁的，而B樹不支援這樣的操作（或者說效率太低）。
正如上面所說，在資料庫中基于範圍的查詢是非常頻繁的，是以MySQL最終選擇的索引結構是B+樹而不是B樹。