MySQL中索引的底層實(shí)現(xiàn)原理是什么

本篇文章為大家展示了MySQL中索引的底層實(shí)現(xiàn)原理是什么，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。

　　MySQL索引底層實(shí)現(xiàn)原理

　　MySQL官方對(duì)索引的定義為：索引(Index)是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。提取句子主干，就可以得到索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)。

　　我們知道，數(shù)據(jù)庫(kù)查詢是數(shù)據(jù)庫(kù)的最主要功能之一。我們都希望查詢數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者會(huì)從查詢算法的角度進(jìn)行優(yōu)化。最基本的查詢算法當(dāng)然是順序查找(linear search)，這種復(fù)雜度為O(n)的算法在數(shù)據(jù)量很大時(shí)顯然是糟糕的，好在計(jì)算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法，例如二分查找(binary search)、二叉樹(shù)查找(binary tree search)等。

　　如果稍微分析一下會(huì)發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹(shù)查找只能應(yīng)用于二叉查找樹(shù)上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)(例如，理論上不可能同時(shí)將兩列都按順序進(jìn)行組織)，所以，在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向)數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

　　上圖展示了一種可能的索引方式。左邊是數(shù)據(jù)表，一共有兩列七條記錄，最左邊的是數(shù)據(jù)記錄的物理地址(注意邏輯上相鄰的記錄在磁盤(pán)上也并不是一定物理相鄰的)。為了加快Col2的查找，可以維護(hù)一個(gè)右邊所示的二叉查找樹(shù)，每個(gè)節(jié)點(diǎn)分別包含索引鍵值和一個(gè)指向?qū)?yīng)數(shù)據(jù)記錄物理地址的指針，這樣就可以運(yùn)用二叉查找在 ( 2) 的復(fù)雜度內(nèi)獲取到相應(yīng)數(shù)據(jù)。

　　雖然這是一個(gè)貨真價(jià)實(shí)的索引，但是實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)幾乎沒(méi)有使用二叉查找樹(shù)或其進(jìn)化品種紅黑樹(shù)(red-black tree)實(shí)現(xiàn)的，原因會(huì)在下文介紹。

　　二叉排序樹(shù)

　　在介紹B樹(shù)之前，先來(lái)看另一棵神奇的樹(shù)——二叉排序樹(shù)(Binary Sort Tree)，首先它是一棵樹(shù)，“二叉”這個(gè)描述已經(jīng)很明顯了，就是樹(shù)上的一根樹(shù)枝開(kāi)兩個(gè)叉，于是遞歸下來(lái)就是二叉樹(shù)了(下圖所示)，而這棵樹(shù)上的節(jié)點(diǎn)是已經(jīng)排好序的，具體的排序規(guī)則如下：

　　若左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值;

　　若右子樹(shù)不空，則右字?jǐn)?shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值;

　　它的左、右子樹(shù)也分別為二叉排序數(shù)(遞歸定義)。

　　從圖中可以看出，二叉排序樹(shù)組織數(shù)據(jù)時(shí)，用于查找是比較方便的，因?yàn)槊看谓?jīng)過(guò)一次節(jié)點(diǎn)時(shí)，最多可以減少一半的可能，不過(guò)極端情況會(huì)出現(xiàn)所有節(jié)點(diǎn)都位于同一側(cè)，直觀上看就是一條直線，那么這種查詢的效率就比較低了，因此需要對(duì)二叉樹(shù)左右子樹(shù)的高度進(jìn)行平衡化處理，于是就有了平衡二叉樹(shù)(Balenced Binary Tree)。

　　所謂“平衡”，說(shuō)的是這棵樹(shù)的各個(gè)分支的高度是均勻的，它的左子樹(shù)和右子樹(shù)的高度之差絕對(duì)值小于1，這樣就不會(huì)出現(xiàn)一條支路特別長(zhǎng)的情況。于是，在這樣的平衡樹(shù)中進(jìn)行查找時(shí)，總共比較節(jié)點(diǎn)的次數(shù)不超過(guò)樹(shù)的高度，這就確保了查詢的效率(時(shí)間復(fù)雜度為O(logn))

　　B樹(shù)

　　還是直接看圖比較清楚，圖中所示，B樹(shù)事實(shí)上是一種平衡的多叉查找樹(shù)，也就是說(shuō)最多可以開(kāi)m個(gè)叉(m>=2)，我們稱之為m階b樹(shù)，為了體現(xiàn)本博客的良心之處，不同于其他地方都能看到2階B樹(shù)，這里特意畫(huà)了一棵5階B樹(shù) 。

　　總的來(lái)說(shuō)，m階B樹(shù)滿足以下條件：

　　每個(gè)節(jié)點(diǎn)至多可以擁有m棵子樹(shù)。

　　根節(jié)點(diǎn)，只有至少有2個(gè)節(jié)點(diǎn)(要么極端情況，就是一棵樹(shù)就一個(gè)根節(jié)點(diǎn)，單細(xì)胞生物，即是根，也是葉，也是樹(shù))。

　　非根非葉的節(jié)點(diǎn)至少有的Ceil(m/2)個(gè)子樹(shù)(Ceil表示向上取整，圖中5階B樹(shù)，每個(gè)節(jié)點(diǎn)至少有3個(gè)子樹(shù)，也就是至少有3個(gè)叉)。

　　非葉節(jié)點(diǎn)中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示該節(jié)點(diǎn)中保存的關(guān)鍵字個(gè)數(shù)，K為關(guān)鍵字且Ki

　　從根到葉子的每一條路徑都有相同的長(zhǎng)度，也就是說(shuō)，葉子節(jié)在相同的層，并且這些節(jié)點(diǎn)不帶信息，實(shí)際上這些節(jié)點(diǎn)就表示找不到指定的值，也就是指向這些節(jié)點(diǎn)的指針為空。

　　B樹(shù)的查詢過(guò)程和二叉排序樹(shù)比較類似，從根節(jié)點(diǎn)依次比較每個(gè)結(jié)點(diǎn)， 因?yàn)槊總€(gè)節(jié)點(diǎn)中的關(guān)鍵字和左右子樹(shù)都是有序的 ，所以只要比較節(jié)點(diǎn)中的關(guān)鍵字，或者沿著指針就能很快地找到指定的關(guān)鍵字，如果查找失敗，則會(huì)返回葉子節(jié)點(diǎn)，即空指針。

　　從根節(jié)點(diǎn)P開(kāi)始，K的位置在P之前，進(jìn)入左側(cè)指針。

　　左子樹(shù)中，依次比較C、F、J、M，發(fā)現(xiàn)K在J和M之間。

　　沿著J和M之間的指針，繼續(xù)訪問(wèn)子樹(shù)，并依次進(jìn)行比較，發(fā)現(xiàn)第一個(gè)關(guān)鍵字K即為指定查找的值。

　　B樹(shù)搜索的簡(jiǎn)單偽算法如下：

　　BTree_Search(node, key) {

　　if(node == null) return null;

　　foreach(node.key)

　　{

　　if(node.key[i] == key) return node.data[i];

　　if(node.key[i] > key) return BTree_Search(point[i]->node);

　　}

　　return BTree_Search(point[i+1]->node);

　　}

　　data = BTree_Search(root, my_key);

　　B樹(shù)的特點(diǎn)可以總結(jié)為如下：

　　關(guān)鍵字集合分布在整顆樹(shù)中。

　　任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)節(jié)點(diǎn)中。

　　搜索有可能在非葉子節(jié)點(diǎn)結(jié)束。

　　其搜索性能等價(jià)于在關(guān)鍵字集合內(nèi)做一次二分查找。

　　B樹(shù)在插入刪除新的數(shù)據(jù)記錄會(huì)破壞B-Tree的性質(zhì)，因?yàn)樵诓迦雱h除時(shí)，需要對(duì)樹(shù)進(jìn)行一個(gè)分裂、合并、轉(zhuǎn)移等操作以保持B-Tree性質(zhì)。

　　Plus版 — B+樹(shù)

　　作為B樹(shù)的加強(qiáng)版，B+樹(shù)與B樹(shù)的差異在于:

　　有n棵子樹(shù)的節(jié)點(diǎn)含有n個(gè)關(guān)鍵字(也有認(rèn)為是n-1個(gè)關(guān)鍵字)。

　　所有的關(guān)鍵字全部存儲(chǔ)在葉子節(jié)點(diǎn)上，且葉子節(jié)點(diǎn)本身根據(jù)關(guān)鍵字自小而大順序連接。

　　非葉子節(jié)點(diǎn)可以看成索引部分，節(jié)點(diǎn)中僅含有其子樹(shù)(根節(jié)點(diǎn))中的最大(或最小)關(guān)鍵字。

　　B+樹(shù)的查找過(guò)程，與B樹(shù)類似，只不過(guò)查找時(shí)，如果在非葉子節(jié)點(diǎn)上的關(guān)鍵字等于給定值，并不終止，而是繼續(xù)沿著指針直到葉子節(jié)點(diǎn)位置。因此在B+樹(shù)，不管查找成功與否，每次查找都是走了一條從根到葉子節(jié)點(diǎn)的路徑。

　　B+樹(shù)的特性如下：

　　所有關(guān)鍵字都存儲(chǔ)在葉子節(jié)上，且鏈表中的關(guān)鍵字恰好是有序的。

　　不可能非葉子節(jié)點(diǎn)命中返回。

　　非葉子節(jié)點(diǎn)相當(dāng)于葉子節(jié)點(diǎn)的索引，葉子節(jié)點(diǎn)相當(dāng)于是存儲(chǔ)(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層。

　　更適合文件索引系統(tǒng)。

　　帶有順序訪問(wèn)指針的B+Tree

　　一般在數(shù)據(jù)庫(kù)系統(tǒng)或文件系統(tǒng)中使用的B+Tree結(jié)構(gòu)都在經(jīng)典B+Tree的基礎(chǔ)上進(jìn)行了優(yōu)化，增加了順序訪問(wèn)指針。

　　如上圖所示，在B+Tree的每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，就形成了帶有順序訪問(wèn)指針的B+Tree。做這個(gè)優(yōu)化的目的是為了提高區(qū)間訪問(wèn)的性能，例如圖4中如果要查詢key為從18到49的所有數(shù)據(jù)記錄，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢效率。

　　二叉樹(shù)與紅黑樹(shù)的比較

　　從上面我們發(fā)現(xiàn)，紅黑樹(shù)相比較于二叉樹(shù)又進(jìn)步了一些，但紅黑樹(shù)還是有些問(wèn)題：那就是數(shù)據(jù)量大的話，紅黑樹(shù)的深度會(huì)很深，也就是說(shuō)深度不可控，這樣一來(lái)查找數(shù)據(jù)還是會(huì)很耗時(shí)。

　　從上面看，我們發(fā)現(xiàn)BTree又進(jìn)步了一些，查詢速度提高，存儲(chǔ)容量也沒(méi)影響到。當(dāng)然有人可能會(huì)這樣想，那我們?yōu)槭裁床话褦?shù)據(jù)全部都存在一個(gè)節(jié)點(diǎn)，這樣深度不就是1了嗎?

　　當(dāng)然不行了!java拿取數(shù)據(jù)一般是這樣的：java程序-->CPU--->內(nèi)存---->硬盤(pán)，而內(nèi)存與硬盤(pán)的交互是有大小限制的，是一頁(yè)數(shù)據(jù)4k左右，所以不能把所有數(shù)據(jù)都放在一個(gè)節(jié)點(diǎn)來(lái)獲取，一般來(lái)說(shuō)節(jié)點(diǎn)會(huì)盡量預(yù)存4K容量。

　　看到這里，我們知道(4K=節(jié)點(diǎn);節(jié)點(diǎn)=小節(jié)點(diǎn)*小節(jié)點(diǎn)的容量)一個(gè)節(jié)點(diǎn)是4K，而節(jié)點(diǎn)內(nèi)有幾個(gè)小節(jié)點(diǎn)，那么也就是說(shuō)，只要我們每個(gè)的小節(jié)點(diǎn)的data容量越小，那么可以存的節(jié)點(diǎn)也就可以更多。

　　B+Tree通過(guò)把data不放在非葉子節(jié)點(diǎn)來(lái)增加度(小節(jié)點(diǎn))，一般會(huì)一百個(gè)以上使得深度是3~5，從而減少查詢次數(shù)。并且，葉子節(jié)點(diǎn)之間會(huì)有指針，數(shù)據(jù)又是遞增的，這使得我們范圍查找可以通過(guò)指針連接查找，而不再?gòu)纳厦婀?jié)點(diǎn)往下一個(gè)個(gè)找。

上述內(nèi)容就是MySQL中索引的底層實(shí)現(xiàn)原理是什么，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。