MySQL中索引的底層實現原理是什么

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

　　MySQL索引底層實現原理

　　MySQL官方對索引的定義為：索引(Index)是幫助MySQL高效獲取數據的數據結構。提取句子主干，就可以得到索引的本質：索引是數據結構。

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

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

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

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

　　二叉排序樹

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

　　若左子樹不空，則左子樹上所有節點的值均小于它的根節點的值;

　　若右子樹不空，則右字數上所有節點的值均大于它的根節點的值;

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

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

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

　　B樹

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

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

　　每個節點至多可以擁有m棵子樹。

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

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

　　非葉節點中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示該節點中保存的關鍵字個數，K為關鍵字且Ki

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

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

　　從根節點P開始，K的位置在P之前，進入左側指針。

　　左子樹中，依次比較C、F、J、M，發現K在J和M之間。

　　沿著J和M之間的指針，繼續訪問子樹，并依次進行比較，發現第一個關鍵字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樹的特點可以總結為如下：

　　關鍵字集合分布在整顆樹中。

　　任何一個關鍵字出現且只出現在一個節點中。

　　搜索有可能在非葉子節點結束。

　　其搜索性能等價于在關鍵字集合內做一次二分查找。

　　B樹在插入刪除新的數據記錄會破壞B-Tree的性質，因為在插入刪除時，需要對樹進行一個分裂、合并、轉移等操作以保持B-Tree性質。

　　Plus版 — B+樹

　　作為B樹的加強版，B+樹與B樹的差異在于:

　　有n棵子樹的節點含有n個關鍵字(也有認為是n-1個關鍵字)。

　　所有的關鍵字全部存儲在葉子節點上，且葉子節點本身根據關鍵字自小而大順序連接。

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

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

　　B+樹的特性如下：

　　所有關鍵字都存儲在葉子節上，且鏈表中的關鍵字恰好是有序的。

　　不可能非葉子節點命中返回。

　　非葉子節點相當于葉子節點的索引，葉子節點相當于是存儲(關鍵字)數據的數據層。

　　更適合文件索引系統。

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

　　一般在數據庫系統或文件系統中使用的B+Tree結構都在經典B+Tree的基礎上進行了優化，增加了順序訪問指針。

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

　　二叉樹與紅黑樹的比較

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

　　從上面看，我們發現BTree又進步了一些，查詢速度提高，存儲容量也沒影響到。當然有人可能會這樣想，那我們為什么不把數據全部都存在一個節點，這樣深度不就是1了嗎?

　　當然不行了!java拿取數據一般是這樣的：java程序-->CPU--->內存---->硬盤，而內存與硬盤的交互是有大小限制的，是一頁數據4k左右，所以不能把所有數據都放在一個節點來獲取，一般來說節點會盡量預存4K容量。

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

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

上述內容就是MySQL中索引的底層實現原理是什么，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。