[[402718]]

本文轉載自微信公眾號「架構精進之路」，作者架構精進之路。轉載本文請聯(lián)系架構精進之路公眾號。

寫在前面

對于MySQL索引，相信每位后端同學日常工作中經(jīng)常會用到，但是對其索引原理，卻可能未曾真正深入了解，導致在面試過程中，回答不出重點那就可能要與機會說byebye了。

面試官：MySQL的索引實現(xiàn)是用什么數(shù)據(jù)結構?

你：好像是B+樹吧

面試官：為什么要用B+樹，而不是B-樹?

你：...

面試官：用B+樹實現(xiàn)索引結構，有什么好處?

你：...

B-樹和B+樹是MySQL索引使用的數(shù)據(jù)結構，對于索引優(yōu)化和原理理解都非常重要，下面就揭開B-樹和B+樹的神秘面紗，讓大家在面試的時候碰到這個知識點一往無前，不再成為你前進的羈絆!

B-樹 簡介

B-樹,這里的 B 表示 balance( 平衡的意思)，B-樹是一顆多路平衡查找樹，它類似普通的平衡二叉樹，不同的一點是B-樹允許每個節(jié)點有更多的子節(jié)點。

從上圖B-樹的簡化圖，我們可以發(fā)現(xiàn)幾個顯著特點：

• 所有鍵值分布在整顆樹中(索引值和具體data都在每個節(jié)點里)，葉節(jié)點具有相同的深度;
• 任何一個關鍵字出現(xiàn)且只出現(xiàn)在一個結點中;
• 搜索有可能在非葉子結點結束(最好情況O(1)就能找到數(shù)據(jù));
• 在關鍵字全集內做一次查找,性能逼近二分查找

平衡二叉樹 VS B-樹

我們知道傳統(tǒng)用來搜索的平衡二叉樹有很多，如 AVL 樹，紅黑樹等。

這些樹在一般情況下查詢性能非常好，但當數(shù)據(jù)非常大的時候它們就無能為力了。原因當數(shù)據(jù)量非常大時，內存不夠用，大部分數(shù)據(jù)只能存放在磁盤上，只有需要的數(shù)據(jù)才加載到內存中。一般而言內存訪問的時間約為 50 ns，而磁盤在 10 ms 左右。速度相差了近 5 個數(shù)量級，磁盤讀取時間遠遠超過了數(shù)據(jù)在內存中比較的時間。這說明程序大部分時間會阻塞在磁盤 IO 上。

那么我們如何提高程序性能呢?

• 平衡二叉樹

平衡二叉樹 是通過旋轉來保持平衡的，而旋轉是對整棵樹的操作，若部分加載到內存中則無法完成旋轉操作。其次平衡二叉樹的高度相對較大為 log n(底數(shù)為2)，這樣邏輯上很近的節(jié)點實際可能非常遠，無法很好的利用磁盤預讀(局部性原理)。

空間局部性原理：如果一個存儲器的某個位置被訪問，那么將它附近的位置也會被訪問。

• B-樹

B-樹多叉的好處非常明顯，有效的降低了B-樹的高度(為底數(shù)很大的 log n，底數(shù)大小與節(jié)點的子節(jié)點數(shù)目有關，一般一棵B-樹的高度在 3 層左右)。層數(shù)低，每個節(jié)點區(qū)確定的范圍更精確，范圍縮小的速度越快(比二叉樹深層次的搜索肯定快很多)。上面說了一個節(jié)點需要進行一次 IO，那么總 IO 的次數(shù)就縮減為了 log n 次。

B-樹的每個節(jié)點是 n 個有序的序列(a1，a2，a3… an)，并將該節(jié)點的子節(jié)點分割成 n+1 個區(qū)間來進行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

B-樹的查找

我們來看看B-樹的查找，假設每個節(jié)點有 n 個 key值，被分割為 n+1 個區(qū)間，注意，每個 key 值緊跟著 data 域，這說明B-樹的 key 和 data 是聚合在一起的。一般而言，根節(jié)點都在內存中，B-樹以每個節(jié)點為一次磁盤 IO。

若搜索 key 為 25 節(jié)點的 data，首先在根節(jié)點進行二分查找(因為 keys 有序，二分最快)，判斷 key 25 小于 key 50，所以定位到最左側的節(jié)點，此時進行一次磁盤 IO，將該節(jié)點從磁盤讀入內存，接著繼續(xù)進行上述過程，直到找到該 key 為止。

總結

索引的效率依賴于磁盤 IO 的次數(shù)，快速索引需要有效的減少磁盤 IO 次數(shù)。

Q：那如何實現(xiàn)快速索引呢?

索引的原理其實是不斷的縮小查找范圍，就如我們平時用字典查單詞一樣，先找首字母縮小范圍，再第二個字母等等。

• 平衡二叉樹是每次將范圍分割為兩個區(qū)間;
• B-樹每次將范圍分割為多個區(qū)間，區(qū)間越多，定位數(shù)據(jù)越快越精確。

那么如果節(jié)點為區(qū)間范圍，每個節(jié)點就較大了。所以新建節(jié)點時，直接申請頁大小的空間(磁盤存儲單位是按 block 分的，一般為 512 Byte。磁盤 IO 一次讀取若干個 block，我們稱為一頁，具體大小和操作系統(tǒng)有關，一般為 4 k，8 k或 16 k)，計算機內存分配是按頁對齊的，這樣就實現(xiàn)了一個節(jié)點只需要一次 IO。

為什么會存在B-樹這類結構呢?

任何事物，存在就有其道理。B-樹的設計相對平衡二叉樹，似乎更“迎合”磁盤的角度。