迎面走來了你的面試官，身穿格子衫，挺著啤酒肚，發際線嚴重后移的中年男子，
手拿泡著枸杞的保溫杯，胳膊夾著MacBook，MacBook上還貼著公司標語：“我愛加班”，
面試開始，直入正題，
面試官： 你知道MySQL索引底層資料結構為啥用B+樹？而不用B樹、紅黑樹或者普通二叉樹？
我： 這事誰知道作者咋想的？他可能是用B+樹習慣了，個人愛好吧，
面試官： 你倒是挺看得開，今天的面試就先到這吧，后面有訊息會主動聯系你，
后面還可能有訊息嗎？你們啥時候主動聯系過我？
實話實說的被拒，八股文背得溜反而被錄取，
好吧，等我看看一燈怎么總結的MySQL的八股文，
我： 要知道MySQL索引底層資料結構為啥用B+樹，先要了解一下什么樣的資料結構更適合建索引，
為了保證資料安全性，一般都是把資料存盤在磁盤里面，當我們需要查詢資料的時候，需要讀取磁盤，就產生了磁盤IO，相比較記憶體操作，磁盤IO讀取速度是非常慢的，
由于所需資料可能在磁盤并不是連續的，一次資料查詢就需要多次磁盤IO，所以就需要我們設計的索引資料結構盡可能的減少磁盤IO次數，
再了解一下這幾種二叉樹的特性，以及優缺點，就知道哪種資料結構更適合建索引，
什么是二叉搜索樹：
- 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
- 若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
- 左、右子樹也分別為二叉查找樹；
二叉搜索樹查找資料的時間復雜度是O(logN)，如圖所示，最多查找3次就可以查到所需資料，
理想很豐滿，現實很骨感，極端情況下，二叉查找樹可能退化成線性鏈表，
鏈表的查找時間復雜度是O(N)，這時候最多需要7次才能查到所需資料，
該怎么辦呢？于是我們就想到了給二叉樹加一些限制條件，平衡一下左右子樹，然后就引申出了很多平衡樹：平衡二叉查找樹、紅黑樹、B樹、B+樹，咱們分別說一下這幾種樹的優缺點，看哪種樹最適合做索引，
什么是紅黑樹？
- 結點是紅色或黑色
- 根結點是黑色
- 所有葉子都是黑色（葉子是NIL結點）
- 每個紅色結點的兩個子結點都是黑色（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點）
- 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點
看蒙了沒有？
這么多復雜的規則，就是為了保證從根節點到葉子節點的最長路徑不超過最短路徑的2倍，
當插入節點或者洗掉節點的時候，為了滿足紅黑樹規則，可能需要變色和旋轉，這是一個復雜且耗時的程序，
紅黑樹的優點：
限制了左右子樹的樹高，不會相差過大，
缺點：
規則復雜，一般人想要弄懂這玩意兒，就已經很費勁了，更別說使用了，
什么是B樹？
我們知道，樹的高度越高，查找次數越多，也就是磁盤IO次數越多，耗時越長，
我們能不能想辦法降低樹的高度，把二叉樹變成N叉樹？于是B樹就來了，
對于一個m階的B樹：
- 根節點至少有2個子節點
- 每個中間節點都包含k-1個元素和k個子節點，其中 m/2 <= k <= m
- 每個葉子節點都包含k-1個元素，其中 m/2 <= k <= m
- 中間節點的元素按照升序排列
- 所有的葉子結點都位于同一層
根節點（8）有兩個子節點，左子節點（3 5）和右子節點（11 15），
左子節點（3 5）中有2個元素和3個子節點，
元素是3和5，按照升序排列，
子節點是（1 2）、（4）、（6 7），
而（1 2）中元素小于3，（4）中的元素在3和5中間，（6 7）的元素大于5，符合B樹特征，
B樹這樣的設計有哪些優點呢？
高度更低，每個節點含有多個元素，查找的時候一次可以把一個節點中的所有元素加載到記憶體中作比較，兩種改進都大大減少了磁盤IO次數，
什么是B+樹？
相比較B樹，B+樹又做了如下約定：
-
有k個子節點的中間節點就有k個元素（B樹中是k-1個元素），也就是子節點數量 = 元素數量，
每個元素不保存資料，只用來索引，所有資料都保存在葉子節點， -
所有的中間節點元素都同時存在于子節點，在子節點元素中是最大（或最小）元素，
-
非葉子節點只保存索引，不保存資料，（B樹中兩者都保存）
-
葉子結點包含了全部元素的資訊，并且葉子結點按照元素大小組成有序串列，
B+樹這樣設計有什么優點呢？
- 每個節點存盤的元素更多，看起來比B樹更矮胖，導致磁盤IO次數更少，
- 非葉子節點不存盤資料，只存盤索引，葉子節點存盤全部資料，
這樣設計導致每次查找都會查到葉子節點，效率更穩定，便于做性能優化， - 葉子節點之間使用有序鏈表連接，
這樣設計方便范圍查找，只需要遍歷鏈表中相鄰元素即可，不再需要二次遍歷二叉樹，
很明顯，B樹和B+樹就是為了檔案檢索系統設計的，更適合做索引結構，
面試官： 還得是你，就你總結的全，我都想不那么全，明天來上班吧，薪資double，
本文知識點總結：
文章持續更新，可以微信搜一搜「 一燈架構 」第一時間閱讀更多技術干貨，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/495434.html
標籤：Java
上一篇：運行硒問題
下一篇：Redis的五種基本資料型別