一文讀懂MySQL中的索引

什麼是索引

#索引是一種資料結構，其功能就是用來提高資料查詢效率。比較常用的比喻就是將其類比為書的目錄。透過目錄可以精確的找到某一章節的內容所在頁。

在資料量較小的時候使用索引其實也沒有意義，即使沒有索引需要一條一條遍歷資料對電腦來說也並不需要太多時間。而一旦資料量較大，要確保我們能正常的對外提供服務，保證使用者使用體驗那麼索引就是必要的了。

索引類型

索引是一種資料結構，為了回應不同的場景會有多種實作。在MySQL中主要就是Hash索引和B Tree。

Hash索引

hash相信大家應該都很熟悉，hash是一種key-value形式的資料結構。實作一般是陣列 鍊錶的結構，透過hash函數計算出key在陣列中的位置，然後如果出現hash衝突就透過鍊錶來解決(拉鍊法)。當然還有其他的解決hash衝突的方法。 hash這種資料結構是很常用的，例如我們系統使用HashMap來建立熱點資料緩存，存取效率很好。

hash結構存資料首先透過計算key的hash值來決定其在陣列中的位置，如果有衝突就在該陣列位置建立一個鍊錶。這樣很明顯有幾個問題：

即使是具有相同特徵的key計算出來的位置可能相隔很遠，連續查詢效率低。即不支援範圍查詢。

hash索引儲存的事計算得到的hash值和行指針，而不儲存具體的行值，所以透過hash索引查詢資料需要進行兩次查詢(先查詢行的位置，然後找到具體的資料)

hash索引查詢資料的前提就是計算hash值，也就是要求key為一個能準確指向一條資料的key，所以對於like等一類的符合查詢是不支援的。

所以我們可以知道的是hash索引適用於快速選取某一行的資料。

B Tree結構

從名字上看這明顯是一種樹狀結構，在大學期間資料結構的課本上樹結構是必講的。樹結構是一種特別重要的資料結構，在很多地方都會使用。

上面我們說到hash索引無法進行範圍查詢，在樹結構中也有一種方便進行有序查詢的結構--二元搜尋樹。二元搜尋樹的結構中要求父節點的值大於左孩子節點且小於右孩子節點，如下圖：

上圖二叉樹的查詢的時間複雜度為O(log(n))，當然要確保O(log(n))的時間複雜度就需要確保二元樹時時刻刻保持平衡。

而在MySQL索引中雖然也使用了樹狀結構，但並不是使用的二元樹。因為在資料庫中資料最終都是存放在磁碟上的，而如果樹的節點過多的話，那麼在節點之間轉移會花費較多的時間。在MySQL的實作中選擇將更多內容放在同一個節點，對同一個節點的操作轉入在記憶體中完成，減少在外存中節點之間轉移的次數，以達到提高效率的目的。這就是B Tree，在B Tree的實作中一個三層的樹結構就基本上可以滿足我們幾乎所有的需求了。

相關推薦：《mysql資料庫知識學習》

#B-Tree

##要了解B Tree首先就得了解B-Tree，B-Tree是一種平衡樹，這裡的B指的是Balance而不是Binary，更確切的說B-Tree是一種多路平衡搜尋樹。

多路平衡搜尋樹如下圖：

這是一種2-3樹，意思是每個節點存有兩個值，同時每個節點分支數為3，從上圖可以看出來著中結構很適合查詢資料。每個節點的左子樹的值都是小於目前節點中最小的值，中間的子樹的值全都是在目前節點兩個值的中間，而右子樹的值全都大於目前節點的最大值。

例如我們要找24這個值：

（1）先從根節點判斷24在根節點(15,25)之間，所以左右子樹排除，從中間找。

（2）接著找出中間子樹的根節點(18,22)，比較發現24大於該節點最大值，排除左子樹和中間子樹。

（3）找到右子樹，判斷節點大值剛好等於24，查詢結束。

基於上面的流程可以總結B樹的搜尋：

（1）從根結點開始，對結點內的關鍵字（有序）序列進行二分查找。

（2）如果命中則結束，否則進入查詢關鍵字所屬範圍的子結點；

（3）重複上面的流程，直到所對應的子節點為空，或已經是葉子結點；

可以看出其搜尋效能相當於在關鍵字集合內做一次二分查找。從這裡看來好像B-Tree沒有什麼問題，但是需要注意到的是在B-Tree中每一個節點都是儲存索引關鍵字以及其代表的具體行資料。而在MySQL中資料庫載入資料是以頁為單位加載，每一頁的大小是固定的(預設16k)。如果每個節點都儲存所有的值，那麼一頁中能存下的節點就會很少，一次查詢可能就會進行多次從內存中去加載數據，導致性能降低。

B Tree

B Tree是B-Tree的變種，讓其更適應於進行外部儲存檔案索引。

兩者之前最大的不同就在於B-Tree的每個節點都儲存所有的數據，而B Tree需要儲存的資料都在葉子節點上，並且增加了順序存取指針，每個葉子節點都有指向下一個相鄰的葉子節點的位址。這樣的結構保證了在一個記憶體頁中可以存下更多的索引節點，並且更適合進行範圍查詢。

索引

因為儲存引擎負責實作索引，所以接下來討論索引都是基於MySQL的InnoDB引擎。

叢集索引

叢集的意思是表示資料行和相鄰的鍵值叢集的儲存在一起。有些資料庫允許選擇特定的某一個索引作為叢集索引，而在InnoDB的實作中直接將主鍵索引指定為叢集索引。如果沒有定義主鍵，InnoDB 會選擇一個唯一的非空索引來取代主鍵索引。如果同樣沒有定義這樣的索引，InnoDB會隱式定義一個主鍵來作為叢集索引(row_id)。

叢集索引實例如圖：

非叢集索引索引

在InnoDB中除主鍵索引外其他都是非叢集索引，所以也叫非主鍵索引。非主鍵索引的葉節點並不是儲存一行的值，而是儲存特定行的主鍵值。不滿足聚集簇的定義。

非叢集索引實例如圖：

叢集索引與非叢集索引在查詢時的差異

#由上面的兩種索引實例圖就可以看出來，在查詢時如果是透過主鍵索引查詢的話直接查詢到資料行然後返回。但是如果是透過非主鍵索引查詢的話首先需要透過該索引確定主鍵，然後透過得到的主鍵從主鍵索引中查到具體行的數據，後面的通過得到的主鍵從主鍵索引中獲取數據的過程被稱為回表。

回表的過程使得透過普通索引查詢較主鍵索引查詢多了一步，在許多情況下效率相對較低。所以在我們的查詢過程中如果能夠只透過主鍵確定資料那最好就是直接使用主鍵來查詢。

覆蓋索引

上面介紹了透過非主鍵查詢會有一個回表的過程，但是需要注意的是並不是每一個查詢都存在回表這一步，對於一個普通索引來說其葉節點儲存的是主鍵的值，那麼假設我現在需要的資料也僅僅就是主鍵的值呢？透過普通索引取到主鍵的值後就並不需要再到主鍵索引中查，那麼也就不存在回表這一過程了。

上面範例中該非主鍵索引已經存在了我們所需要的值，所以該索引也稱為覆寫索引。覆蓋索引並不是固定的結構，可以使單一索引(一個欄位的索引)，也可以使複合索引，凡是能夠直接提供查詢結果而不需要進行回表過程的都可以稱為覆蓋索引。

很多時候我們不可能僅僅透過主鍵來確定數據，使用普通索引可能會導致低效，所以覆蓋索引在日常開發過程中也是一個很常用的性能優化的手段。

當然覆蓋索引頁並不都是好的，例如我現在建立了一個索引index(a,b)。由a，b兩個字段來建立索引，好處已經說過了就是查詢ab字段時不會回表，但是如果僅僅通過b字段來查詢就無法走這個索引了。建立的索引的索引項是依照索引定義裡面出現的欄位順序排序的。

最左前綴原則

假設現在存在索引index(a,b)，那麼如果透過a和b來查詢能夠應用該索引，單獨使用a來查詢也能套用到該索引，但如果單獨使用b來查詢則無法套用到該索引。這就是最左前綴原則，在匹配索引時回匹配索引最左邊的n個字段，能匹配上就可以應用該索引。

由於最左前綴原則的存在也就要求我們在建立索引時可能需要考慮更多的事情。

首先需要清楚的事索引是一種資料結構，建立索引時需要消耗儲存空間的，所以索引並不是建立的越多越好，而是應該根據需求盡可能的減少索引的數量。

而最左前綴原則的存在就使得一個聯合索引可以被當成多個索引來使用，當然前提是設計好索引中字段的順序(實際上最左前綴原則也並不是僅僅適用於聯合索引，對於字串索引也使用，字串索引中最左n個字元相當於聯合索引中的最左n個欄位)。

例如index(a,b)，有了這個索引後我們就不需要單獨為a建立索引，所以在設計聯合索引時一般將使用頻率較高的欄位放在前面。

接著是將區分度較高的欄位靠前，區分度就是欄位中值的重複率，重複率越低區分度越高。例如性別就不適合作為索引，區分度越高的欄位經過一次篩選能過濾掉更多的行。

然後還要考慮的是欄位的大小，由於索引也需要佔據空間所以一般選用較小的欄位。

參考資料

MySQL運維內參：MySQL、Galera、Inception核心原理與最佳實踐

以上是一文讀懂MySQL中的索引的詳細內容。更多資訊請關注PHP中文網其他相關文章！