本文是針對(duì)Mysql索引原理剖析的入門級(jí)文章，主要圍繞以下四個(gè)話題展開(kāi)對(duì)索引相關(guān)原理的描述。

• 一丶索引基本概念
• 二丶(B+)-Tree索引基本實(shí)現(xiàn)
• 三丶關(guān)于Mysql索引常見(jiàn)術(shù)語(yǔ)解疑(聚族索引，非聚族索引，最左前綴原則, 索引覆蓋,哈希索引,自適應(yīng)哈希索引)
• 四丶索引局限性

一丶索引基本概念

對(duì)照著生活中的概念，數(shù)據(jù)庫(kù)索引的概念理解起來(lái)比較容易。數(shù)據(jù)庫(kù)的索引相當(dāng)于書籍的目錄。

• 書籍目錄：
  查閱書籍內(nèi)容時(shí)可對(duì)照著目錄，直接定位到想查閱內(nèi)容的具體頁(yè)數(shù)，避免逐頁(yè)翻書的工作量
• 數(shù)據(jù)庫(kù)索引:
  某條查詢sql語(yǔ)句可以對(duì)照數(shù)據(jù)表中的索引，直接定位到符合查詢條件的數(shù)據(jù)行的物理地址，避免對(duì)數(shù)據(jù)表進(jìn)行全表掃描的工作。
  上述概念關(guān)于索引的概念很簡(jiǎn)單，但是包含了很多的信息量。進(jìn)一步挖掘如下:
  1. 索引是建立數(shù)據(jù)表上的，每張數(shù)據(jù)表都可以有自己的索引。并且數(shù)據(jù)表中的索引可以有多個(gè)，但是不能設(shè)置重復(fù)的索引。
  2. 索引更具體一點(diǎn)來(lái)說(shuō)，其是建立在數(shù)據(jù)表的相關(guān)列上, 畢竟只有索引建立在列上才能和查詢條件相關(guān)聯(lián)嘛。若索引在一個(gè)列上建立稱為單一索引，若索引在多個(gè)列上建立成為復(fù)合索引。在表table1中的col1，col2，col3列上建立名為indx1的索引的sql語(yǔ)句如下:
     create index idx1 on table1(col1,col2,col3)
     這里需要特別注意，索引和建立索引時(shí)的數(shù)據(jù)列順序有關(guān)，比如在col3，col2，col1這三個(gè)列上建立名為idx2的索引和上述idx1索引是不同的索引。這是一個(gè)非常重要的概念
  3. 索引是一個(gè)獨(dú)立于數(shù)據(jù)表的結(jié)構(gòu)，就像書籍一樣，目錄和正文分屬于不同的部分。數(shù)據(jù)表的內(nèi)容發(fā)生了改變了，那么索引的結(jié)構(gòu)也會(huì)發(fā)生相應(yīng)調(diào)整，簡(jiǎn)而言之，索引的更新和數(shù)據(jù)表內(nèi)容的更新保持一致。
     該條具體一點(diǎn)就是，在對(duì)建立了索引的相關(guān)列進(jìn)行增刪改操作時(shí)，會(huì)附加維護(hù)索引結(jié)構(gòu)的相關(guān)操作。未建立索引的列則不需要考慮這個(gè)性能消耗。
  4. 索引提高查詢的性能，索引通過(guò)避免全表掃描，減少掃描行的數(shù)量來(lái)提高查詢的性能。
  5. 對(duì)于一條簡(jiǎn)單的查詢來(lái)說(shuō)，是如何使用索引查詢的呢？
     select * from table1 where col1 = A and col2 = B and col3 = C 這條查詢就利用idx1這個(gè)索引。目前來(lái)看，非常簡(jiǎn)單查詢條件和索引列完全一致就可以利用索引完成查詢避免全表掃描。此處注意，查詢條件的順序和索引建立是的順序是一致的，后續(xù)的關(guān)于索引的最左前綴原則會(huì)進(jìn)一步描述，此處記住是一致的就行

二丶(B+)-Tree索引基本實(shí)現(xiàn)

(B+)-Tree是一個(gè)數(shù)據(jù)結(jié)構(gòu)，是一個(gè)平衡的多路查找二叉樹(shù)。Mysql innodb引擎中建立的索引默認(rèn)就是基于(B+)-Tree實(shí)現(xiàn)的索引。

• B-Tree和(B+)-Tree數(shù)據(jù)結(jié)構(gòu)基本概念
  關(guān)于B-Tree和(B+)-Tree數(shù)據(jù)結(jié)構(gòu)具體特性參見(jiàn)該篇文章，本文借用上篇文章中的圖來(lái)剖析B-Tree是如何構(gòu)建索引的。
  
  (B+)-Tree
  
  
  B-Tree
  
  上圖就是B+樹(shù)和B樹(shù)結(jié)構(gòu)圖，非常清晰。B樹(shù)和B+樹(shù)之間有兩點(diǎn)最大的不同:

1. B+樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)了所有的數(shù)據(jù)，非葉子節(jié)點(diǎn)中存儲(chǔ)的是比較關(guān)鍵字。而B(niǎo)數(shù)所有的節(jié)點(diǎn)都會(huì)存儲(chǔ)數(shù)據(jù)。例如，在B+樹(shù)中查找數(shù)字26的過(guò)程是 p1->p3->26,最終在葉子節(jié)點(diǎn)里找到了待查找數(shù)字26。在B樹(shù)中查找數(shù)字26，查找的順序是p2->26,在非葉子節(jié)點(diǎn)中查找到了數(shù)據(jù)就返回。
2. B+樹(shù)的葉子節(jié)點(diǎn)之間存在一個(gè)指針連接，B樹(shù)不存在指針連接。B+樹(shù)這種設(shè)計(jì)結(jié)構(gòu)能帶來(lái)什么好處呢？
   B+樹(shù)所有的數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)，那么順著葉子節(jié)點(diǎn)從左往右即可完成對(duì)數(shù)據(jù)的遍歷，極大了簡(jiǎn)化了排序操作。這也是mysql設(shè)計(jì)索引是采用B+樹(shù)的原因，不僅僅能方便查找，而且有助于排序，在mysql的索引中葉子節(jié)點(diǎn)之間數(shù)雙向鏈表可正反遍歷，更加靈活

• B+樹(shù)和Mysql索引之間關(guān)系
  介紹關(guān)于B+樹(shù)數(shù)據(jù)結(jié)構(gòu)的相關(guān)內(nèi)容后，如何將其與索引聯(lián)系在一起呢？請(qǐng)看下圖

  
  
  B+樹(shù)和索引之間的關(guān)系
  
  

  在一張數(shù)據(jù)表的整型id上建立一個(gè)索引，該索引對(duì)應(yīng)的B+樹(shù)結(jié)構(gòu)如上圖所示。在B+樹(shù)中通過(guò)主鍵之間的比較，最終在葉子節(jié)點(diǎn)將找到指向數(shù)據(jù)表中對(duì)應(yīng)數(shù)據(jù)行的指針。通過(guò)訪問(wèn)指針即可拿到需查找的數(shù)據(jù)，通過(guò)這種方式可以避免對(duì)數(shù)據(jù)表全表掃描。極大的減少了檢索數(shù)據(jù)的時(shí)間

三丶關(guān)于Mysql常見(jiàn)術(shù)語(yǔ)的解疑

1. 聚族索引和非聚族索引

聚族索引和非聚族索引指的是存儲(chǔ)結(jié)構(gòu)
Mysql中InnoDB存儲(chǔ)引擎是采用聚族索引的存儲(chǔ)方式，是在主鍵上建立的聚族索引，MyISAM則是非聚族索引的方式。下文引用《高性能Mysql第三版167頁(yè)的一張圖解釋下聚族索引和非聚族索引》

聚族索引和非聚族索引

2. 索引覆蓋

理解索引的存儲(chǔ)結(jié)構(gòu)后，理解索引的覆蓋就非常簡(jiǎn)單了。如果select語(yǔ)句所查詢的字段全部都是索引列的話，稱為索引覆蓋。

1. 對(duì)于聚族索引而言，如果滿足索引覆蓋，那么不用通過(guò)主鍵訪問(wèn)聚族索引。
2. 對(duì)于非聚族索引而言，如果滿足索引覆蓋，那么不需要再次訪問(wèn)數(shù)據(jù)表。
   在滿足索引覆蓋的條件下，select語(yǔ)句從索引文件從就可以拿到所查詢的數(shù)據(jù)，而不必訪問(wèn)數(shù)據(jù)行。

3. 最左前綴原則

最左前綴原則就是Mysql通過(guò)索引檢索數(shù)據(jù)時(shí)必須遵守的原則。最左前綴原則的內(nèi)容規(guī)定如下，滿足如下情況，將使用索引查詢。

• 全值匹配，select語(yǔ)句中的查詢條件(查詢字段和字段順序)和索引完全對(duì)應(yīng)。
• 匹配最左前綴，select語(yǔ)句中的查詢條件并未和索引完全匹配。但是和索引最左側(cè)完全匹配。比如index(col1,col2,col3)，查詢條件(col1,col2)或者(col1)都成為匹配索引的最左前綴。
• 匹配列前綴，這是匹配最左前綴長(zhǎng)的特殊情況。查詢條件是匹配索引第一列的開(kāi)頭部分。比如 like col1 = aaa%。匹配索引第一列與aaa開(kāi)頭的數(shù)據(jù)行。
• 匹配范圍，針對(duì)索引的第一列，使用了范圍查詢。比如， col1<A。
• 精確匹配某一個(gè)列，范圍匹配某一列。比如col1 =A and col2<B。精確匹配的列必須是索引的最左列。

4. 哈希索引

哈希索引不同于以B+樹(shù)為存儲(chǔ)結(jié)構(gòu)的索引。哈希以哈希為存儲(chǔ)結(jié)構(gòu)組織索引。

image.png

• Hash索引檢索數(shù)據(jù)的速度比B+樹(shù)索引更快
• Hash索引值只適用于全值匹配查詢，查詢條件和索引列必須完全一致。B+樹(shù)所適應(yīng)的最左前綴原則Hash索引并不適用
• Hash索引只能滿足精確匹配，比如查詢條件是==或者！=。并不能滿足范圍查詢的場(chǎng)景。

5. 自適應(yīng)哈希索引

自適應(yīng)Hash索引是InnoDB存儲(chǔ)引擎添加的一種優(yōu)化策略。InnoDB存儲(chǔ)引擎對(duì)那些查詢頻繁的索引條件，構(gòu)建一個(gè)hash索引。下若有相同的查詢語(yǔ)句，則直接命中hash索引，而不必走B+樹(shù)索引，能提高檢索速度。自適應(yīng)Hash索引是innoDB的一種優(yōu)化策略，對(duì)用戶而言是透明的。

四丶索引的局限性

有關(guān)索引局限性的討論是一個(gè)比較有難度的話題，其不像原理分析那樣固定。其在不同的業(yè)務(wù)場(chǎng)景下會(huì)有不同的結(jié)論。本文論文幾種索引常見(jiàn)分析，并未涵蓋所有情況

1. 什么情況需要建立索引？

• 當(dāng)數(shù)據(jù)表較小時(shí)，維護(hù)索引的代價(jià)將超過(guò)索引加速查詢所帶來(lái)的好處。數(shù)據(jù)表較大時(shí)，索引能夠極大加速查詢，適合創(chuàng)建索引。
• 對(duì)于那些，查詢多于增刪改的操作，建立索引是合適的。

2. 在什么列上建立索引

• 一般而言，選擇在選擇性比較高的列上建立索引。
• 選擇性 = 不重復(fù)的索引列/所有數(shù)據(jù)行數(shù)。選擇性越接近于1越好。

3. 索引建立的順序。

• 受限于索引的最左前綴原則，索引建立的順序并不能是隨意的，應(yīng)該和查詢場(chǎng)景相互印證。讓索引順序能滿足最多的查詢場(chǎng)景

4. 多列索引和多個(gè)單列索引

• 一般提供選擇建立多列索引，而不建立單例索引。多列索引能覆蓋單列索引的查詢條件。

5. 是否針對(duì)不同的查詢條件，建立不同的索引

• 索引的建立是有代價(jià)的，包括索引存儲(chǔ)代價(jià)，數(shù)據(jù)增刪改的性能下降。對(duì)不同查詢條件建立索引，需要仔細(xì)考慮。
  受限于作者水平，關(guān)于索引局限性的討論，并不一定正確。在不同的場(chǎng)景，具有不同的選擇。