[[402718]]

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

寫在前面

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

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

你：好像是B+樹吧

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

你：...

面試官：用B+樹實(shí)現(xiàn)索引結(jié)構(gòu)，有什么好處?

你：...

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

B-樹 簡介

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

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

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

平衡二叉樹 VS B-樹

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

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

那么我們?nèi)绾翁岣叱绦蛐阅苣?

• 平衡二叉樹

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

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

• B-樹

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

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

B-樹的查找

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

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

總結(jié)

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

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

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

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

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

為什么會(huì)存在B-樹這類結(jié)構(gòu)呢?

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