什么是索引
索引是一種數(shù)據(jù)結(jié)構(gòu)，其作用就是用來提高數(shù)據(jù)查詢效率。比較常用的比喻就是將其類比為書籍的目錄。通過目錄可以精確的找到某一章節(jié)的內(nèi)容所在頁。
在數(shù)據(jù)量較小的時候使用索引其實也沒有什么意義，即使沒有索引需要一條一條遍歷數(shù)據(jù)對于計算機來說也并不需要太多時間。而一旦數(shù)據(jù)量較大，要保證我們能正常的對外提供服務(wù)，保證用戶使用體驗?zāi)敲此饕褪潜匾牧恕?/p>
索引類型
索引是一種數(shù)據(jù)結(jié)構(gòu)，為了應(yīng)對不同的場景會有多種實現(xiàn)。在mysql中主要就是Hash索引和B+Tree。
Hash索引
hash相信大家應(yīng)該都很熟悉，hash是一種key-value形式的數(shù)據(jù)結(jié)構(gòu)。實現(xiàn)一般是數(shù)組+鏈表的結(jié)構(gòu)，通過hash函數(shù)計算出key在數(shù)組中的位置，然后如果出現(xiàn)hash沖突就通過鏈表來解決(拉鏈法)。當然還有其他的解決hash沖突的方法。hash這種數(shù)據(jù)結(jié)構(gòu)是很常用的，比如我們系統(tǒng)使用HashMap來構(gòu)建熱點數(shù)據(jù)緩存，存取效率很好。
hash結(jié)構(gòu)存數(shù)據(jù)首先通過計算key的hash值來確定其在數(shù)組中的位置，如果有沖突就在該數(shù)組位置建一個鏈表。這樣很明顯有幾個問題：
即使是具有相同特征的key計算出來的位置可能相隔很遠，連續(xù)查詢效率低下。即不支持范圍查詢。
hash索引存儲的事計算得到的hash值和行指針，而不存儲具體的行值，所以通過hash索引查詢數(shù)據(jù)需要進行兩次查詢(首先查詢行的位置，然后找到具體的數(shù)據(jù))
hash索引查詢數(shù)據(jù)的前提就是計算hash值，也就是要求key為一個能準確指向一條數(shù)據(jù)的key，所以對于like等一類的匹配查詢是不支持的。
所以我們可以知道的是hash索引適用于快速選取某一行的數(shù)據(jù)。
B+Tree結(jié)構(gòu)
從名字上看這明顯是一種樹結(jié)構(gòu)，在大學(xué)期間數(shù)據(jù)結(jié)構(gòu)的課本上樹結(jié)構(gòu)是必講的。樹結(jié)構(gòu)是一種特別重要的數(shù)據(jù)結(jié)構(gòu)，在很多地方都會使用到。
上面我們說到hash索引無法進行范圍查詢，在樹結(jié)構(gòu)中也有一種方便進行有序查詢的結(jié)構(gòu)–二叉搜索樹。二叉搜索樹的結(jié)構(gòu)中要求父節(jié)點的值大于左孩子節(jié)點并且小于右孩子節(jié)點，如下圖：
上圖中二叉樹的查詢的時間復(fù)雜度為O(log(n))，當然要保證O(log(n))的時間復(fù)雜度就需要保證二叉樹時刻保持平衡。
而在MySQL索引中雖然也使用了樹結(jié)構(gòu)，但是并不是使用的二叉樹。因為在數(shù)據(jù)庫中數(shù)據(jù)最終都是存放在磁盤上的，而如果樹的節(jié)點過多的話，那么在節(jié)點之間轉(zhuǎn)移會花費較多的時間。在MySQL的實現(xiàn)中選擇將更多內(nèi)容放在同一個節(jié)點，對同一個節(jié)點的操作轉(zhuǎn)入在內(nèi)存中完成，減少在外存中節(jié)點之間轉(zhuǎn)移的次數(shù)，以達到提高效率的目的。這就是B+Tree，在B+Tree的實現(xiàn)中一個三層的樹結(jié)構(gòu)就基本上可以滿足我們幾乎所有的需求了。
相關(guān)推薦：《mysql數(shù)據(jù)庫知識學(xué)習(xí)》
B-Tree
要了解B+Tree首先就得了解B-Tree，B-Tree是一種平衡樹，這里的B指的是Balance而不是Binary，更確切的說B-Tree是一種多路平衡搜索樹。
多路平衡搜索樹如下圖：
這是一種2-3樹，意思就是每個節(jié)點存有兩個值，同時每個節(jié)點分支數(shù)為3，從上圖中可以看出來著中結(jié)構(gòu)很適合查詢數(shù)據(jù)。每個節(jié)點的左子樹的值都是小于當前節(jié)點中最小的值，中間的子樹的值全都是在當前節(jié)點兩個值的中間，而右子樹的值全都大于當前節(jié)點的最大值。
比如我們要查找24這個值：
（1）首先從根節(jié)點判斷24在根節(jié)點(15,25)之間，所以左右子樹排除，從中間查找。
（2）然后找到中間子樹的根節(jié)點(18,22)，比較發(fā)現(xiàn)24大于該節(jié)點最大值，排除左子樹和中間子樹。
（3）找到右子樹，判斷節(jié)點大值剛好等于24，查詢結(jié)束。
基于上面的流程可以總結(jié)B樹的搜索：
（1）從根結(jié)點開始，對結(jié)點內(nèi)的關(guān)鍵字（有序）序列進行二分查找。
（2）如果命中則結(jié)束，否則進入查詢關(guān)鍵字所屬范圍的子結(jié)點；
（3）重復(fù)上面的流程，直到所對應(yīng)的子節(jié)點為空，或已經(jīng)是葉子結(jié)點；
可以看出其搜索性能相當于在關(guān)鍵字集合內(nèi)做一次二分查找。從這里看來好像B-Tree沒有什么問題，但是需要注意到的是在B-Tree中每一個節(jié)點都是存儲索引關(guān)鍵字以及其代表的具體行數(shù)據(jù)。而在MySQL中數(shù)據(jù)庫加載數(shù)據(jù)是以頁為單位加載，每一頁的大小是固定的(默認16k)。如果每一個節(jié)點都存儲所有的值，那么一頁中能存下的節(jié)點就會很少，一次查詢可能就會進行多次從內(nèi)存中去加載數(shù)據(jù)，導(dǎo)致性能降低。
B+Tree
B+Tree是對B-Tree的一個變種，讓其更加適應(yīng)于進行外部存儲文件索引。
兩者之前最大的不同就在于B-Tree的每個節(jié)點都存儲所有的數(shù)據(jù)，而B+Tree需要存儲的數(shù)據(jù)都在葉子節(jié)點上，并且增加了順序訪問指針，每個葉子節(jié)點都有指向下一個相鄰的葉子節(jié)點的地址。這樣的結(jié)構(gòu)保證了在一個內(nèi)存頁中可以存下更多的索引節(jié)點，并且更加適合進行范圍查詢。
索引
因為存儲引擎負責(zé)實現(xiàn)索引，所以接下來討論索引都是基于MySQL的InnoDB引擎。
聚簇索引
聚簇的意思是表示數(shù)據(jù)行和相鄰的鍵值聚簇的存儲在一起。一些數(shù)據(jù)庫允許選擇具體的某一個索引作為聚簇索引，而在InnoDB的實現(xiàn)中直接將主鍵索引指定為聚簇索引。如果沒有定義主鍵，InnoDB 會選擇一個唯一的非空索引來代替主鍵索引。如果同樣沒有定義這樣的索引，InnoDB會隱式定義一個主鍵來作為聚簇索引(row_id)。
聚簇索引實例如圖：
非聚簇索引索引
在InnoDB中除主鍵索引外其他都是非聚簇索引，所以也叫非主鍵索引。非主鍵索引的葉節(jié)點并不是存儲一行的值，而是存儲具體行的主鍵值。不滿足聚簇的定義。
非聚簇索引實例如圖：
聚簇索引和非聚簇索引在查詢時的差異
由上面的兩種索引實例圖就可以看出來，在查詢時如果是通過主鍵索引查詢的話直接查詢到數(shù)據(jù)行然后返回。但是如果是通過非主鍵索引查詢的話首先需要通過該索引確定主鍵，然后通過得到的主鍵從主鍵索引中查到具體行的數(shù)據(jù)，后面的通過得到的主鍵從主鍵索引中獲取數(shù)據(jù)的過程被稱為回表。
回表的過程使得通過普通索引查詢較主鍵索引查詢多了一步，在很多情況下效率相對較低。所以在我們的查詢過程中如果能夠僅通過主鍵確定數(shù)據(jù)那最好就是直接使用主鍵進行查詢。
覆蓋索引
上面介紹了通過非主鍵查詢會有一個回表的過程，但是需要注意的是并不是每一個查詢都存在回表這一步，對于一個普通索引來說其葉節(jié)點存儲的是主鍵的值，那么假設(shè)我現(xiàn)在需要的數(shù)據(jù)也僅僅就是主鍵的值呢？通過普通索引取到主鍵的值后就并不需要再到主鍵索引中查，那么也就不存在回表這一過程了。
上面例子中該非主鍵索引已經(jīng)存在了我們所需要的值，所以該索引也被稱為覆蓋索引。覆蓋索引并不是一個固定的結(jié)構(gòu)，可以使單索引(一個字段的索引)，也可以使復(fù)合索引，凡是能夠直接提供查詢結(jié)果而不需要進行回表過程的都可以被稱為覆蓋索引。
很多時候我們不可能僅僅通過主鍵來確定數(shù)據(jù)，使用普通索引可能會導(dǎo)致低效，所以覆蓋索引在日常開發(fā)過程中也是一個很常用的性能優(yōu)化的手段。
當然覆蓋索引頁并不都是好的，比如我現(xiàn)在建立了一個索引index(a,b)。由a，b兩個字段來建立索引，好處已經(jīng)說過了就是查詢ab字段時不會回表，但是如果僅僅通過b字段來查詢就無法走這個索引了。建立的索引的索引項是按照索引定義里面出現(xiàn)的字段順序排序的。
最左前綴原則
假設(shè)現(xiàn)在存在索引index(a,b)，那么如果通過a和b來查詢能夠應(yīng)用該索引，單獨使用a來查詢也能應(yīng)用到該索引，但是如果單獨使用b來查詢則無法應(yīng)用到該索引。這就是最左前綴原則，在匹配索引時回匹配索引最左邊的n個字段，能匹配上就可以應(yīng)用該索引。
由于最左前綴原則的存在也就要求我們在建立索引時可能需要考慮更多的事情。
首先需要清楚的事索引是一種數(shù)據(jù)結(jié)構(gòu)，建立索引時需要消耗存儲空間的，所以索引并不是建立的越多越好，而是應(yīng)該根據(jù)需求盡可能的減少索引的數(shù)量。
而最左前綴原則的存在就使得一個聯(lián)合索引可以被當成多個索引來使用，當然前提是設(shè)計好索引中字段的順序(實際上最左前綴原則也并不是僅僅適用于聯(lián)合索引，對于字符串索引也使用，字符串索引中最左n個字符相當于聯(lián)合索引中的最左n個字段)。
比如index(a,b)，有了這個索引后我們就不需要單獨為a建立索引，所以在設(shè)計聯(lián)合索引時一般將使用頻率較高的字段放在前面。
然后是將區(qū)分度較高的字段靠前，區(qū)分度就是字段中值的重復(fù)率，重復(fù)率越低區(qū)分度越高。比如性別就不適合作為索引，區(qū)分度越高的字段經(jīng)過一次篩選能過濾掉更多的行。
然后還需要考慮的是字段的大小，由于索引也需要占據(jù)空間所以一般選用較小的字段。
參考資料
MySQL運維內(nèi)參：MySQL、Galera、Inception核心原理與最佳實踐
