快捷導(dǎo)航

教你通過(guò)B+Tree平衡多叉樹(shù)理解InnoDB引擎的聚集和非聚集索引

更新時(shí)間：2022年01月27日 15:56:26 作者：CaptainCats

大家都知道B+Tree是從二叉樹(shù)演化而來(lái)，在這之前我們來(lái)先了解二叉樹(shù)、平衡二叉樹(shù)、平衡多叉樹(shù)，這篇文章主要介紹了通過(guò)B+Tree平衡多叉樹(shù)理解InnoDB引擎的聚集和非聚集索引,需要的朋友可以參考下

InnoDB引擎是通過(guò)B+Tree實(shí)現(xiàn)索引結(jié)構(gòu)

因?yàn)锽+Tree是從二叉樹(shù)演化而來(lái)，在這之前我們來(lái)先了解二叉樹(shù)、平衡二叉樹(shù)、平衡多叉樹(shù)。

二叉樹(shù)（Binary Tree）

簡(jiǎn)介：每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。
它有一個(gè)特點(diǎn)：左子樹(shù)的鍵值小于根的鍵值，右子樹(shù)的鍵值大于根的鍵值。

如下圖（圖1）所示就是一個(gè)二叉樹(shù)：

在這里插入圖片描述

對(duì)于該二叉樹(shù)，假設(shè)我們要查找鍵值為5的節(jié)點(diǎn)：

首先從根節(jié)點(diǎn)開(kāi)始，
第一次查找結(jié)果為6判斷5小于6；
往下查找6的左節(jié)點(diǎn)，結(jié)果為3判斷5大于3；
往下查找3的右節(jié)點(diǎn)，結(jié)果為5。
一共查找了3次。

我們可以發(fā)現(xiàn)：

深度為1的節(jié)點(diǎn)需要查找一次，這樣的節(jié)點(diǎn)有1個(gè)需要查找1次；
深度為2的節(jié)點(diǎn)需要查找2次，這樣的節(jié)點(diǎn)有2個(gè)共需要查找4次；
深度為3的節(jié)點(diǎn)需要查找3次，這樣的節(jié)點(diǎn)有3個(gè)共需要查找9次。
如果要將所有節(jié)點(diǎn)全部查找遍歷一共需要查找1+4+9=14次。

二叉樹(shù)可以任意地構(gòu)造，同樣是2、3、5、6、7、8這幾個(gè)數(shù)字，還可以按照下圖（圖2）的方式構(gòu)造：

在這里插入圖片描述

如果要遍歷該二叉樹(shù)所有節(jié)點(diǎn)一共需要查找1+2+3+4+5+5=20次，這樣效率相對(duì)來(lái)說(shuō)就比較低了。
若要最大程度地減少二叉樹(shù)的查找次數(shù)，需要二叉樹(shù)盡可能地趨近于平衡二叉樹(shù)。

平衡二叉樹(shù)（AVL Tree）

簡(jiǎn)介：在滿足二叉樹(shù)的前提下任一節(jié)點(diǎn)上左右兩個(gè)子樹(shù)的深度差不超過(guò)1。

下面兩個(gè)二叉樹(shù)，左邊的是平衡二叉樹(shù)，右邊的是非平衡二叉樹(shù)：

在這里插入圖片描述

如果在平衡二叉樹(shù)中插入或刪除節(jié)點(diǎn)，可能會(huì)導(dǎo)致平衡二叉樹(shù)失衡。
這種失去平衡的二叉樹(shù)可以概括為四種姿態(tài)：LL（左左）、RR（右右）、LR（左右）、RL（右左）。

它們的示意圖如下：

在這里插入圖片描述

這四種失去平衡的姿態(tài)都有各自的定義：
LL：LeftLeft，也稱(chēng)“左左”。
插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的左孩子（Left Child）的左孩子（Left Child）還有非空節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的左子樹(shù)高度比右子樹(shù)高度高2，AVL樹(shù)失去平衡。
RR：RightRight，也稱(chēng)“右右”。
插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的右孩子（Right Child）的右孩子（Right Child）還有非空節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的右子樹(shù)高度比左子樹(shù)高度高2，AVL樹(shù)失去平衡。
LR：LeftRight，也稱(chēng)“左右”。
插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的左孩子（Left Child）的右孩子（Right Child）還有非空節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的左子樹(shù)高度比右子樹(shù)高度高2，AVL樹(shù)失去平衡。
RL：RightLeft，也稱(chēng)“右左”。
插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的右孩子（Right Child）的左孩子（Left Child）還有非空節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的右子樹(shù)高度比左子樹(shù)高度高2，AVL樹(shù)失去平衡。
平衡二叉樹(shù)失衡后，可以通過(guò)旋轉(zhuǎn)二叉樹(shù)使其恢復(fù)平衡。具體這四種失去平衡姿態(tài)情況下對(duì)應(yīng)的旋轉(zhuǎn)方法，請(qǐng)移步BTree和B+Tree詳解，里面有十分詳細(xì)的講解，這里不再贅述。

平衡多叉樹(shù)（B-Tree）

B-Tree是為磁盤(pán)等設(shè)備設(shè)計(jì)的一種平衡查找樹(shù)，因此在講B-Tree之前先了解下磁盤(pán)的相關(guān)知識(shí)。

系統(tǒng)從磁盤(pán)讀取數(shù)據(jù)到內(nèi)存時(shí)是以磁盤(pán)塊（block）為基本單位的，位于同一個(gè)磁盤(pán)塊中的數(shù)據(jù)會(huì)被一次性讀取出來(lái)，而不是需要什么取什么。

InnoDB存儲(chǔ)引擎中有頁(yè)（Page）的概念，頁(yè)是其磁盤(pán)管理的最小單位。InnoDB存儲(chǔ)引擎中默認(rèn)每個(gè)頁(yè)的大小為16KB，可通過(guò)參數(shù)innodb_page_size將頁(yè)的大小設(shè)置為4K、8K、16K，
在MySQL中可通過(guò)如下命令查看頁(yè)的大小：

mysql> show variables like 'innodb_page_size';

而系統(tǒng)一個(gè)磁盤(pán)塊的存儲(chǔ)空間往往沒(méi)有這么大，因此InnoDB每次申請(qǐng)磁盤(pán)空間時(shí)都會(huì)是若干個(gè)地址連續(xù)磁盤(pán)塊（成為大磁盤(pán)塊即頁(yè)，接下來(lái)的部分如無(wú)特殊說(shuō)明，所說(shuō)磁盤(pán)塊即是InnoDB的頁(yè)）來(lái)達(dá)到頁(yè)的大小16KB。
InnoDB在把磁盤(pán)數(shù)據(jù)讀取到內(nèi)存時(shí)會(huì)以頁(yè)為基本單位。

B-Tree結(jié)構(gòu)的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤(pán)塊。
為了描述B-Tree，首先定義一條記錄為一個(gè)對(duì)象[key, data]，key為記錄的鍵值，對(duì)應(yīng)表中的主鍵，data為一行記錄中除主鍵外的數(shù)據(jù)。對(duì)于不同的記錄，key值互不相同。

m（整數(shù)）階（寬度為m，m>2）B-Tree滿足以下條件：

每個(gè)節(jié)點(diǎn)占用一個(gè)磁盤(pán)塊；
節(jié)點(diǎn)（除葉節(jié)點(diǎn)外）包含指針、鍵值（關(guān)鍵字）、數(shù)據(jù)三種元素，葉節(jié)點(diǎn)不包含其它節(jié)點(diǎn)的關(guān)鍵字信息：即指針；
所有葉子節(jié)點(diǎn)都在同一層；
節(jié)點(diǎn)擁有n個(gè)按照升序排序的不連續(xù)關(guān)鍵字，n在[m/2, m-1]閉區(qū)間內(nèi)為整數(shù)；
除葉節(jié)點(diǎn)外，n個(gè)關(guān)鍵字劃分出n+1個(gè)范圍域?qū)?yīng)n+1個(gè)指針。指針指向子樹(shù)關(guān)鍵字的范圍域，
比如：以根節(jié)點(diǎn)為例，關(guān)鍵字為17和35，p1指針指向的子樹(shù)的數(shù)據(jù)范圍域小于17，p2指針指向的子樹(shù)的數(shù)據(jù)范圍域在(17, 35)開(kāi)區(qū)間內(nèi)，p3指針指向的子樹(shù)的數(shù)據(jù)范圍域大于35。

見(jiàn)下圖：
磁盤(pán)塊3也是包含三個(gè)指針，只是p1和p3的指向磁盤(pán)塊沒(méi)有畫(huà)出來(lái)。

在這里插入圖片描述

如果要查找關(guān)鍵字29，
那么首先會(huì)把磁盤(pán)塊1由磁盤(pán)加載到內(nèi)存，此時(shí)發(fā)生一次IO，
在內(nèi)存中用二分法查找確定29在17和35之間，鎖定磁盤(pán)塊1的P2指針，內(nèi)存時(shí)間因?yàn)榉浅６蹋ㄏ啾却疟P(pán)的IO）可以忽略不計(jì)，
通過(guò)磁盤(pán)塊1的P2指針的磁盤(pán)地址把磁盤(pán)塊3由磁盤(pán)加載到內(nèi)存，發(fā)生第二次IO，
29在26和30之間，鎖定磁盤(pán)塊3的P2指針，
通過(guò)指針加載磁盤(pán)塊8到內(nèi)存，發(fā)生第三次IO，
同時(shí)內(nèi)存中做二分查找找到29，結(jié)束查詢(xún)，總計(jì)三次IO。

（
基礎(chǔ)·磁盤(pán)IO與預(yù)讀：
磁盤(pán)讀取依靠的是機(jī)械運(yùn)動(dòng)，分為尋道時(shí)間、旋轉(zhuǎn)延遲、傳輸時(shí)間三個(gè)部分，
這三個(gè)部分耗時(shí)相加就是一次磁盤(pán)IO的時(shí)間，大概9ms左右。這個(gè)成本是訪問(wèn)內(nèi)存的十萬(wàn)倍左右；
正是由于磁盤(pán)IO是非常昂貴的操作，所以計(jì)算機(jī)操作系統(tǒng)對(duì)此做了優(yōu)化：
預(yù)讀：每一次IO時(shí)，不僅僅把當(dāng)前磁盤(pán)地址的數(shù)據(jù)加載到內(nèi)存，同時(shí)也把相鄰數(shù)據(jù)也加載到內(nèi)存緩沖區(qū)中。
因?yàn)榫植款A(yù)讀原理說(shuō)明，當(dāng)訪問(wèn)一個(gè)地址數(shù)據(jù)的時(shí)候，與其相鄰的數(shù)據(jù)很快也會(huì)被訪問(wèn)到。
每次磁盤(pán)IO讀取的數(shù)據(jù)我們稱(chēng)之為一頁(yè)（page）。一頁(yè)的大小與操作系統(tǒng)有關(guān)，一般為4k或者8k。這也就意味著讀取一頁(yè)內(nèi)數(shù)據(jù)的時(shí)候，實(shí)際上發(fā)生了一次磁盤(pán)IO。
）

我們?cè)賮?lái)看二叉樹(shù)的查找過(guò)程

定義一個(gè)樹(shù)高為4的二叉樹(shù)，查找值為10：

在這里插入圖片描述

第一次磁盤(pán)IO：

在這里插入圖片描述

第二次磁盤(pán)IO：

在這里插入圖片描述

第三次磁盤(pán)IO：

在這里插入圖片描述

第四次磁盤(pán)IO：

在這里插入圖片描述

可以看到最壞情況下，磁盤(pán)的IO次數(shù)等于VAL樹(shù)的高度。

二叉樹(shù)深度和節(jié)點(diǎn)數(shù)的關(guān)系：

在這里插入圖片描述

相比VAL二叉樹(shù)，B-Tree可以大大減少磁盤(pán)IO次數(shù)。

B+Tree

B+tree是基于B-tree的變體。

B-Tree結(jié)構(gòu)中每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key值，還有data值，而每一個(gè)節(jié)點(diǎn)的存儲(chǔ)空間是有限的，
如果data數(shù)據(jù)比較大會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)能存儲(chǔ)的key的數(shù)量變少，導(dǎo)致數(shù)據(jù)量很大時(shí)B-Tree的深度較大，增大查詢(xún)時(shí)的磁盤(pán)I/O次數(shù)，進(jìn)而影響查詢(xún)效率。
在B+Tree中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都存放在同一層的葉子節(jié)點(diǎn)上，而非葉子節(jié)點(diǎn)上只存儲(chǔ)key值信息，這樣可以大大加大每個(gè)節(jié)點(diǎn)存儲(chǔ)的key值數(shù)量，降低B+Tree的高度。

在這里插入圖片描述

和B-Tree不同，由于它的非葉子節(jié)點(diǎn)不存儲(chǔ)data信息，所以相同的鍵值會(huì)和data一起，出現(xiàn)在葉子節(jié)點(diǎn)中。
以磁盤(pán)塊3的p2指針為例，指針指向的子樹(shù)的數(shù)據(jù)范圍域就是在在[36, 79)左開(kāi)右閉區(qū)間內(nèi)。

InnoDB存儲(chǔ)引擎中頁(yè)的大小為16KB，一般表的主鍵類(lèi)型為INT（占用4個(gè)字節(jié)）或BIGINT（占用8個(gè)字節(jié)），指針類(lèi)型也一般為4或8個(gè)字節(jié)，
一個(gè)頁(yè)（B+Tree中的一個(gè)節(jié)點(diǎn)）中大概能存儲(chǔ)16KB/(8B+8B)=1K個(gè)鍵值（為方便計(jì)算，這里的K取值為[10]^3）。
也就是說(shuō)一個(gè)深度為3的B+Tree索引大概可以維護(hù)10^3 * 10^3 * 10^3 = 10億條記錄。

實(shí)際情況中每個(gè)節(jié)點(diǎn)可能不能填充滿，因此在數(shù)據(jù)庫(kù)中，B+Tree的高度一般都在2~4層。
mysql的InnoDB存儲(chǔ)引擎在設(shè)計(jì)時(shí)是將根節(jié)點(diǎn)常駐內(nèi)存的，也就是說(shuō)查找某一鍵值的行記錄時(shí)最多只需要1~3次磁盤(pán)I/O操作。

聚集和非聚集索引

到這兒，再來(lái)理解聚集和非聚集索引就比較簡(jiǎn)單了。

聚集索引（clustered index）

通常，聚集索引是主鍵的同義詞。一個(gè)表中只能擁有一個(gè)聚集索引。
聚集索引的邏輯順序與數(shù)據(jù)庫(kù)表中記錄在磁盤(pán)上的排列順序一致。通俗來(lái)講就是，聚集索引葉子節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)包含表中一條記錄完整的信息。找到鍵值key就找到了整條數(shù)據(jù)。

非聚集索引（secondary index）

非聚集索引相對(duì)來(lái)說(shuō)就不是那么好理解一點(diǎn)。
因?yàn)榍懊嫖覀冎v到的關(guān)鍵值key對(duì)應(yīng)的都是數(shù)據(jù)庫(kù)中唯一的一條記錄，而非聚集索引不一樣，它的關(guān)鍵值key無(wú)法確定唯一一條記錄，多條記錄的key值可能會(huì)相同。
非聚集索引是通過(guò)溢出頁(yè)來(lái)處理這種情況的，當(dāng)多條記錄對(duì)應(yīng)某個(gè)同一關(guān)鍵值key時(shí)，分配出一個(gè)溢出頁(yè)，
用來(lái)存放重復(fù)鍵值及其對(duì)應(yīng)記錄的偏移量（該條記錄在磁盤(pán)上的實(shí)際物理位置）。和HashMap解決Hash key沖突類(lèi)似。
非聚集索引維護(hù)了表中記錄的邏輯順序，但是它的葉子節(jié)點(diǎn)存儲(chǔ)的是表中的記錄在數(shù)據(jù)頁(yè)中的指針，相比聚集索引會(huì)多一次磁盤(pán)IO。

以上見(jiàn)解如有不當(dāng)之處，請(qǐng)予指正。

參考文章：
過(guò)來(lái)啊小蓮：BTree和B+Tree詳解
lbcBoy：索引原理-BTree講解

還有兩篇找不到了，找齊之后會(huì)在這里補(bǔ)上。

補(bǔ)充參考文章：
SeedQi：B-Tree詳解

到此這篇關(guān)于通過(guò)B+Tree平衡多叉樹(shù)理解InnoDB引擎的聚集和非聚集索引的文章就介紹到這了,更多相關(guān)B+Tree平衡多叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！