MySQL索引底層:B+樹(shù)詳解
前言
當(dāng)我們發(fā)現(xiàn)SQL執(zhí)行很慢的時(shí)候,自然而然想到的就是加索引。對(duì)于范圍查詢,索引的底層結(jié)構(gòu)就是B+樹(shù)。今天我們一起來(lái)學(xué)習(xí)一下B+樹(shù)哈~
- 樹(shù)簡(jiǎn)介、樹(shù)種類(lèi)
- B-樹(shù)、B+樹(shù)簡(jiǎn)介
- B+樹(shù)插入
- B+樹(shù)查找
- B+樹(shù)刪除
- B+樹(shù)經(jīng)典面試題
樹(shù)的簡(jiǎn)介
樹(shù)的簡(jiǎn)介
樹(shù)跟數(shù)組、鏈表、堆棧一樣,是一種數(shù)據(jù)結(jié)構(gòu)。它由有限個(gè)節(jié)點(diǎn),組成具有層次關(guān)系的集合。因?yàn)樗雌饋?lái)像一棵樹(shù),所以得其名。一顆普通的樹(shù)如下:
樹(shù)是包含n(n為整數(shù),大于0)個(gè)結(jié)點(diǎn), n-1條邊的有窮集,它有以下特點(diǎn):
- 每個(gè)結(jié)點(diǎn)或者無(wú)子結(jié)點(diǎn)或者只有有限個(gè)子結(jié)點(diǎn);
- 有一個(gè)特殊的結(jié)點(diǎn),它沒(méi)有父結(jié)點(diǎn),稱(chēng)為根結(jié)點(diǎn);
- 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn);
- 樹(shù)里面沒(méi)有環(huán)路
一些有關(guān)于樹(shù)的概念:
- 結(jié)點(diǎn)的度:一個(gè)結(jié)點(diǎn)含有的子結(jié)點(diǎn)個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度;
- 樹(shù)的度:一棵樹(shù)中,最大結(jié)點(diǎn)的度稱(chēng)為樹(shù)的度;
- 父結(jié)點(diǎn):若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn),則這個(gè)結(jié)點(diǎn)稱(chēng)為其子結(jié)點(diǎn)的父結(jié)點(diǎn);
- 深度:對(duì)于任意結(jié)點(diǎn)n,n的深度為從根到n的唯一路徑長(zhǎng),根結(jié)點(diǎn)的深度為0;
- 高度:對(duì)于任意結(jié)點(diǎn)n,n的高度為從n到一片樹(shù)葉的最長(zhǎng)路徑長(zhǎng),所有樹(shù)葉的高度為0;
樹(shù)的種類(lèi)
按照有序性,可以分為有序樹(shù)和無(wú)序樹(shù):
- 無(wú)序樹(shù):樹(shù)中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒(méi)有順序關(guān)系
- 有序樹(shù):樹(shù)中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系
按照節(jié)點(diǎn)包含子樹(shù)個(gè)數(shù),可以分為B樹(shù)和二叉樹(shù),二叉樹(shù)可以分為以下幾種:
- 二叉樹(shù):每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱(chēng)為二叉樹(shù);
- 二叉查找樹(shù):首先它是一顆二叉樹(shù),若左子樹(shù)不空,則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;若右子樹(shù)不空,則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值;左、右子樹(shù)也分別為二叉排序樹(shù);
- 滿二叉樹(shù):葉節(jié)點(diǎn)除外的所有節(jié)點(diǎn)均含有兩個(gè)子樹(shù)的樹(shù)被稱(chēng)為滿二叉樹(shù);
- 完全二叉樹(shù):如果一顆二叉樹(shù)除去最后一層節(jié)點(diǎn)為滿二叉樹(shù),且最后一層的結(jié)點(diǎn)依次從左到右分布
- 霍夫曼樹(shù):帶權(quán)路徑最短的二叉樹(shù)。
- 紅黑樹(shù):紅黑樹(shù)是一顆特殊的二叉查找樹(shù),每個(gè)節(jié)點(diǎn)都是黑色或者紅色,根節(jié)點(diǎn)、葉子節(jié)點(diǎn)是黑色。如果一個(gè)節(jié)點(diǎn)是紅色的,則它的子節(jié)點(diǎn)必須是黑色的。
- 平衡二叉樹(shù)(AVL):一 棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1,并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)
B-樹(shù)、B+樹(shù)簡(jiǎn)介
B-樹(shù) 簡(jiǎn)介
B-樹(shù),也稱(chēng)為B樹(shù),是一種平衡的多叉樹(shù)(可以對(duì)比一下平衡二叉查找樹(shù)),它比較適用于對(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-樹(shù),有以下特征:
- 根結(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)都位于同一層。
一棵簡(jiǎn)單的B-樹(shù)如下:
B+ 樹(shù)簡(jiǎn)介
B+樹(shù)是B-樹(shù)的變體,也是一顆多路搜索樹(shù)。一棵m階的B+樹(shù)主要有這些特點(diǎn):
- 每個(gè)結(jié)點(diǎn)至多有m個(gè)子女;
- 非根節(jié)點(diǎn)關(guān)鍵值個(gè)數(shù)范圍:?m/2? - 1 <= k <= m-1
- 相鄰葉子節(jié)點(diǎn)是通過(guò)指針連起來(lái)的,并且是關(guān)鍵字大小排序的。
一顆3階的B+樹(shù)如下:
B+樹(shù)和B-樹(shù)的主要區(qū)別如下:
- B-樹(shù)內(nèi)部節(jié)點(diǎn)是保存數(shù)據(jù)的;而B(niǎo)+樹(shù)內(nèi)部節(jié)點(diǎn)是不保存數(shù)據(jù)的,只作索引作用,它的葉子節(jié)點(diǎn)才保存數(shù)據(jù)。
- B+樹(shù)相鄰的葉子節(jié)點(diǎn)之間是通過(guò)鏈表指針連起來(lái)的,B-樹(shù)卻不是。
- 查找過(guò)程中,B-樹(shù)在找到具體的數(shù)值以后就結(jié)束,而B(niǎo)+樹(shù)則需要通過(guò)索引找到葉子結(jié)點(diǎn)中的數(shù)據(jù)才結(jié)束
- B-樹(shù)中任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中,而B(niǎo)+樹(shù)可以出現(xiàn)多次。
B+樹(shù)的插入
B+樹(shù)插入要記住這幾個(gè)步驟:
- 1.B+樹(shù)插入都是在葉子結(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)開(kāi)始 「分裂」為兩個(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+樹(shù)為例子吧,4階的話,關(guān)鍵值最多3(m-1)個(gè)。假設(shè)插入以下數(shù)據(jù)43,48,36,32,37,49,28.
- 在空樹(shù)中插入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)鍵字都是還沒(méi)滿的,直接插入,如下:
-
最后插入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+樹(shù)的查找
因?yàn)锽+樹(shù)的數(shù)據(jù)都是在葉子節(jié)點(diǎn)上的,內(nèi)部節(jié)點(diǎn)只是指針?biāo)饕淖饔?,因此,查找過(guò)程需要搜索到葉子節(jié)點(diǎn)上。還是以這顆B+樹(shù)為例吧:
B+ 樹(shù)單值查詢
假設(shè)我們要查的值為32.
第一次磁盤(pán) I/O,查找磁盤(pán)塊1,即根節(jié)點(diǎn)(36,43),因?yàn)?2小于36,因此訪問(wèn)根節(jié)點(diǎn)的左邊第一個(gè)孩子節(jié)點(diǎn)
第二次磁盤(pán) I/O, 查找磁盤(pán)塊2,即根節(jié)點(diǎn)的第一個(gè)孩子節(jié)點(diǎn),獲得區(qū)間(28,32),遍歷即可得32.
動(dòng)態(tài)圖如下:
B+ 樹(shù)范圍查詢
假設(shè)我們要查找區(qū)間 [32,40]區(qū)間的值.
第一步先訪問(wèn)根節(jié)點(diǎn),發(fā)現(xiàn)區(qū)間的左端點(diǎn)32小于36,則訪問(wèn)根節(jié)點(diǎn)的第一個(gè)左子樹(shù)(28,32);
第二步訪問(wèn)節(jié)點(diǎn)(28,32),找到32,于是開(kāi)始遍歷鏈表,把[32,40]區(qū)間值找出來(lái),這也是B+樹(shù)比B-樹(shù)高效的地方。
B+樹(shù)的刪除
B+樹(shù)刪除關(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)沒(méi)有多余的關(guān)鍵字,則與兄弟結(jié)點(diǎn)合并。
如果關(guān)鍵字個(gè)數(shù)大于?m/2?,直接刪除即可;
假設(shè)當(dāng)前有這么一顆5階的B+樹(shù)
如果刪除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+樹(shù),
如果刪除15,刪除關(guān)鍵字的結(jié)點(diǎn)只剩1個(gè)關(guān)鍵字,小于?5/2?-1=2,不滿足B+樹(shù)特點(diǎn),但是其兄弟節(jié)點(diǎn)擁有3個(gè)元素(7,8,9),可以借用9過(guò)來(lái),如圖:
在刪除關(guān)鍵字后,如果導(dǎo)致其結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)不足,并且兄弟結(jié)點(diǎn)沒(méi)有得借用的話,需要合并兄弟結(jié)點(diǎn)
以下這顆5階的B+樹(shù):
如果刪除關(guān)鍵字7,刪除關(guān)鍵字的結(jié)點(diǎn)只剩1個(gè)關(guān)鍵字,小于?5/2?-1=2,不滿足B+樹(shù)特點(diǎn),并且兄弟結(jié)點(diǎn)沒(méi)法借用,因此發(fā)生合并,如下:
主要流程醬紫:
- 因?yàn)?被刪掉后,只剩一個(gè)8的關(guān)鍵字,不滿足B+樹(shù)特點(diǎn)(?m/2?-1<=關(guān)鍵字<=m-1)。
- 并且沒(méi)有兄弟結(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)鍵字,也是沒(méi)得借,因此在此合并。
- 被刪關(guān)鍵字結(jié)點(diǎn)的父子節(jié)點(diǎn),也和其兄弟結(jié)點(diǎn)合并后,只剩一個(gè)子樹(shù)分支,因此根節(jié)點(diǎn)(16)也下移了。
所以刪除關(guān)鍵字7后的結(jié)果如下:
B+樹(shù)經(jīng)典面試題
- InnoDB一棵B+樹(shù)可以存放多少行數(shù)據(jù)?
- 為什么索引結(jié)構(gòu)默認(rèn)使用B+樹(shù),而不是hash,二叉樹(shù),紅黑樹(shù),B-樹(shù)?
- B-樹(shù)和B+樹(shù)的區(qū)別
InnoDB一棵B+樹(shù)可以存放多少行數(shù)據(jù)?
這個(gè)問(wèn)題的簡(jiǎn)單回答是:約2千萬(wàn)行。
- 在計(jì)算機(jī)中,磁盤(pán)存儲(chǔ)數(shù)據(jù)最小單元是扇區(qū),一個(gè)扇區(qū)的大小是512字節(jié)。
- 文件系統(tǒng)中,最小單位是塊,一個(gè)塊大小就是4k;
- InnoDB存儲(chǔ)引擎最小儲(chǔ)存單元是頁(yè),一頁(yè)大小就是16k。
因?yàn)锽+樹(shù)葉子存的是數(shù)據(jù),內(nèi)部節(jié)點(diǎn)存的是鍵值+指針。索引組織表通過(guò)非葉子節(jié)點(diǎn)的二分查找法以及指針確定數(shù)據(jù)在哪個(gè)頁(yè)中,進(jìn)而再去數(shù)據(jù)頁(yè)中找到需要的數(shù)據(jù);
假設(shè)B+樹(shù)的高度為2的話,即有一個(gè)根結(jié)點(diǎn)和若干個(gè)葉子結(jié)點(diǎn)。這棵B+樹(shù)的存放總記錄數(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類(lèi)型,長(zhǎng)度為8字節(jié),而指針大小在InnoDB源碼中設(shè)置為6字節(jié),所以就是8+6=14字節(jié),16k/14B =16*1024B/14B = 1170
因此,一棵高度為2的B+樹(shù),能存放1170 * 16=18720條這樣的數(shù)據(jù)記錄。同理一棵高度為3的B+樹(shù),能存放1170 *1170 *16 =21902400,也就是說(shuō),可以存放兩千萬(wàn)左右的記錄。B+樹(shù)高度一般為1-3層,已經(jīng)滿足千萬(wàn)級(jí)別的數(shù)據(jù)存儲(chǔ)。
為什么索引結(jié)構(gòu)默認(rèn)使用B+樹(shù),而不是B-Tree,Hash哈希,二叉樹(shù),紅黑樹(shù)?
簡(jiǎn)單版回答如下:
- Hash哈希,只適合等值查詢,不適合范圍查詢。
- 一般二叉樹(shù),可能會(huì)特殊化為一個(gè)鏈表,相當(dāng)于全表掃描。
- 紅黑樹(shù),是一種特化的平衡二叉樹(shù),MySQL 數(shù)據(jù)量很大的時(shí)候,索引的體積也會(huì)很大,內(nèi)存放不下的而從磁盤(pán)讀取,樹(shù)的層次太高的話,讀取磁盤(pán)的次數(shù)就多了。
- B-Tree,葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都保存數(shù)據(jù),相同的數(shù)據(jù)量,B+樹(shù)更矮壯,也是就說(shuō),相同的數(shù)據(jù)量,B+樹(shù)數(shù)據(jù)結(jié)構(gòu),查詢磁盤(pán)的次數(shù)會(huì)更少。
B-樹(shù)和B+樹(shù)的區(qū)別
- B-樹(shù)內(nèi)部節(jié)點(diǎn)是保存數(shù)據(jù)的;而B(niǎo)+樹(shù)內(nèi)部節(jié)點(diǎn)是不保存數(shù)據(jù)的,只作索引作用,它的葉子節(jié)點(diǎn)才保存數(shù)據(jù)。
- B+樹(shù)相鄰的葉子節(jié)點(diǎn)之間是通過(guò)鏈表指針連起來(lái)的,B-樹(shù)卻不是。
- 查找過(guò)程中,B-樹(shù)在找到具體的數(shù)值以后就結(jié)束,而B(niǎo)+樹(shù)則需要通過(guò)索引找到葉子結(jié)點(diǎn)中的數(shù)據(jù)才結(jié)束
- B-樹(shù)中任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中,而B(niǎo)+樹(shù)可以出現(xiàn)多次。
參考與感謝
- B+樹(shù)看這一篇就夠了 [1]
- B樹(shù)和B+樹(shù)的插入、刪除圖文詳解 [2]
- InnoDB一棵B+樹(shù)可以存放多少行數(shù)據(jù)? [3]
Reference
[1]B+樹(shù)看這一篇就夠了: https://zhuanlan.zhihu.com/p/149287061
[2]B樹(shù)和B+樹(shù)的插入、刪除圖文詳解: https://www.cnblogs.com/nullzx/p/8729425.html
[3]InnoDB一棵B+樹(shù)可以存放多少行數(shù)據(jù)?: https://www.cnblogs.com/leefreeman/p/8315844.html
免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn),不代表本平臺(tái)立場(chǎng),如有問(wèn)題,請(qǐng)聯(lián)系我們,謝謝!