MySQL中的索引
索引設(shè)計(jì)和工作原理
先來(lái)看看索引設(shè)計(jì)和工作原理。想創(chuàng)建高性能索引，首先要了解什么是索引。維基百科對(duì)其定義：數(shù)據(jù)庫(kù)索引是一種數(shù)據(jù)結(jié)構(gòu)，它以額外的寫入和存儲(chǔ)空間為代價(jià)來(lái)提高數(shù)據(jù)庫(kù)表上數(shù)據(jù)檢索操作的速度。通俗來(lái)說(shuō)，索引類似于書的目錄，根據(jù)其中記錄的頁(yè)碼可以快速找到所需的內(nèi)容。
MySQL 官方對(duì)索引（Index）的定義是存儲(chǔ)引擎用于快速查找記錄的一種數(shù)據(jù)結(jié)構(gòu)。
索引是物理數(shù)據(jù)頁(yè)，數(shù)據(jù)庫(kù)頁(yè)大?。≒age Size）決定了一個(gè)頁(yè)可以存儲(chǔ)多少個(gè)索引行，以及需要多少頁(yè)來(lái)存儲(chǔ)指定大小的索引。
索引可以加快檢索速度，但同時(shí)也降低索引列插入、刪除、更新的速度，索引維護(hù)需要代價(jià)。
索引涉及的理論知識(shí)有二分查找法、哈希表及 B+Tree。
二分查找法
二分查找法也叫作折半查找法，它是在有序數(shù)組中查找指定數(shù)據(jù)的搜索算法。如下圖所示是維基百科對(duì)二分查找法的定義。它的優(yōu)點(diǎn)是等值查詢、范圍查詢性能優(yōu)秀，缺點(diǎn)是更新數(shù)據(jù)、新增數(shù)據(jù)、刪除數(shù)據(jù)維護(hù)成本高。
舉個(gè)例子，有序數(shù)組 [1-71] 有 17 個(gè)值, 即在有序數(shù)組 [A0-A16] 中希望找到 Target(7)所在的位置，首選確定下標(biāo) L 為 0，下標(biāo) R 為 16，下標(biāo) m 為 floor [( L+R)/2]，即向下取整數(shù)。
第一次查詢
下標(biāo) L=0，R=16，m= floor[(0+16)/2]=8，獲得 A8 的值為 14，因?yàn)?A8(14) >Target(7) 則設(shè)置 R=m-1=7，如下圖所示。
第二次查詢
下標(biāo) L=0，R=7，m=floor[(0+7)/2]=3，獲得 A3 的值為 6，A3(6) < Target(7) 則設(shè)置下標(biāo) L=m+1=4，如下圖所示。
第三次查詢
下標(biāo) L=4，R=7，m=floor[(4+7)/2]=5，獲得 A5 的值為 8，A5(8) > Target(7) 則設(shè)置下標(biāo) R=m-1=4，如下圖所示。
第四次查詢
下標(biāo) L=4，R=4，m=floor[(4+4)/2]=4，獲得 A4 的值為 7，A4(7) = Target(7)，查詢結(jié)束，如下圖所示。
此次查詢經(jīng)過(guò) 4 次二分查找后找到目標(biāo)數(shù)據(jù) 7，如果在查詢過(guò)程中出現(xiàn)下標(biāo) L>R 的情況，則表示目標(biāo)元素不在有序數(shù)組內(nèi)，結(jié)束查詢。
二分查找是索引實(shí)現(xiàn)的理論基礎(chǔ)，對(duì)接下來(lái)的索引學(xué)習(xí)很有幫助。
索引原理
大家都知道數(shù)據(jù)庫(kù)查詢是數(shù)據(jù)庫(kù)的核心功能，而索引又是作為加速查詢的重要技術(shù)手段。對(duì)于索引數(shù)據(jù)結(jié)構(gòu)的選擇其本質(zhì)是貼合當(dāng)前數(shù)據(jù)讀寫的硬件環(huán)境選擇一個(gè)優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)進(jìn)行數(shù)據(jù)存儲(chǔ)及遍歷，在數(shù)據(jù)庫(kù)中大部分索引都是通過(guò) B+Tree 來(lái)實(shí)現(xiàn)的。當(dāng)然也涉及其他數(shù)據(jù)結(jié)構(gòu)，在 MySQL 中除了 B+Tree 索引外我們還需要關(guān)注下 Hash 索引。
接下來(lái)我們對(duì) Hash 索引、B+Tree 索引逐一展開學(xué)習(xí)。因?yàn)楹罄m(xù)大部分內(nèi)容都是講 B 樹的，為了讓 B 樹的內(nèi)容更連貫，這里先講 Hash 索引。
Hash 索引
哈希表是數(shù)據(jù)庫(kù)中哈希索引的基礎(chǔ)，是根據(jù)鍵值 <key,value> 存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)。簡(jiǎn)單說(shuō)，哈希表是使用哈希函數(shù)將索引列計(jì)算到桶或槽的數(shù)組，實(shí)際存儲(chǔ)是根據(jù)哈希函數(shù)將 key 換算成確定的存儲(chǔ)位置，并將 value 存放到該數(shù)組位置上。訪問(wèn)時(shí)，只需要輸入待查找的 key，即可通過(guò)哈希函數(shù)計(jì)算得出確定的存儲(chǔ)位置并讀取數(shù)據(jù)。
如下圖所示，姓名作為 key，通過(guò)哈希函數(shù)對(duì)姓名字段數(shù)據(jù)進(jìn)行計(jì)算，得到哈希碼并存放到桶或槽的數(shù)組中，同時(shí)存放指向真實(shí)數(shù)據(jù)行的指針作為 value，形成哈希表。
接下來(lái)我們從哈希索引如何實(shí)現(xiàn)、Hash 碰撞處理、MySQL 如何使用 Hash，三個(gè)方面學(xué)習(xí)哈希索引。
首先講解哈希索引是如何實(shí)現(xiàn)的？數(shù)據(jù)庫(kù)中哈希索引是基于哈希表實(shí)現(xiàn)的，對(duì)于哈希索引列的數(shù)據(jù)通過(guò) Hash 算法計(jì)算，得到對(duì)應(yīng)索引列的哈希碼形成哈希表，由哈希碼及哈希碼指向的真實(shí)數(shù)據(jù)行的指針組成了哈希索引。哈希索引的應(yīng)用場(chǎng)景是只在對(duì)哈希索引列的等值查詢才有效。
如下圖所示，根據(jù)表中的 name 字段構(gòu)建 Hash 索引，通過(guò) Hash 算法對(duì)每一行 name 字段的數(shù)據(jù)進(jìn)行計(jì)算，得出 Hash 碼。由 Hash 碼及 Hash 碼指向真實(shí)數(shù)據(jù)行的指針組成了哈希索引。
因?yàn)楣Ｋ饕淮鎯?chǔ)哈希值和行指針，不存儲(chǔ)實(shí)際字段值，所以其結(jié)構(gòu)緊湊，查詢速度也非?？?，在無(wú)哈希沖突的場(chǎng)景下訪問(wèn)哈希索引一次即可命中。但是哈希索引只適用于等值查詢，包括 =、IN()、<=> （安全等于， select null <=> null 和 select null=null 是不一樣的結(jié)果) ，不支持范圍查詢。
另外，哈希索引的性能跟哈希沖突數(shù)量成反比，哈希沖突越多其維護(hù)代價(jià)越大性能越低。
接下來(lái)我們看看 Hash 碰撞如何處理？Hash 碰撞是指不同索引列值計(jì)算出相同的哈希碼，如上圖所示， 表中 name 字段為 John Smith 和 Sandra Dee 兩個(gè)不同值根據(jù) Hash 算法計(jì)算出來(lái)的哈希碼都是 152，這就表示出現(xiàn)了 Hash 碰撞。 對(duì)于 Hash 碰撞通用的處理方法是使用鏈表，將 Hash 沖突碰撞的元素形成一個(gè)鏈表，發(fā)生沖突時(shí)在鏈表上進(jìn)行二次遍歷找到數(shù)據(jù)。
Hash 碰撞跟選擇的 Hash 算法有關(guān)系，為了減少 Hash 碰撞的概率，優(yōu)先選擇避免 Hash 沖突的 Hash 算法，例如，使用 Percona Server 的函數(shù) FNV64() ，其哈希值為 64 位，出現(xiàn) Hash 沖突的概率要比 CRC32 小很多。
其次是考慮性能，優(yōu)先選擇數(shù)字類型的 Hash 算法，因?yàn)樽址愋偷?Hash 算法不僅浪費(fèi)空間而且不方便進(jìn)行比較。
常見的 CRC32、SHA1 和 MD5 Hash 函數(shù)生成的返回值如下圖所示。
綜合建議 Hash 算法使用優(yōu)先級(jí)為：FNV64 > CRC32 （大數(shù)據(jù)量下 Hash 沖突概率較大）> MD5 > SHA1。
最后再看看，MySQL 中如何使用 Hash 索引？在 MySQL 中主要是分為 Memory 存儲(chǔ)引擎原生支持的 Hash 索引 、InnoDB 自適應(yīng)哈希索引及 NDB 集群的哈希索引3類。
Memory 存儲(chǔ)引擎原生支持的 Hash 索引，如上圖所示，Memory 存儲(chǔ)引擎創(chuàng)建表時(shí)即可原生顯式創(chuàng)建并使用 Hash 索引。
相比 InnoDB，雖然不能原生顯示創(chuàng)建 Hash 索引，但是可以偽造哈希索引來(lái)加速定值查詢的性能。例如為超長(zhǎng)文本（如網(wǎng)站 URL）進(jìn)行 Hash 計(jì)算后的字段 url_hash 創(chuàng)建 B+Tree 索引，獲得 Hash 索引的功能。
關(guān)于哈希索引，InnoDB 提供了 InnoDB 自適應(yīng)哈希索引的強(qiáng)大功能，接下來(lái)重點(diǎn)描述 InnoDB 自適應(yīng)哈希索引。
InnoDB 自適應(yīng)哈希索引是為了提升查詢效率，InnoDB 存儲(chǔ)引擎會(huì)監(jiān)控表上各個(gè)索引頁(yè)的查詢，當(dāng) InnoDB 注意到某些索引值訪問(wèn)非常頻繁時(shí)，會(huì)在內(nèi)存中基于 B+Tree 索引再創(chuàng)建一個(gè)哈希索引，使得內(nèi)存中的 B+Tree 索引具備哈希索引的功能，即能夠快速定值訪問(wèn)頻繁訪問(wèn)的索引頁(yè)。
B+Tree 索引
在數(shù)據(jù)庫(kù)中大部分索引都是通過(guò) B+Tree 來(lái)實(shí)現(xiàn)的。 對(duì)于 B+Tree 具體的定義可以參考《數(shù)據(jù)結(jié)構(gòu)》等相關(guān)書籍。 在 MySQL 數(shù)據(jù)庫(kù)中討論索引時(shí)，如果沒(méi)有明確指定類型，則默認(rèn)是指使用 B+Tree 數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)，其說(shuō)法等價(jià)于 B+Tree、B-Tree、BTREE（看到創(chuàng)建索引語(yǔ)句為 BTREE 也不要驚訝，等同于 B+Tree）。
如下圖所示為一個(gè)簡(jiǎn)單的、標(biāo)準(zhǔn)的 B+tree，每個(gè)節(jié)點(diǎn)有 K 個(gè)鍵值和 K+1 個(gè)指針。
對(duì)于 MySQL 存儲(chǔ)引擎而言，其實(shí)際使用的 B+Tree 索引是為了滿足數(shù)據(jù)讀寫性能，以及適配磁盤訪問(wèn)模式優(yōu)化后的數(shù)據(jù)結(jié)構(gòu)，每一個(gè)葉子節(jié)點(diǎn)都包含指向下一個(gè)葉子節(jié)點(diǎn)的指針。
在 MySQL 中，索引是在存儲(chǔ)引擎層而非服務(wù)器層實(shí)現(xiàn)的，所以不同存儲(chǔ)引擎層支持的索引類型可以不同。例如，雖然 MyISAM 和 InnoDB 的索引都是使用 B+Tree 實(shí)現(xiàn)的，但是其實(shí)際數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有不少差異。下圖中 B+Tree 示例一共2層，圖中每個(gè)頁(yè)面都已經(jīng)被隨機(jī)編號(hào)（編號(hào)可以認(rèn)定為頁(yè)面號(hào)），其中頁(yè)面號(hào)為 20 的頁(yè)面是 B+Tree 的根頁(yè)面（根頁(yè)面通常是存放在內(nèi)存中的），根頁(yè)面存儲(chǔ)了 <key+pageno>，pageno 是指向具體葉子節(jié)點(diǎn)的頁(yè)面號(hào)。其他頁(yè)面都是葉子節(jié)點(diǎn)，存放了具體的數(shù)據(jù) <key+data>。
B+Tree 索引能夠快速訪問(wèn)數(shù)據(jù)，就是因?yàn)榇鎯?chǔ)引擎可以不再需要通過(guò)全表掃描來(lái)獲取數(shù)據(jù)，而是從索引的根結(jié)點(diǎn)（通常在內(nèi)存中）開始進(jìn)行二分查找，根節(jié)點(diǎn)的槽中都存放了指向子節(jié)點(diǎn)的指針，存儲(chǔ)引擎根據(jù)這些指針能夠快速遍歷數(shù)據(jù)。例如，通過(guò)頁(yè)面號(hào)為 20 的根節(jié)點(diǎn)可以快速得知 Key<10 的數(shù)據(jù)在 pageno 33 的頁(yè)面，key在 [10,16) 范圍的數(shù)據(jù)在 pageno 56 的頁(yè)面。
葉子節(jié)點(diǎn)存放的 <key+data> ，對(duì)于真正要存放哪些數(shù)據(jù)還得取決于該 B+Tree 是聚簇索引（Clustered Index）還是輔助索引（Secondary Index）。
聚簇索引和輔助索引
聚簇索引是一種數(shù)據(jù)存儲(chǔ)方式，它表示表中的數(shù)據(jù)按照主鍵順序存儲(chǔ)，是索引組織表。InnoDB 的聚簇索引就是按照主鍵順序構(gòu)建 B+Tree，B+Tree 的葉子節(jié)點(diǎn)就是行記錄，數(shù)據(jù)行和主鍵值緊湊地存儲(chǔ)在一起。 這也意味著 InnoDB 的主鍵索引就是數(shù)據(jù)表本身，它按主鍵順序存放了整張表的數(shù)據(jù)。
而 InnoDB 輔助索引（也叫作二級(jí)索引）只是根據(jù)索引列構(gòu)建 B+Tree，但在 B+Tree 的每一行都存了主鍵信息，加速回表操作。
聚簇索引占用的空間就是整個(gè)表數(shù)據(jù)量的大小，而二級(jí)索引會(huì)比聚簇索引小很多， 通常創(chuàng)建輔助索引就是為了提升查詢效率
InnoDB 只能創(chuàng)建一個(gè)聚簇索引（假想下如果能支持多個(gè)聚簇索引，那就意味著一張表按不同排序規(guī)則冗余存儲(chǔ)多份全表數(shù)據(jù)了），但可以創(chuàng)建多個(gè)輔助索引。
相比索引組織表，還有一種堆表類型，堆表是根據(jù)數(shù)據(jù)寫入的順序直接存儲(chǔ)在磁盤上的。對(duì)于堆表而言，其主鍵和輔助索引唯一的區(qū)別就是鍵值是否唯一，兩者都是根據(jù)索引列排序構(gòu)建 B+Tree 的，在每個(gè)葉子節(jié)點(diǎn)加上指向堆表的行指針（row data pointer） 。堆表在各類數(shù)據(jù)庫(kù)中也被廣泛使用，MyISAM 存儲(chǔ)引擎的表就是堆表。
