[TOC] # 簡介 索引有很多類型,可以為不同的場景提供更好的性能.在mysql中,索引是存儲引擎層面而不是服務器層實現. 所以,并沒有統一的索引標準,不同存儲引擎的索引的工作方式并不一樣,也不是所有的存儲引擎都支持所有類型的索引.即使多個存儲引擎支持同一種類型的索引,其底層的實現也可能不同 # B-Tree索引 大多數mysql都支持這種索引 不過底層的存儲引擎也可能使用不同的存儲結構,例如,NDB集群存儲引擎內部實際上使用了T-Tree結構存儲這種索引,即使其名字是BTREE,Innodb則使用B+Tree 存儲引擎以不同方式使用B-Tree索引,性能也各有不同,各有優劣.例如:myisam使用前綴壓縮技術使得索引更小,但是Innodb則按照原數據格式進行存儲 再如myisam索引通過數據的物理位置引用被索引的行,而Innodb則根據主鍵引用被索引的行 B-Tree通常意味著所有的值都是按順序存儲的,并且每一個葉子頁到根的距離相同  建立在B-Tree結構(從技術上來說是B+Tree)上的索引 假設有如下數據表 ~~~ create table People ( last_name varchar(50) not null, first_name varchar(50) not null, dob date not null, gender enum('m','f') not null, key(last_name, first_name, dob) ); ~~~ 下面是B-Tree索引的限制 * 如果不是按照索引的最左列開始查找,則無法使用索引.例如上面例子中,查找 first_name, dob,因為這不是罪左數據列 * 不能跳過索引中的列,也就是說前面所述的索引無法用于跳過first_name * 如果查詢中有某個列的范圍查詢,其右邊所有列都無法使用索引優化查找. ~~~ where last_name='Smith' and first_name like 'J%' and dob='1976-12-23' ~~~ 這個查詢只能使用索引的前兩列,因為這里like是一個范圍條件 索引列的順序是多么重要,這些限制都和索引列的順序有關.在優化性能的時候,可能需要使用相同的列但順序不同的索引來滿足不同類型的查詢需求 # 哈希索引 哈希索引基于哈希表實現,只有精確匹配索引所有列的查詢才有效. 對于每一行數據,存儲引擎都會對所有的索引列計算一個哈希碼(hash code),哈希碼是一個較小的值,并且不同鍵值的行計算出來的哈希碼也不一樣.哈希索引將所有的哈希碼存儲在索引中,同時在哈希表中保存指向每個數據行的指針 在mysql中,只有memory引擎顯示支持哈希索引.這也是memory引擎表的默認索引類型.memory引擎同時也支持B-Tree索引.值得一提的是,memory引擎是支持非唯一哈希索引的,這在數據庫世界里面是比較與眾不同的 如果多個列的哈希值相同,索引會以鏈表的方式存放多個記錄的指針到同一個哈希條目中 下面來看個例子 ~~~ create table testhash ( fname varchar(50) not null, lname varchar(50) not null, key using hash(fname) )engine=memory; ~~~ 表中包含了如下的數據  假設索引使用假象的哈希函數f(),他返回下面的值(都是示例數據,非真實數據)  則哈希索引的數據結構如下  注意每個槽的編號是順序的,但是數據行不是.現在,來看如下查詢 ~~~ select lname from testhash where fname = 'Peter'; ~~~ mysql先計算'Peter'的哈希值,并使用該值尋找對應的記錄指針,因為f('Peter') = 8784,所以mysql在索引中查找8784,可以找到指向第三方的指針,最后一步是比較第三行的值是否為'Peter',以確保就是要查找的行 因為索引自身只需存儲對應的哈希值,所以索引的結構十分緊湊,這也讓哈希索引查找的速度非常快.然而,哈希索引也有它的限制 * 哈希索引只包含哈希值和行指針,而不存儲字段值,所以不能使用索引中的值來避免讀取行.不過,訪問內存中的行的速度很快,所以大部分情況下這一點對性能影響并不明顯 * 哈希索引數據并不是按照索引值順序存儲,所以也就無法用于排序 * 哈希索引也不支持部分索引列匹配查找,因為哈希索引始終是使用索引列的全部內容來計算哈希值的.例如,在數據列(A,B)上建立哈希索引,如果查詢只有數據列A,則無法使用該索引 * 哈希索引只支持等值比較查詢,包括=,IN(),<=>,(注意<>和<=>是不同操作).也不支持任何范圍查詢,例如`where price > 100` * 訪問哈希索引的數據非常快,除非有很多哈希沖突(不同的索引列值卻有相同的哈希值).當出現哈希沖突的時候,存儲引擎必須遍歷鏈表中的所有行指針,逐行進行比較,直到找到符合條件的行 * 如果哈希沖突很多的話,一些索引維護操作的代價也會很高.例如,如果在某個選擇性很低(哈希沖突很多)的列上建立哈希索引,那么當從表中刪除一行時,存儲引擎需要遍歷對應哈希值的鏈表中的每一行,找到并刪除對應行的引用,沖突越多,代價越大 因為這些限制,哈希索引只適用于某些特定的場合.而一旦適合哈希索引,則它帶來的性能提升將非常顯著.舉個例子,在數據倉庫應用中有一種經典的"星型" schema,需要關聯很多查找表,哈希索引就非常適合查找表的需求 除了memory引擎外,NDB集群引擎也支持唯一哈希索引,且在NDB集群引擎中作用非常特殊 Innodb引擎有一個特殊的功能叫做"自適應哈希索引".當Innodb注意到某些索引值被使用得非常頻繁時,他會在內存中基于B-Tree索引之上再創建一個哈希索引,這樣就讓B-Tree索引也具有哈希索引的一些優點,比如快速的哈希查找.這是一個完全自動的,內部的行為,用戶無法控制或者配置,不過如果有必要,完全可以關閉該功能 創建自定義哈希索引,如果存儲引擎不支持哈希索引,則可以模擬像Innodb一樣創建哈希索引,這可以享受一些哈希索引的便利,例如只需要很小的索引就可以為超長的鍵創建索引 思路很簡單:在B-Tree基礎上創建一個偽哈希索引.這和真正的哈希索引不是一回事,因為還是使用B-Tree進行查找,但是他使用哈希值而不是鍵本身進行索引查找.你需要做的就是在查詢的where子句中手動指定使用的哈希函數 下面是一個實例,例如需要存儲大量的URL,并需要根據URL進行搜索查找,如果使用B-Tree來存儲URL,存儲的內容就會很大,因為URL本身很長.正常情況下會有如下查詢 ~~~ select id from url where url = "http://www.mysql.com" ~~~ 若刪除原來URL列上的索引,而新增一個被索引的url_crc列,使用CRC32做哈希,就可以使用下面的方式查詢 ~~~ select id from url where url="http://www.mysql.com" and url_crc=CRC32("http://www.mysql.com"); ~~~ 這樣做的性能會非常高,因為mysql優化器會使用這個選擇性很高而體積很小的基于url_crc列的索引來完成查找(在上面的案列中,索引值為1560514994).即使有多個記錄相同的索引值,查找仍然很快,只需要根據哈希值做快速的整數比較就能找到索引條目,然后一一比較返回對應的行.另外一種方式就是對完整的URL字符串做索引,那樣會非常慢 這樣實現的缺陷是需要維護哈希值.可以手動維護,也可以使用觸發器實現.下面的案列演示了觸發器如何在插入和更新時維護url_crc列.首先創建如下表  然后創建觸發器.先臨時修改一下語句分割符,這樣就可以在觸發器定義中使用分號  剩下的就是驗證一下觸發器如何維護哈希索引  如果采用這種方式,記住不要使用sha1()和md5()作為哈希函數.因為這兩個函數計算出來的哈希值是非常長的字符串,會浪費大量的空間,比較時也會更慢.sha1()和md5()是強加密函數,設計目標是最大限度消除沖突,但這里并不需要達到這樣高的要求.簡單哈希函數的沖突在一個可以接受的范圍,同時又能夠提供更好的性能 如果數據表非常大,CRC32()會出現大量的哈希沖突,則可以考慮自己實現一個簡單的64位哈希函數. 這個自定義函數要返回整數而不是字符串.一個簡單的方法可以使用MD5()函數的返回值的一部分來作為自定義哈希函數.這可能比自己寫一個哈希算法的性能要差,不過這樣實現最簡單  處理哈希沖突,當使用哈希索引進行查詢的時候,必須在where子句中包含常量值 ~~~ select id from url where url_crc=CRC32("http://www.mysql.com") and url="http://www.mysql.com"; ~~~ 一旦出現哈希沖突,另一個字符串的哈希值也恰好是1560514994,則下面的查詢是無法正確工作 ~~~ select id from url where url_crc=CRC32("http://www.mysql.com"); ~~~ 因為所謂的"生日悖論",出現哈希沖突的概念的增長速度可能比想象的要快得多.CRC32()返回的是32位的整數,當索引有9300條記錄時出現沖突的概率是1%.例如我們將/usr/share/dict/words中的詞導入數據表并進行CRC32()計算,最后會有98569行這就已經出現一次哈希沖突,沖突讓下面的查詢返回了多條記錄  正確的寫法應該如下  要避免沖突問題,必須在where條件中帶入哈希值和對應列值.如果不是想查詢具體值,例如只是統計記錄數(不精確的),則可以不帶入列值,直接使用CRC32()的哈希值查詢即可.還可以使用如FNV64()函數作為哈希函數,哈希值64位,速度快,而且沖突比CRC32()要少很多