MySQL索引底層：B+樹詳解
本文公眾號(hào)來源：撿田螺的小男孩
作者：撿田螺的小男孩
本文已收錄至我的GitHub
當(dāng)我們發(fā)現(xiàn)SQL執(zhí)行很慢的時(shí)候，自然而然想到的就是加索引。對(duì)于范圍查詢，索引的底層結(jié)構(gòu)就是B+樹。今天我們一起來學(xué)習(xí)一下B+樹哈~
樹簡介、樹種類 B-樹、B+樹簡介 B+樹插入 B+樹查找 B+樹刪除 B+樹經(jīng)典面試題
樹的簡介
樹的簡介
樹跟數(shù)組、鏈表、堆棧一樣，是一種數(shù)據(jù)結(jié)構(gòu)。它由有限個(gè)節(jié)點(diǎn)，組成具有層次關(guān)系的集合。因?yàn)樗雌饋硐褚豢脴?，所以得其名。一顆普通的樹如下:
樹是包含n（n為整數(shù)，大于0）個(gè)結(jié)點(diǎn)， n-1條邊的有窮集，它有以下特點(diǎn)：
??
每個(gè)結(jié)點(diǎn)或者無子結(jié)點(diǎn)或者只有有限個(gè)子結(jié)點(diǎn)； 有一個(gè)特殊的結(jié)點(diǎn),它沒有父結(jié)點(diǎn)，稱為根結(jié)點(diǎn)； 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)； 樹里面沒有環(huán)路
一些有關(guān)于樹的概念：
??
結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的度； 樹的度：一棵樹中，最大結(jié)點(diǎn)的度稱為樹的度； 父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)； 深度：對(duì)于任意結(jié)點(diǎn)n,n的深度為從根到n的唯一路徑長，根結(jié)點(diǎn)的深度為0； 高度：對(duì)于任意結(jié)點(diǎn)n,n的高度為從n到一片樹葉的最長路徑長，所有樹葉的高度為0；
樹的種類
按照有序性，可以分為有序樹和無序樹：
??
無序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒有順序關(guān)系 有序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系
按照節(jié)點(diǎn)包含子樹個(gè)數(shù)，可以分為B樹和二叉樹，二叉樹可以分為以下幾種：
??
二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹； 二叉查找樹：首先它是一顆二叉樹，若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；左、右子樹也分別為二叉排序樹； 滿二叉樹：葉節(jié)點(diǎn)除外的所有節(jié)點(diǎn)均含有兩個(gè)子樹的樹被稱為滿二叉樹； 完全二叉樹：如果一顆二叉樹除去最后一層節(jié)點(diǎn)為滿二叉樹，且最后一層的結(jié)點(diǎn)依次從左到右分布 霍夫曼樹：帶權(quán)路徑最短的二叉樹。 紅黑樹：紅黑樹是一顆特殊的二叉查找樹，每個(gè)節(jié)點(diǎn)都是黑色或者紅色，根節(jié)點(diǎn)、葉子節(jié)點(diǎn)是黑色。如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。 平衡二叉樹（AVL）：一 棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹
B-樹、B+樹簡介
B-樹 簡介
B-樹，也稱為B樹，是一種平衡的多叉樹（可以對(duì)比一下平衡二叉查找樹），它比較適用于對(duì)外查找。看下這幾個(gè)概念哈：
??
階數(shù)：一個(gè)節(jié)點(diǎn)最多有多少個(gè)孩子節(jié)點(diǎn)。（一般用字母m表示） 關(guān)鍵字：節(jié)點(diǎn)上的數(shù)值就是關(guān)鍵字 度：一個(gè)節(jié)點(diǎn)擁有的子節(jié)點(diǎn)的數(shù)量。
一顆m階的B-樹，有以下特征：
??
根結(jié)點(diǎn)至少有兩個(gè)子女； 每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿足：?m/2? - 1 <= j <= m - 1.(??表示向上取整) 有k個(gè)關(guān)鍵字(關(guān)鍵字按遞增次序排列)的非葉結(jié)點(diǎn)恰好有k+1個(gè)孩子。 所有的葉子結(jié)點(diǎn)都位于同一層。
一棵簡單的B-樹如下：
B+ 樹簡介
B+樹是B-樹的變體，也是一顆多路搜索樹。一棵m階的B+樹主要有這些特點(diǎn)：
??
每個(gè)結(jié)點(diǎn)至多有m個(gè)子女; 非根節(jié)點(diǎn)關(guān)鍵值個(gè)數(shù)范圍：[m/2](注意是這個(gè)哈，后面圖例寫錯(cuò)了) <= k <= m-1 相鄰葉子節(jié)點(diǎn)是通過指針連起來的，并且是關(guān)鍵字大小排序的。
一顆3階的B+樹如下：
B+樹和B-樹的主要區(qū)別如下：
B-樹內(nèi)部節(jié)點(diǎn)是保存數(shù)據(jù)的;而B+樹內(nèi)部節(jié)點(diǎn)是不保存數(shù)據(jù)的，只作索引作用，它的葉子節(jié)點(diǎn)才保存數(shù)據(jù)。 B+樹相鄰的葉子節(jié)點(diǎn)之間是通過鏈表指針連起來的，B-樹卻不是。 查找過程中，B-樹在找到具體的數(shù)值以后就結(jié)束，而B+樹則需要通過索引找到葉子結(jié)點(diǎn)中的數(shù)據(jù)才結(jié)束 B-樹中任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中，而B+樹可以出現(xiàn)多次。
B+樹的插入
B+樹插入要記住這幾個(gè)步驟：
1.B+樹插入都是在葉子結(jié)點(diǎn)進(jìn)行的，就是插入前，需要先找到要插入的葉子結(jié)點(diǎn)。 2.如果被插入關(guān)鍵字的葉子節(jié)點(diǎn)，當(dāng)前含有的關(guān)鍵字?jǐn)?shù)量是小于階數(shù)m，則直接插入。 3.如果插入關(guān)鍵字后，葉子節(jié)點(diǎn)當(dāng)前含有的關(guān)鍵字?jǐn)?shù)目等于階數(shù)m，則插，該節(jié)點(diǎn)開始「分裂」為兩個(gè)新的節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)包含?m/2? 個(gè)關(guān)鍵字，另外一個(gè)關(guān)鍵字包含?m/2?個(gè)關(guān)鍵值。（?m/2?表示向下取整，?m/2?表示向上取整，如?3/2?=2）。 4.分裂后，需要將第?m/2?的關(guān)鍵字上移到父結(jié)點(diǎn)。如果這時(shí)候父結(jié)點(diǎn)中包含的關(guān)鍵字個(gè)數(shù)小于m，則插入操作完成。 5.分裂后，需要將?m/2?的關(guān)鍵字上移到父結(jié)點(diǎn)。如果父結(jié)點(diǎn)中包含的關(guān)鍵字個(gè)數(shù)等于m，則繼續(xù)分裂父結(jié)點(diǎn)。
以一顆4階的B+樹為例子吧，4階的話，關(guān)鍵值最多3（m-1）個(gè)。假設(shè)插入以下數(shù)據(jù)43，48，36，32,37,49,28.
在空樹中插入43
這時(shí)候根結(jié)點(diǎn)就一個(gè)關(guān)鍵值，此時(shí)它是根結(jié)點(diǎn)也是葉子結(jié)點(diǎn)。
依次插入48，36
這時(shí)候跟節(jié)點(diǎn)擁有3個(gè)關(guān)鍵字，已經(jīng)滿了
繼續(xù)插入 32，發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)關(guān)鍵字已經(jīng)不小于階數(shù)4了，于是分裂 第?4/2?=2（下標(biāo)0,1,2）個(gè)，也即43上移到父節(jié)點(diǎn)。
繼續(xù)插入37，49，前節(jié)點(diǎn)關(guān)鍵字都是還沒滿的，直接插入，如下：
最后插入28，發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)關(guān)鍵字也是不小于階數(shù)4了，于是分裂，于是分裂， 第 ?4/2?=2個(gè)，也就是36上移到父節(jié)點(diǎn)，因父子節(jié)點(diǎn)只有2個(gè)關(guān)鍵值，還是小于4的，所以不用繼續(xù)分裂，插入完成 
B+樹的查找
因?yàn)锽+樹的數(shù)據(jù)都是在葉子節(jié)點(diǎn)上的，內(nèi)部節(jié)點(diǎn)只是指針?biāo)饕淖饔茫虼?，查找過程需要搜索到葉子節(jié)點(diǎn)上。還是以這顆B+樹為例吧：
B+ 樹單值查詢
假設(shè)我們要查的值為32.
第一次磁盤 I/O，查找磁盤塊1，即根節(jié)點(diǎn)（36,43）,因?yàn)?2小于36，因此訪問根節(jié)點(diǎn)的左邊第一個(gè)孩子節(jié)點(diǎn)
第二次磁盤 I/O, 查找磁盤塊2，即根節(jié)點(diǎn)的第一個(gè)孩子節(jié)點(diǎn)，獲得區(qū)間(28,32),遍歷即可得32.
動(dòng)態(tài)圖如下：
B+ 樹范圍查詢
假設(shè)我們要查找區(qū)間 [32,40]區(qū)間的值.
第一步先訪問根節(jié)點(diǎn)，發(fā)現(xiàn)區(qū)間的左端點(diǎn)32小于36,則訪問根節(jié)點(diǎn)的第一個(gè)左子樹(28,32);
第二步訪問節(jié)點(diǎn)（28,32），找到32，于是開始遍歷鏈表，把[32,40]區(qū)間值找出來，這也是B+樹比B-樹高效的地方。
B+樹的刪除
B+樹刪除關(guān)鍵字，分這幾種情況
找到包含關(guān)鍵值的結(jié)點(diǎn)，如果關(guān)鍵字個(gè)數(shù)大于?m/2?-1，直接刪除即可； 找到包含關(guān)鍵值的結(jié)點(diǎn),如果關(guān)鍵字個(gè)數(shù)大于?m/2?-1，并且關(guān)鍵值是當(dāng)前節(jié)點(diǎn)的最大（?。┲?，并且該關(guān)鍵值存在父子節(jié)點(diǎn)中，那么刪除該關(guān)鍵字，同時(shí)需要相應(yīng)調(diào)整父節(jié)點(diǎn)的值。 找到包含關(guān)鍵值的結(jié)點(diǎn)，如果刪除該關(guān)鍵字后，關(guān)鍵字個(gè)數(shù)小于?m/2?，并且其兄弟結(jié)點(diǎn)有多余的關(guān)鍵字，則從其兄弟結(jié)點(diǎn)借用關(guān)鍵字 找到包含關(guān)鍵值的結(jié)點(diǎn)，如果刪除該關(guān)鍵字后，關(guān)鍵字個(gè)數(shù)小于?m/2?，并且其兄弟結(jié)點(diǎn)沒有多余的關(guān)鍵字，則與兄弟結(jié)點(diǎn)合并。
如果關(guān)鍵字個(gè)數(shù)大于?m/2?，直接刪除即可；
假設(shè)當(dāng)前有這么一顆5階的B+樹
如果刪除22，因?yàn)殛P(guān)鍵字個(gè)數(shù)為3 > ?5/2?-1=2， 直接刪除（??表示向上取整的意思）
如果關(guān)鍵字個(gè)數(shù)大于?m/2?-1，并且刪除的關(guān)鍵字存在于父子節(jié)點(diǎn)中，那么需要相應(yīng)調(diào)整父子節(jié)點(diǎn)的值
如果刪除20，因?yàn)殛P(guān)鍵字個(gè)數(shù)為3 > ?5/2?-1=2，并且20是當(dāng)前節(jié)點(diǎn)的邊界值，且存在父子節(jié)點(diǎn)中，所以刪除后，其父子節(jié)點(diǎn)也要響應(yīng)調(diào)整。
如果刪除該關(guān)鍵字后，關(guān)鍵字個(gè)數(shù)小于?m/2?-1，兄弟節(jié)點(diǎn)可以借用
以下這顆5階的B+樹，
如果刪除15,刪除關(guān)鍵字的結(jié)點(diǎn)只剩1個(gè)關(guān)鍵字，小于?5/2?-1=2，不滿足B+樹特點(diǎn)，但是其兄弟節(jié)點(diǎn)擁有3個(gè)元素（7,8,9），可以借用9過來，如圖：
在刪除關(guān)鍵字后，如果導(dǎo)致其結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)不足，并且兄弟結(jié)點(diǎn)沒有得借用的話，需要合并兄弟結(jié)點(diǎn)
以下這顆5階的B+樹：
如果刪除關(guān)鍵字7，刪除關(guān)鍵字的結(jié)點(diǎn)只剩1個(gè)關(guān)鍵字，小于?5/2?-1=2，不滿足B+樹特點(diǎn)，并且兄弟結(jié)點(diǎn)沒法借用，因此發(fā)生合并，如下：
主要流程醬紫：
因?yàn)?被刪掉后，只剩一個(gè)8的關(guān)鍵字，不滿足B+樹特點(diǎn)（?m/2?-1<=關(guān)鍵字<=m-1）。 并且沒有兄弟結(jié)點(diǎn)關(guān)鍵字借用，因此8與前面的兄弟結(jié)點(diǎn)結(jié)合。 被刪關(guān)鍵字結(jié)點(diǎn)的父節(jié)點(diǎn)，7索引也被刪掉了，只剩一個(gè)9，并且其右兄弟結(jié)點(diǎn)（18,20）只有兩個(gè)關(guān)鍵字，也是沒得借，因此在此合并。 被刪關(guān)鍵字結(jié)點(diǎn)的父子節(jié)點(diǎn)，也和其兄弟結(jié)點(diǎn)合并后，只剩一個(gè)子樹分支，因此根節(jié)點(diǎn)（16）也下移了。
所以刪除關(guān)鍵字7后的結(jié)果如下：
B+樹經(jīng)典面試題
InnoDB一棵B+樹可以存放多少行數(shù)據(jù)？ 為什么索引結(jié)構(gòu)默認(rèn)使用B+樹，而不是hash，二叉樹，紅黑樹，B-樹？ B-樹和B+樹的區(qū)別
InnoDB一棵B+樹可以存放多少行數(shù)據(jù)？
這個(gè)問題的簡單回答是：約2千萬行。
在計(jì)算機(jī)中，磁盤存儲(chǔ)數(shù)據(jù)最小單元是扇區(qū)，一個(gè)扇區(qū)的大小是512字節(jié)。 文件系統(tǒng)中，最小單位是塊，一個(gè)塊大小就是4k； InnoDB存儲(chǔ)引擎最小儲(chǔ)存單元是頁，一頁大小就是16k。
因?yàn)锽+樹葉子存的是數(shù)據(jù)，內(nèi)部節(jié)點(diǎn)存的是鍵值+指針。索引組織表通過非葉子節(jié)點(diǎn)的二分查找法以及指針確定數(shù)據(jù)在哪個(gè)頁中，進(jìn)而再去數(shù)據(jù)頁中找到需要的數(shù)據(jù)；
假設(shè)B+樹的高度為2的話，即有一個(gè)根結(jié)點(diǎn)和若干個(gè)葉子結(jié)點(diǎn)。這棵B+樹的存放總記錄數(shù)為=根結(jié)點(diǎn)指針數(shù)*單個(gè)葉子節(jié)點(diǎn)記錄行數(shù)。
如果一行記錄的數(shù)據(jù)大小為1k，那么單個(gè)葉子節(jié)點(diǎn)可以存的記錄數(shù) =16k/1k =16. 非葉子節(jié)點(diǎn)內(nèi)存放多少指針呢？我們假設(shè)主鍵ID為bigint類型，長度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，所以就是8+6=14字節(jié)，16k/14B =16*1024B/14B = 1170
因此，一棵高度為2的B+樹，能存放1170 * 16=18720條這樣的數(shù)據(jù)記錄。同理一棵高度為3的B+樹，能存放1170 *1170 *16 =21902400，也就是說，可以存放兩千萬左右的記錄。B+樹高度一般為1-3層，已經(jīng)滿足千萬級(jí)別的數(shù)據(jù)存儲(chǔ)。
為什么索引結(jié)構(gòu)默認(rèn)使用B+樹，而不是B-Tree，Hash哈希，二叉樹，紅黑樹？
簡單版回答如下：
Hash哈希，只適合等值查詢，不適合范圍查詢。 一般二叉樹，可能會(huì)特殊化為一個(gè)鏈表，相當(dāng)于全表掃描。 紅黑樹，是一種特化的平衡二叉樹，MySQL 數(shù)據(jù)量很大的時(shí)候，索引的體積也會(huì)很大，內(nèi)存放不下的而從磁盤讀取，樹的層次太高的話，讀取磁盤的次數(shù)就多了。 B-Tree，葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都保存數(shù)據(jù)，相同的數(shù)據(jù)量，B+樹更矮壯，也是就說，相同的數(shù)據(jù)量，B+樹數(shù)據(jù)結(jié)構(gòu)，查詢磁盤的次數(shù)會(huì)更少。
B-樹和B+樹的區(qū)別
B-樹內(nèi)部節(jié)點(diǎn)是保存數(shù)據(jù)的;而B+樹內(nèi)部節(jié)點(diǎn)是不保存數(shù)據(jù)的，只作索引作用，它的葉子節(jié)點(diǎn)才保存數(shù)據(jù)。 B+樹相鄰的葉子節(jié)點(diǎn)之間是通過鏈表指針連起來的，B-樹卻不是。 查找過程中，B-樹在找到具體的數(shù)值以后就結(jié)束，而B+樹則需要通過索引找到葉子結(jié)點(diǎn)中的數(shù)據(jù)才結(jié)束 B-樹中任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中，而B+樹可以出現(xiàn)多次。
《對(duì)線面試官》系列目前已經(jīng)連載19篇啦！進(jìn)度是一周更新兩篇，歡迎持續(xù)關(guān)注
【對(duì)線面試官】Java注解 【對(duì)線面試官】Java泛型 【對(duì)線面試官】 Java NIO 【對(duì)線面試官】Java反射 && 動(dòng)態(tài)代理 【對(duì)線面試官】多線程基礎(chǔ) 【對(duì)線面試官】 CAS 【對(duì)線面試官】synchronized 【對(duì)線面試官】AQS&&ReentrantLock 【對(duì)線面試官】線程池 【對(duì)線面試官】ThreadLocal 【對(duì)線面試官】CountDownLatch和CyclicBarrier 【對(duì)線面試官】List 【對(duì)線面試官】Map 【對(duì)線面試官】SpringMVC 【對(duì)線面試官】Spring基礎(chǔ) 【對(duì)線面試官】SpringBean生命周期 【對(duì)線面試官】Redis基礎(chǔ) 【對(duì)線面試官】Redis持久化
怎樣偷偷努力 驚艷所有人？
點(diǎn)擊小卡片關(guān)注【面試造火箭】