面試官：談談你對索引的認知系列之B-樹
本文轉載自微信公眾號「架構精進之路」，作者架構精進之路。轉載本文請聯系架構精進之路公眾號。
寫在前面
對于MySQL索引，相信每位后端同學日常工作中經常會用到，但是對其索引原理，卻可能未曾真正深入了解，導致在面試過程中，回答不出重點那就可能要與機會說byebye了。
面試官：MySQL的索引實現是用什么數據結構?
你：好像是B+樹吧
面試官：為什么要用B+樹，而不是B-樹?
你：...
面試官：用B+樹實現索引結構，有什么好處?
你：...
B-樹和B+樹是MySQL索引使用的數據結構，對于索引優化和原理理解都非常重要，下面就揭開B-樹和B+樹的神秘面紗，讓大家在面試的時候碰到這個知識點一往無前，不再成為你前進的羈絆!
B-樹 簡介
B-樹,這里的 B 表示 balance( 平衡的意思)，B-樹是一顆多路平衡查找樹，它類似普通的平衡二叉樹，不同的一點是B-樹允許每個節點有更多的子節點。
從上圖B-樹的簡化圖，我們可以發現幾個顯著特點：
- 所有鍵值分布在整顆樹中(索引值和具體data都在每個節點里)，葉節點具有相同的深度;
- 任何一個關鍵字出現且只出現在一個結點中;
- 搜索有可能在非葉子結點結束(最好情況O(1)就能找到數據);
- 在關鍵字全集內做一次查找,性能逼近二分查找
平衡二叉樹 VS B-樹
我們知道傳統用來搜索的平衡二叉樹有很多，如 AVL 樹，紅黑樹等。
這些樹在一般情況下查詢性能非常好，但當數據非常大的時候它們就無能為力了。原因當數據量非常大時，內存不夠用，大部分數據只能存放在磁盤上，只有需要的數據才加載到內存中。一般而言內存訪問的時間約為 50 ns，而磁盤在 10 ms 左右。速度相差了近 5 個數量級，磁盤讀取時間遠遠超過了數據在內存中比較的時間。這說明程序大部分時間會阻塞在磁盤 IO 上。
那么我們如何提高程序性能呢?
- 平衡二叉樹
平衡二叉樹 是通過旋轉來保持平衡的，而旋轉是對整棵樹的操作，若部分加載到內存中則無法完成旋轉操作。其次平衡二叉樹的高度相對較大為 log n(底數為2)，這樣邏輯上很近的節點實際可能非常遠，無法很好的利用磁盤預讀(局部性原理)。
空間局部性原理：如果一個存儲器的某個位置被訪問，那么將它附近的位置也會被訪問。
- B-樹
B-樹多叉的好處非常明顯，有效的降低了B-樹的高度(為底數很大的 log n，底數大小與節點的子節點數目有關，一般一棵B-樹的高度在 3 層左右)。層數低，每個節點區確定的范圍更精確，范圍縮小的速度越快(比二叉樹深層次的搜索肯定快很多)。上面說了一個節點需要進行一次 IO，那么總 IO 的次數就縮減為了 log n 次。
B-樹的每個節點是 n 個有序的序列(a1，a2，a3… an)，并將該節點的子節點分割成 n+1 個區間來進行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。
B-樹的查找
我們來看看B-樹的查找，假設每個節點有 n 個 key值，被分割為 n+1 個區間，注意，每個 key 值緊跟著 data 域，這說明B-樹的 key 和 data 是聚合在一起的。一般而言，根節點都在內存中，B-樹以每個節點為一次磁盤 IO。
若搜索 key 為 25 節點的 data，首先在根節點進行二分查找(因為 keys 有序，二分最快)，判斷 key 25 小于 key 50，所以定位到最左側的節點，此時進行一次磁盤 IO，將該節點從磁盤讀入內存，接著繼續進行上述過程，直到找到該 key 為止。
總結
索引的效率依賴于磁盤 IO 的次數，快速索引需要有效的減少磁盤 IO 次數。
Q：那如何實現快速索引呢?
索引的原理其實是不斷的縮小查找范圍，就如我們平時用字典查單詞一樣，先找首字母縮小范圍，再第二個字母等等。
- 平衡二叉樹是每次將范圍分割為兩個區間;
- B-樹每次將范圍分割為多個區間，區間越多，定位數據越快越精確。
那么如果節點為區間范圍，每個節點就較大了。所以新建節點時，直接申請頁大小的空間(磁盤存儲單位是按 block 分的，一般為 512 Byte。磁盤 IO 一次讀取若干個 block，我們稱為一頁，具體大小和操作系統有關，一般為 4 k，8 k或 16 k)，計算機內存分配是按頁對齊的，這樣就實現了一個節點只需要一次 IO。
為什么會存在B-樹這類結構呢?
任何事物，存在就有其道理。B-樹的設計相對平衡二叉樹，似乎更“迎合”磁盤的角度。
