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

易門ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為成都創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：13518219792（備注：SSL證書合作）期待與您的合作！

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

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

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

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

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

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

二叉排序樹

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

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

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

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

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

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

B樹

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

總的來說，m階B樹滿足以下條件：

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

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

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

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

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

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

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

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

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

B樹搜索的簡單偽算法如下：

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樹的特點(diǎn)可以總結(jié)為如下：

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

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

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

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

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

Plus版 — B+樹

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

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

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

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

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

B+樹的特性如下：

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

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

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

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

帶有順序訪問指針的B+Tree

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

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

二叉樹與紅黑樹的比較

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

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

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

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

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

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

文章標(biāo)題：MySQL中索引的底層實(shí)現(xiàn)原理是什么
標(biāo)題來源：http://chinadenli.net/article28/pdsecp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、電子商務(wù)、響應(yīng)式網(wǎng)站、網(wǎng)站導(dǎo)航、標(biāo)簽優(yōu)化、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)