mysql索引

最近一直在看《高性能mysql》，關(guān)于索引部分，以前接觸過，但是不是特別深入，僅僅了解過主鍵索引，本片博文用來加深對(duì)索引部分的印象，博主學(xué)習(xí)的《高性能mysql》是2013年5月版，主要是基于 mysql5.5

mysql索引分類

本文主要介紹以下兩種索引

1. B+Tree索引（書中寫的是B-Tree，根據(jù)譯者說明，應(yīng)該是B+Tree）
2. 哈希索引

B+Tree索引

既然原書中寫的是 B-Tree，我們就簡(jiǎn)單介紹一下 B-Tree，介紹 B+Tree時(shí)也方便一點(diǎn)

B-Tree 是 B樹而不是 B減樹，中間的 - 是連接符
B-Tree 是一種多叉平衡查找樹，對(duì)比二叉平衡查找樹（又叫 avl樹），B-Tree 每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目可以大于兩個(gè)，如果B-Tree樹中每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目最大為 m，則為m階B-Tree，除此以外B-Tree與 avl樹沒有明顯的不同

B+Tree 是在 B-Tree樹上的一種拓展，百科上面對(duì)B+Tree講述的比較細(xì)致，這里主要有三點(diǎn)需要額外的注意

1. 除了最后的葉子節(jié)點(diǎn)，每個(gè)葉子節(jié)點(diǎn)都有指向下一個(gè)葉子節(jié)點(diǎn)的指針，從而所有葉子節(jié)點(diǎn)形成了一個(gè)有序的鏈表，連續(xù)順序查找時(shí)會(huì)非常節(jié)省時(shí)間
2. 每個(gè)非葉子節(jié)點(diǎn)不存儲(chǔ)具體的數(shù)據(jù)（嚴(yán)格來說時(shí)指向數(shù)據(jù)的指針），而僅僅存儲(chǔ)鍵
3. 當(dāng)索引的鍵不止一個(gè)時(shí)（譬如，使用 <last_name, first_name, date> 作為索引）時(shí)，只有在前一個(gè)鍵匹配的情況下才能去查找下一個(gè)。譬如，如果 last_name匹配，則可以去匹配 first_name，如果 first_name也已經(jīng)匹配，則可以去匹配 date。如果不提供 last_name的值，則不能直接去匹配 first_name，也不能直接去匹配 date

B+Tree示意圖如下

圖片來自百度百科

我們可以模擬一下B+Tree索引的查找過程
譬如，我們需要查找 <last_name=Y,first_name=XC,date=2020.10.26,time=night>，首先我們需要建立這樣的索引 key(last_name,first_name,date,time)，上圖中的 key就變成數(shù)據(jù)庫(kù)中這四個(gè)項(xiàng)的組合，然后

1. 根據(jù) last_name=Y 在對(duì)應(yīng)的 B+Tree中查找
2. 找到對(duì)應(yīng)索引后，再根據(jù) first_name查找
3. 找到對(duì)應(yīng)索引后，再根據(jù) date=2020.10.26查找（如果這里 date是范圍表示，譬如 date<2030.1.1，則time索引不會(huì)被查找）
4. 最后按照 time索引查找

在查找到對(duì)應(yīng)的葉子節(jié)點(diǎn)后，直接訪問也葉子節(jié)點(diǎn)指向的數(shù)據(jù)行，查找過程結(jié)束。

我們回顧一下查找過程，主要的耗時(shí)在于索引樹的遍歷，假設(shè)我們使用的是 m 階B+Tree，樹的深度為 log(m)n，每一層查找平局耗時(shí)為 m/2，網(wǎng)上很多地方說這里可以用二分查找，但是博主仔細(xì)想了一下，第一，除非葉子節(jié)點(diǎn)，否則同一個(gè)父親的子節(jié)點(diǎn)之間沒有關(guān)聯(lián)（只有葉子節(jié)點(diǎn)才用“串”起來）。第二，哪怕是葉子節(jié)點(diǎn)，他們之間的關(guān)聯(lián)方式為指針連接，也很難通過下標(biāo)的方式訪問子節(jié)點(diǎn)

那么一次查找的平均耗時(shí)為 m/2*log(m)n，1/2為常數(shù)，可以省略，耗時(shí)可以寫成 log(m^(1/m))n，對(duì)m^(1/m)求導(dǎo)可知，當(dāng) m=e的時(shí)候取最大值，此時(shí)耗時(shí)為最小值，由于這里m為整數(shù)，所以當(dāng) m=3時(shí)，有最好的效率，復(fù)雜度為 O(log(3)n)

如果我們不使用索引，直接查找數(shù)據(jù)行，復(fù)雜度為 O(n)

哈希索引

哈希索引使用哈希表實(shí)現(xiàn)，通過對(duì)不同的鍵值進(jìn)行哈希計(jì)算，得到哈希碼，通過訪問哈希碼能快速的訪問到數(shù)據(jù)行

我們假設(shè)，使用 fname建立哈希索引，我們執(zhí)行如下查詢

SELECT lname FROM testhash WHERE fname='Peter';

通過哈希索引訪問過程如下

1. 計(jì)算 Peter的哈希值
2. 使用哈希值查詢到對(duì)應(yīng)的記錄指針
3. 使用記錄指針找到對(duì)應(yīng)的數(shù)據(jù)行，并判斷該行的 fname是否等于 Peter

由于底層使用了哈希表，所以查詢速度非常快，不過哈希索引也存在著一定的問題

1. 哈希索引不支持部分索引列匹配查找。
   使用 B+Tree索引時(shí)，如果我們無(wú)法對(duì)整個(gè)查詢字段進(jìn)行索引查找，我們也可以根據(jù)前幾項(xiàng)索引來優(yōu)化我們的查找速度，但是哈希索引是建立時(shí)就將所有字段組合之后進(jìn)行哈希，所以只提供部分字段值，我們無(wú)法生成對(duì)應(yīng)的哈希值，也就無(wú)法使用哈希查找
2. 哈希索引不支持范圍查找。
   由于字段經(jīng)過哈希函數(shù)之后已經(jīng)無(wú)法比較大小，所以范圍查找是無(wú)法通過哈希索引的
3. 如果哈希沖突很多，查找和維護(hù)的代價(jià)也會(huì)很高

綜上，哈希索引在部分情況下效率極高，特別是當(dāng)數(shù)據(jù)行的鍵重合度比較低，查詢多是等值查詢時(shí)。我們可以在通過做CRC32或者取用MD5的一部分作為我們的鍵，降低數(shù)據(jù)行的鍵重合度來優(yōu)化我們的哈希索引。