共計 3377 個字符，預(yù)計需要花費 9 分鐘才能閱讀完成。
本篇文章為大家展示了 MySQL 中索引的底層實現(xiàn)原理是什么，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
MySQL 索引底層實現(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è)計者會從查詢算法的角度進行優(yōu)化。最基本的查詢算法當然是順序查找 (linear search)，這種復(fù)雜度為 O(n) 的算法在數(shù)據(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) (例如，理論上不可能同時將兩列都按順序進行組織)，所以，在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向) 數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。
上圖展示了一種可能的索引方式。左邊是數(shù)據(jù)表，一共有兩列七條記錄，最左邊的是數(shù)據(jù)記錄的物理地址(注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的)。為了加快 Col2 的查找，可以維護一個右邊所示的二叉查找樹，每個節(jié)點分別包含索引鍵值和一個指向?qū)?yīng)數(shù)據(jù)記錄物理地址的指針，這樣就可以運用二叉查找在 (2) 的復(fù)雜度內(nèi)獲取到相應(yīng)數(shù)據(jù)。
雖然這是一個貨真價實的索引，但是實際的數(shù)據(jù)庫系統(tǒng)幾乎沒有使用二叉查找樹或其進化品種紅黑樹 (red-black tree) 實現(xiàn)的，原因會在下文介紹。
二叉排序樹
在介紹 B 樹之前，先來看另一棵神奇的樹——二叉排序樹(Binary Sort Tree)，首先它是一棵樹，“二叉”這個描述已經(jīng)很明顯了，就是樹上的一根樹枝開兩個叉，于是遞歸下來就是二叉樹了(下圖所示)，而這棵樹上的節(jié)點是已經(jīng)排好序的，具體的排序規(guī)則如下：
若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值;
若右子樹不空，則右字數(shù)上所有節(jié)點的值均大于它的根節(jié)點的值;
它的左、右子樹也分別為二叉排序數(shù)(遞歸定義)。
從圖中可以看出，二叉排序樹組織數(shù)據(jù)時，用于查找是比較方便的，因為每次經(jīng)過一次節(jié)點時，最多可以減少一半的可能，不過極端情況會出現(xiàn)所有節(jié)點都位于同一側(cè)，直觀上看就是一條直線，那么這種查詢的效率就比較低了，因此需要對二叉樹左右子樹的高度進行平衡化處理，于是就有了平衡二叉樹(Balenced Binary Tree)。
所謂“平衡”，說的是這棵樹的各個分支的高度是均勻的，它的左子樹和右子樹的高度之差絕對值小于 1，這樣就不會出現(xiàn)一條支路特別長的情況。于是，在這樣的平衡樹中進行查找時，總共比較節(jié)點的次數(shù)不超過樹的高度，這就確保了查詢的效率(時間復(fù)雜度為 O(logn))
B 樹
還是直接看圖比較清楚，圖中所示，B 樹事實上是一種平衡的多叉查找樹，也就是說最多可以開 m 個叉(m =2)，我們稱之為 m 階 b 樹，為了體現(xiàn)本博客的良心之處，不同于其他地方都能看到 2 階 B 樹，這里特意畫了一棵 5 階 B 樹。
總的來說，m 階 B 樹滿足以下條件：
每個節(jié)點至多可以擁有 m 棵子樹。
根節(jié)點，只有至少有 2 個節(jié)點(要么極端情況，就是一棵樹就一個根節(jié)點，單細胞生物，即是根，也是葉，也是樹)。
非根非葉的節(jié)點至少有的 Ceil(m/2)個子樹(Ceil 表示向上取整，圖中 5 階 B 樹，每個節(jié)點至少有 3 個子樹，也就是至少有 3 個叉)。
非葉節(jié)點中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中 n 表示該節(jié)點中保存的關(guān)鍵字個數(shù)，K 為關(guān)鍵字且 Ki
從根到葉子的每一條路徑都有相同的長度，也就是說，葉子節(jié)在相同的層，并且這些節(jié)點不帶信息，實際上這些節(jié)點就表示找不到指定的值，也就是指向這些節(jié)點的指針為空。
B 樹的查詢過程和二叉排序樹比較類似，從根節(jié)點依次比較每個結(jié)點，因為每個節(jié)點中的關(guān)鍵字和左右子樹都是有序的，所以只要比較節(jié)點中的關(guān)鍵字，或者沿著指針就能很快地找到指定的關(guān)鍵字，如果查找失敗，則會返回葉子節(jié)點，即空指針。
從根節(jié)點 P 開始，K 的位置在 P 之前，進入左側(cè)指針。
左子樹中，依次比較 C、F、J、M，發(fā)現(xiàn) K 在 J 和 M 之間。
沿著 J 和 M 之間的指針，繼續(xù)訪問子樹，并依次進行比較，發(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 樹的特點可以總結(jié)為如下：
關(guān)鍵字集合分布在整顆樹中。
任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個節(jié)點中。
搜索有可能在非葉子節(jié)點結(jié)束。
其搜索性能等價于在關(guān)鍵字集合內(nèi)做一次二分查找。
B 樹在插入刪除新的數(shù)據(jù)記錄會破壞 B -Tree 的性質(zhì)，因為在插入刪除時，需要對樹進行一個分裂、合并、轉(zhuǎn)移等操作以保持 B -Tree 性質(zhì)。
Plus 版 — B+ 樹
作為 B 樹的加強版，B+ 樹與 B 樹的差異在于:
有 n 棵子樹的節(jié)點含有 n 個關(guān)鍵字(也有認為是 n - 1 個關(guān)鍵字)。
所有的關(guān)鍵字全部存儲在葉子節(jié)點上，且葉子節(jié)點本身根據(jù)關(guān)鍵字自小而大順序連接。
非葉子節(jié)點可以看成索引部分，節(jié)點中僅含有其子樹 (根節(jié)點) 中的最大 (或最小) 關(guān)鍵字。
B+ 樹的查找過程，與 B 樹類似，只不過查找時，如果在非葉子節(jié)點上的關(guān)鍵字等于給定值，并不終止，而是繼續(xù)沿著指針直到葉子節(jié)點位置。因此在 B + 樹，不管查找成功與否，每次查找都是走了一條從根到葉子節(jié)點的路徑。
B+ 樹的特性如下：
所有關(guān)鍵字都存儲在葉子節(jié)上，且鏈表中的關(guān)鍵字恰好是有序的。
不可能非葉子節(jié)點命中返回。
非葉子節(jié)點相當于葉子節(jié)點的索引，葉子節(jié)點相當于是存儲 (關(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ǔ)上進行了優(yōu)化，增加了順序訪問指針。
如上圖所示，在 B +Tree 的每個葉子節(jié)點增加一個指向相鄰葉子節(jié)點的指針，就形成了帶有順序訪問指針的 B +Tree。做這個優(yōu)化的目的是為了提高區(qū)間訪問的性能，例如圖 4 中如果要查詢 key 為從 18 到 49 的所有數(shù)據(jù)記錄，當找到 18 后，只需順著節(jié)點和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點，極大提到了區(qū)間查詢效率。
二叉樹與紅黑樹的比較
從上面我們發(fā)現(xiàn)，紅黑樹相比較于二叉樹又進步了一些，但紅黑樹還是有些問題：那就是數(shù)據(jù)量大的話，紅黑樹的深度會很深，也就是說深度不可控，這樣一來查找數(shù)據(jù)還是會很耗時。
從上面看，我們發(fā)現(xiàn) BTree 又進步了一些，查詢速度提高，存儲容量也沒影響到。當然有人可能會這樣想，那我們?yōu)槭裁床话褦?shù)據(jù)全部都存在一個節(jié)點，這樣深度不就是 1 了嗎?
當然不行了!java 拿取數(shù)據(jù)一般是這樣的：java 程序 – CPU— 內(nèi)存 —- 硬盤，而內(nèi)存與硬盤的交互是有大小限制的，是一頁數(shù)據(jù) 4k 左右，所以不能把所有數(shù)據(jù)都放在一個節(jié)點來獲取，一般來說節(jié)點會盡量預(yù)存 4K 容量。
看到這里，我們知道 (4K= 節(jié)點; 節(jié)點 = 小節(jié)點 * 小節(jié)點的容量) 一個節(jié)點是 4K，而節(jié)點內(nèi)有幾個小節(jié)點，那么也就是說，只要我們每個的小節(jié)點的 data 容量越小，那么可以存的節(jié)點也就可以更多。
B+Tree 通過把 data 不放在非葉子節(jié)點來增加度(小節(jié)點)，一般會一百個以上使得深度是 3~5，從而減少查詢次數(shù)。并且，葉子節(jié)點之間會有指針，數(shù)據(jù)又是遞增的，這使得我們范圍查找可以通過指針連接查找，而不再從上面節(jié)點往下一個個找。
上述內(nèi)容就是 MySQL 中索引的底層實現(xiàn)原理是什么，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注丸趣 TV 行業(yè)資訊頻道。
