索引類(lèi)型包括 B-Tree霞玄、哈希索引没讲、R-Tree绩蜻、全文索引等，這里主要總結(jié) B-Tree 和哈希索引绿聘。

B-Tree 索引

以 B-Tree 為結(jié)構(gòu)的索引是最常見(jiàn)的索引類(lèi)型暗挑，比如 InnoDB 和 MyISAM 都是以 B-Tree 為索引結(jié)構(gòu)的索引，事實(shí)上是以 B+ Tree 為索引結(jié)構(gòu)斜友，B-Tree 和 B+Tree 區(qū)別在于炸裆，B+ Tree 在葉子節(jié)點(diǎn)上增加了順序訪問(wèn)指針，方便葉子節(jié)點(diǎn)的范圍遍歷鲜屏。這里主要介紹一下 InnoDB 和 MyISAM 兩種不同的索引烹看。

InnoDB

InnoDB 支持聚簇索引，聚簇索引和非聚簇索引嚴(yán)格來(lái)說(shuō)不是一種索引洛史，而是一種數(shù)據(jù)存儲(chǔ)方式惯殊，這個(gè)名字跟它本身的存儲(chǔ)方式有關(guān)系，“聚簇“表示數(shù)據(jù)行和相鄰的鍵值存儲(chǔ)在一起也殖，簡(jiǎn)單的說(shuō)土思，就是葉子節(jié)點(diǎn)中存儲(chǔ)的實(shí)際是真實(shí)的數(shù)據(jù)。InnoDB 通過(guò)主鍵聚集數(shù)據(jù)忆嗜，所以一個(gè)表只能有一個(gè)聚簇索引己儒，且必須有主鍵，如果沒(méi)有定義主鍵捆毫，且不存在非空索引可以代替闪湾，InnoDB 會(huì)隱式定義一個(gè)主鍵作為聚簇索引。

聚簇索引的二級(jí)索引存儲(chǔ)的不是指向行的物理位置的指針绩卤，而是行的主鍵值途样，所以如果通過(guò)二級(jí)索引查找行，需要找到二級(jí)索引的葉子結(jié)點(diǎn)獲得對(duì)應(yīng)的主鍵值濒憋，然后再去查找對(duì)應(yīng)的行何暇。對(duì)于 InnoDB，自適應(yīng)哈希索引可以減少這樣的重復(fù)工作凛驮。

MyISAM

MyISAM 支持非聚簇索引裆站，和 InnoDB 的區(qū)別在于，葉子結(jié)點(diǎn)上存的是指向?qū)?yīng)行的物理地址辐烂，也就是說(shuō)索引和數(shù)據(jù)實(shí)際是分開(kāi)存儲(chǔ)的遏插。

MyISAM 采用了前綴壓縮技術(shù)，從而使得更多索引可以放入到內(nèi)存中纠修，默認(rèn)只壓縮字符串胳嘲，但是通過(guò)參數(shù)設(shè)置也可以對(duì)整數(shù)做壓縮。壓縮方法為扣草，完整保存索引塊中的第一個(gè)IE之了牛，然后將其他值和第一個(gè)值進(jìn)行比較得到相同前綴的字節(jié)數(shù)和剩余的不同后綴部分颜屠，把這部分存儲(chǔ)起來(lái)即可。例如鹰祸，索引塊中的第一個(gè)值是“perform”甫窟，第二個(gè)值是“performance”，那么第二個(gè)值的前綴壓縮后存儲(chǔ)的是類(lèi)似“7蛙婴，ance”這樣的形式粗井。MyISAM 對(duì)行指針也采用類(lèi)似的前綴壓縮方式。

壓縮可以使索引使用更少的空間街图，在某種程度上性能有所提升浇衬，但是代價(jià)是某些操作可能更慢。因?yàn)槊總€(gè)值的壓縮前綴都依賴(lài)前面的值餐济，所以 MyISAM 查找時(shí)無(wú)法在索引塊使用二分查找耘擂，只能從頭開(kāi)始掃描，正序掃描速度還不錯(cuò)絮姆，逆序掃描的話查找某一行的操作平均都需要掃描半個(gè)索引塊醉冤。對(duì)于 CPU 密集型應(yīng)用，掃描需要隨機(jī)查找篙悯，所以壓縮索引會(huì)使得索引查找慢很多蚁阳，而對(duì)于 I/O 密集型應(yīng)用，對(duì)于某些查詢(xún)的優(yōu)化更明顯辕近。

鎖

InnoDB 使用的是行鎖韵吨，所以支持事務(wù)，而 MyISAM 使用的是表鎖移宅，不支持事務(wù)。

適用范圍

B-Tree 索引適用于區(qū)間查詢(xún)椿疗，因?yàn)?B-Tree 存儲(chǔ)后的葉子節(jié)點(diǎn)本身就是有序的漏峰，并且 B+ Tree 結(jié)構(gòu)還增加了葉子節(jié)點(diǎn)的連續(xù)順序指針，對(duì)于區(qū)間查詢(xún)來(lái)說(shuō)就更加方便了届榄。

哈希索引

哈希索引是基于哈希表實(shí)現(xiàn)的浅乔，只有精確匹配索引所有列的查詢(xún)才有效。方法是铝条，對(duì)所有的索引列計(jì)算一個(gè) hash code靖苇，hash code 作為索引，在哈希表中保存指向每個(gè)數(shù)據(jù)行的指針班缰。

優(yōu)點(diǎn)

• 索引本身只存儲(chǔ) hash code贤壁，所以結(jié)構(gòu)很緊湊，并且查找速度很快

限制

• 索引中的 hash code 是順序存儲(chǔ)的埠忘，但是 hash code 對(duì)應(yīng)的數(shù)據(jù)并不是順序的脾拆，所以無(wú)法用于排序
• 不支持部分索引列匹配查找馒索，因?yàn)楣Ｋ饕鞘褂盟饕械娜績(jī)?nèi)容來(lái)計(jì)算 hash code
• 只支持等值比較，不支持范圍查詢(xún)
• 如果哈希沖突嚴(yán)重時(shí)名船，必須遍歷鏈表中所有行指針
• 哈希沖突嚴(yán)重的話绰上，索引維護(hù)操作的代價(jià)也很高

InnoDB 的自適應(yīng)哈希索引

首先，請(qǐng)注意渠驼，自適應(yīng)哈希索引對(duì)于用戶(hù)來(lái)說(shuō)是無(wú)感知的蜈块，這是一個(gè)完全自動(dòng)、內(nèi)部的行為迷扇，用戶(hù)無(wú)法控制或者配置疯趟，但是可以關(guān)閉。

當(dāng) InnoDB 注意到某個(gè)索引值被使用的非常頻繁時(shí)谋梭，它會(huì)在內(nèi)存中基于 B-Tree 索引之上再創(chuàng)建一個(gè)哈希索引信峻，這樣 B-Tree 也可以具有哈希索引的一些優(yōu)點(diǎn)，比如快速的哈希查找瓮床。

當(dāng)然如果存儲(chǔ)引擎不支持哈希索引盹舞，用戶(hù)也可以自定義哈希索引，這樣性能會(huì)比較高隘庄，缺陷是需要自己維護(hù)哈希值踢步，如果采用這種方法，不要使用 SHA1() 和 MD5() 作為哈希函數(shù)丑掺，因?yàn)檫@兩個(gè)是強(qiáng)加密函數(shù)获印，設(shè)計(jì)目標(biāo)是最大限度消除沖突，生成的 hash code 是一個(gè)非常長(zhǎng)的字符串街州，浪費(fèi)大量的空間兼丰，哈希索引中對(duì)于索引的沖突要求沒(méi)有那么高。

索引的優(yōu)點(diǎn)

• 使用索引可以減少服務(wù)器需要掃描的數(shù)據(jù)量
• 使用索引可以幫助服務(wù)器避免排序和臨時(shí)表
• 使用索引可以將隨機(jī) I/O 變?yōu)轫樞?I/O

但是不是所有情況下唆缴，索引都是最好的解決方案鳍征，對(duì)于非常小的表來(lái)說(shuō)，大部分情況下簡(jiǎn)單的全表掃描更高效面徽，對(duì)于中到大型表艳丛，索引就比較有效，對(duì)于特大型的表來(lái)說(shuō)趟紊，分區(qū)會(huì)更加有效氮双。

Reference

《高性能 MySQL》