為什么MySQL的常用引擎都默認使用B+樹作為索引？
一、前言
為了講清楚這個問題，阿粉先帶大家了解一下什么是索引。
我記得剛剛學習數據庫的時候，老師喜歡用書本的目錄來類比數據庫的索引，并告訴我們索引能夠像目錄一樣，讓我們更快地找到想要找到的數據。
如果是第一次接觸索引，這個比喻能夠讓我們有一個直觀的印象。但是當深入去學習索引的時候，我們不能繼續持有索引即目錄的思想，我們要跳出來去思考索引的本質是什么。
二、索引的本質
在沒有索引的情況下，我們查找數據只能按照從頭到尾的順序逐行查找，每查找一行數據，意味著我們要到到磁盤相應的位置去讀取一條數據。
如果把查詢一條數據分為到磁盤中查詢和比對查詢條件兩步的話，到磁盤中查詢的時間會遠遠大于比對查詢條件的時間，這意味著在一次查詢中，磁盤io占用了大部分的時間。更進一步地說，一次查詢的效率取絕于磁盤io的次數，如果我們能夠在一次查詢中盡可能地降低磁盤io的次數，那么我們就能加快查詢的速度。
在知道了減少磁盤io能加快查詢速度后，我們就要聚焦于如何減少磁盤io。如果按照原表逐行查詢的話，n條數據就要查詢n次，也就是O(N)的時間復雜度，為了減少磁盤io的次數，我們必須用一種查詢時間復雜度更低的數據結構來保存數據。
這種查詢時間復雜度低的數據結構，我們稱之為索引。所以通俗來說，索引其實就是某種數據結構，能充當索引的數據結構是多種多樣的。
三、索引的選擇
既然索引是一種便于查詢的數據結構，如果大家對數據結構有一定了解的話，大概率會首選樹型結構。畢竟樹型結構普遍有著O(logN)的查詢時間復雜度，而且插入刪除數據的性能也比較平均。(可能你會說數組，哈希表的查詢速度也很高啊，這個后面也會分析)
雖然我們都已經知道Mysql中最常用的引擎像InnoDB和MyISAM，最終都選擇了B+樹作為索引，但是這里我還是打算從最常見的二叉樹開始講起，推導一下為什么最終選擇了B+樹作為索引，并比較一下幾種樹型結構在充當索引時的優劣。
二叉樹
最普通的二叉樹的問題在于他不能保證O(logN)的查詢時間復雜度，我們看下面的圖：
由于插入的元素逐漸增大，元素始終在右邊進行插入，好好的一棵二叉樹最終變成了一條“鏈表”。在這種極端的情況下，二叉樹的查詢時間復雜度不再是O(logN)，而是退化為O(N)，這樣顯然不符合索引的要求。
平衡二叉樹(紅黑樹)
像紅黑樹這樣的平衡二叉樹，無論如何插入元素，他都可以通過一些旋轉的方法調整樹的高度，使得整棵樹的查詢效率維持在O(logN)，如下圖所示：
這么來說他已經符合了成為索引的必備條件，但是最終沒有選擇他作為索引說明還有不足的地方。仔細看看可以發現平衡二叉樹的每個節點只有兩個孩子節點，如果一張表的數據量特別大，整棵樹的高度也會隨之上升。一個千萬級別的表如果用平衡二叉樹作為索引的話，樹高將會達到二十多層。這也就意味著做一次查詢需要二十多次磁盤io，這是一個不小的開銷。
那么有沒有能在大數據量的情況下，還能保持一個較小樹高的樹型結構呢?
B樹和B+樹
答案就是B樹。上面我們說到了平衡二叉樹的瓶頸在于一個節點只有兩個孩子節點，而B樹一個節點可以存放N個孩子節點，這就完美解決了樹高的問題，我們可以把B樹稱為平衡多叉樹，B樹作為索引如下圖所示：
圖片來源網絡
但是以B樹的結構作為索引仍有可以優化的地方，我們先看看最終的B+樹，再仔細分析B+樹在B樹的基礎上作了哪些改進，為什么B+樹最終能夠勝任索引的工作：
圖片來源網絡
從圖片中可以看到B+樹同樣是一棵多差平衡樹，和B樹一樣很好地解決了樹高的問題。
改進點一：
但仔細看可以發現，B樹的節點中既存儲索引，也存儲表對應的數據;而B+樹的非葉子節點是不存儲數據的，只存儲索引，數據全部存儲在葉子節點上。
為什么要做這樣的改進?我們做一次算術就知道了。
假設樹高為2，主鍵ID為bigint類型，長度為8字節，節點指針為6字節，一行數據記錄的大小為1k，一次io操作能獲得一頁16k的數據。
在索引為B+樹的情況下，根節點能存儲：16k / (6 + 8) = 1170 條索引指針;到了第一層，一共能指向 1170 * 1170 = 1368900 條索引指針;到了最底一層葉子節點，一個節點能存儲16k / 1k = 16 條記錄，一共能存儲 1170 * 1170 * 16 = 21902400 條記錄
在B樹的情況下，由于非葉子節點使用了大量空間存儲數據，存放的索引指針肯定就少，最終整棵樹如果想要存儲和B+樹一樣多的數據就必須要增加樹高，這樣一來就增加了磁盤io，所以說B+樹作為索引的性能比B樹高。
改進點二：
葉子節點之間使用指針連接，提高區間訪問效率。如果我們要進行范圍查詢，可以輕松通過B+樹葉子節點之間的指針進行遍歷，減少了不必要的磁盤io。
總結
看到這里，相信大家對為什么Mysql的常用引擎都默認使用B+樹作為索引已經有了初步的認知。我們只要牢記一點：索引是為了減少磁盤io提高查詢性能而存在的。
最后回應一下為什么不常用哈希表和數組作為索引
哈希表雖然單一個值的查詢效率很高，但是撐不住范圍查詢，哪個公司的業務還沒個范圍查詢呢?
而數組雖然查詢的效率高，但是增加和刪除的效率低，由于記錄在增加和刪除的時候索引也得跟著維護，這會導致大數據量的情況下，增加或刪除一條記錄效率較低。
