索引基礎(chǔ)

索引的類型

B-Tree索引

當(dāng)人們談?wù)撍饕龝r(shí)，如果沒有特別指明類型，那多半說(shuō)的是B-Tree索引。
存儲(chǔ)引擎以不同的方式使用B-Tree索引，性能也各有不同，各有優(yōu)劣。例如，MyISAM使用前綴壓縮技術(shù)使得索引更小，但I(xiàn)nnoDB則按照數(shù)據(jù)格式進(jìn)行存儲(chǔ)。再如MyISAM索引通過數(shù)據(jù)的屋里位置引用被索引的行，而InnoDB則根據(jù)主鍵引用被索引的行。

B-Tree索引能夠加快訪問數(shù)據(jù)的速度，因?yàn)榇鎯?chǔ)引擎不再需要進(jìn)行全表掃描來(lái)獲取需要的數(shù)據(jù)，取而代之的是從索引的根節(jié)點(diǎn)開始進(jìn)行搜索。
B-Tree對(duì)索引列是順序組織存儲(chǔ)的，所以很適合查找范圍數(shù)據(jù)。

B-Tree索引適用于全鍵值，鍵值范圍或鍵前綴查找。

• 全值匹配
  全值匹配是指和索引中的所有列進(jìn)行匹配。
• 匹配最左前綴
  可以查找只使用索引的第一列。
• 匹配列前綴
  也可以只匹配某一列的值的開頭部分。
• 匹配范圍值
• 精確匹配某一列并范圍匹配另外一列
• 只訪問索引的查詢
  B-Tree通常可以支持“只訪問索引的查詢”，即查詢只需要訪問索引，而無(wú)需訪問數(shù)據(jù)行。

B-Tree索引的限制：

• 如果不是按照索引的最左列開始查找，則無(wú)法使用索引。
• 不能跳過索引中的列。
• 如果查找中有某個(gè)列的范圍查詢，則其右邊所有列都無(wú)法使用索引優(yōu)化查找。

哈希索引

哈希索引基于哈希表實(shí)現(xiàn)，只有精確匹配索引所有列的查詢才有效。
在mysql中，只有memory引擎顯示支持哈希索引，這也是memory引擎的默認(rèn)索引類型。memory引擎是支持非唯一索引的，如果多個(gè)列的哈希值相同，索引會(huì)以鏈表的方式存放多嗯記錄指針到同一個(gè)哈希條目中。

因?yàn)樗饕恍枰鎯?chǔ)對(duì)應(yīng)的哈希值，所以索引的結(jié)構(gòu)十分緊湊，這也讓哈希索引查找的速度非?？臁?/p>

哈希索引的限制：

• 哈希索引只包含哈希值和行指針，而不存儲(chǔ)字段值，所以不能使用索引中的值來(lái)避免讀取行。不過，訪問內(nèi)存中的行的速度很快，所以大部分情況下這一點(diǎn)對(duì)性能的影響并不明顯。
• 哈希索引數(shù)據(jù)并不是按照索引值順序存儲(chǔ)的，所以無(wú)法用于排序。
• 哈希索引也不支持部分索引列匹配查找，因?yàn)楣Ｋ饕冀K是列的全部?jī)?nèi)容來(lái)計(jì)算哈希值。例如在數(shù)據(jù)列（A，B）上建立哈希索引，如果查詢只有數(shù)據(jù)列A，則無(wú)法使用該索引。
• 哈希索引只支持等值比較，包括 = , in(), <=> （注意 <> 和 <=> 是不同的操作），也不支持任何范圍查詢。
• 訪問哈希索引的數(shù)據(jù)非?？欤怯泻芏喙_突（不同的索引列值卻有相同的哈希值）。當(dāng)出現(xiàn)哈希沖突的時(shí)候，存儲(chǔ)引擎必須遍歷鏈表中所有的行指針，逐行進(jìn)行比較，直到找到所有符合條件的行。
• 如果哈希沖突很多的話，一些索引維護(hù)操作的代價(jià)也會(huì)很高。沖突越大，代價(jià)越大。

創(chuàng)建自定義哈希索引。

在B-Tree基礎(chǔ)上創(chuàng)建一個(gè)偽哈希索引，這和真正的哈希索引不是一回事，因?yàn)檫€是使用B-Tree進(jìn)行查找，但是它使用哈希值而不是鍵本身進(jìn)行索引查找。查詢時(shí)，在where子句中手動(dòng)指定使用哈希函數(shù)。

例如需要存儲(chǔ)大量的URL，并需要根據(jù)URL進(jìn)行搜索查找。如果使用B-Tree來(lái)存儲(chǔ)URL，存儲(chǔ)的內(nèi)容就會(huì)很大，因?yàn)閁RL本身都很長(zhǎng)。新增一個(gè)被索引的 url_crc列，使用CRC32做哈希，就可以使用下面的方式查詢：

select id from url where url="http://www.mysql.com" and url_crc=CRC32("http://www.mysql.com");

這樣做的性能會(huì)很高，因?yàn)閙ysql優(yōu)化器會(huì)使用這個(gè)選擇性很高而體積很小的基于 url_crc 列的索引來(lái)完成查找。即使有多個(gè)記錄有相同的索引值，查找仍然很快，只需要根據(jù)哈希值做快速的整數(shù)比較就能找到索引條目，然后一一比較返回對(duì)應(yīng)的行。
另外一種方式是對(duì)完整的url字符串做索引，那樣會(huì)非常慢。
如果采用這種方式，記住不要使用sha1()和md5()作為哈希函數(shù)，因?yàn)檫@兩個(gè)函數(shù)計(jì)算出來(lái)的哈希值是非常長(zhǎng)的字符串，會(huì)浪費(fèi)大量空間，比較時(shí)也會(huì)更慢。

還可以使用如FNV64()函數(shù)作為哈希函數(shù)，這時(shí)移植自Percona Server的函數(shù)，可以以插件的方式在任何mysql版本中使用，哈希值為64位，速度快，沖突比CRC32要少很多。

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

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

高性能的索引策略

獨(dú)立的列

獨(dú)立的列是指索引列不能是表達(dá)式的一部分，也不能是函數(shù)的參數(shù)。
下面這個(gè)查詢無(wú)法使用 actor_id 列的索引：

select actor_id from actor where actor_id + 1 = 5;

前綴索引和索引選擇性

有時(shí)候需要索引很長(zhǎng)的字符串，這回讓索引變的大且慢，一個(gè)策略是前面提到過的模擬哈希索引。但有時(shí)候這樣做還不夠，還可以做些什么呢？

通?？梢运饕_始的部分字符，這樣可以大大節(jié)約索引空間，從而提高索引效率。
索引的選擇性是指，不重復(fù)的索引值和數(shù)據(jù)表的記錄總數(shù)的比值，范圍從 1/#T 到 1 之間。索引的選擇性越高則查詢效率越高，因?yàn)檫x擇性高的索引可以讓msyql在查找時(shí)過濾掉更多的行。
唯一索引的選擇性是1，這時(shí)最好的索引選擇性，性能也是最好的。

多列索引

很多人對(duì)多列索引理解不夠，一個(gè)常見的錯(cuò)誤是，為每個(gè)列創(chuàng)建獨(dú)立的索引，或者按照錯(cuò)誤的順序創(chuàng)建多列索引。
在多個(gè)列上建立獨(dú)立的單列索引，大部分情況下都不能提高mysql的查詢能力。
mysql5.0和更新的版本引入了一種叫做“索引合并”的策略，一定程度上可以使用表上的多個(gè)單列索引來(lái)定位指定的行。
例如，表 file_actor 在字段 file_id 和 actor_id 各有一個(gè)單列的索引，但對(duì)于下面的查詢where條件，這兩個(gè)索引都不是最好的選擇：

select file_id , actor_id from file_actor
where actor_id=1 or file_id=1;

在老的mysql版本中，mysql會(huì)對(duì)這個(gè)查詢使用全表掃描，除非改寫為兩個(gè)查詢 union 操作：

select file_id,actor_id from file_actor where actor_id=1
union all
select file__id,actor_id from file_actor where file_id=1;

但在mysql5.0和更新的版本中，查詢能夠同時(shí)使用這兩個(gè)單列索引進(jìn)行掃描，并將結(jié)果進(jìn)行合并。
這種算法有三個(gè)變種：OR條件的聯(lián)合（union），AND條件的相交（intersection），組合前兩種情況的聯(lián)合及相交。
下面的查詢就是使用了兩個(gè)索引掃描的聯(lián)合，通過 EXPLAIN 中的 Extra 列可以看到這點(diǎn)：

explain select file_id, actor_id from file_actor where actor_id=1 or file_id=1;
**************************************** 1 row ****************************
id: 1
select_type: simple
table: film_actor
type: index_merge
possible_keys: primary,idx_fk_film_id
key: primary,idx_fk_film_id
ken_len: 2,2
ref: null
rows: 29
extra: using union(primary,idx_fk_film_id);using where

索引合并策略有時(shí)候是一種優(yōu)化的結(jié)果，但實(shí)際上更多時(shí)候說(shuō)明了表上的索引建的很糟糕。

• 當(dāng)出現(xiàn)服務(wù)器對(duì)多個(gè)索引做相交操作時(shí)（通常有多個(gè)AND條件），通常意味著需要一個(gè)包含多個(gè)相關(guān)列的多列索引，而不是多個(gè)獨(dú)立的單列索引。
• 當(dāng)服務(wù)器需要對(duì)多個(gè)索引做聯(lián)合操作時(shí)（通常有多個(gè)OR條件），通常需要耗費(fèi)大量CPU和內(nèi)存資源在內(nèi)的算法的緩存，排序和合并操作上。特別是當(dāng)其中有些索引的選擇性不高，需要合并掃描返回的大量數(shù)據(jù)的時(shí)候。
• 更重要的是，優(yōu)化器不會(huì)把這些計(jì)算到查詢成本中，優(yōu)化器只關(guān)心隨機(jī)頁(yè)面讀取。這會(huì)使得查詢的成本被低估，導(dǎo)致該執(zhí)行計(jì)劃還不如直接走全表掃描。

選擇合適的索引順序

我們遇到的最容易引起困惑的問題就是索引列的順序。正確的順序依賴于使用該索引的查詢，并且同時(shí)需要考慮如何更好的滿足排序和分組的需要。
在一個(gè)多列B-Tree索引中，索引列的順序意味著索引首先按照最左列進(jìn)行排序，其次是第二列，等等。
對(duì)于如何選擇索引的順序有一個(gè)經(jīng)驗(yàn)法則：將選擇性最高的列放到索引最前列。
當(dāng)不需要考慮排序和分組時(shí)，將選擇性最高的列放在前面通常是很好的。
然而，性能不只是依賴于所有索引列的選擇性，也和查詢條件的具體值有關(guān)，也就是和值分布有關(guān)。

聚簇索引

聚簇索引并不是一種單獨(dú)的索引類型，而是一種數(shù)據(jù)存儲(chǔ)方式。
InnoDB的聚簇索引實(shí)際上在同一個(gè)結(jié)構(gòu)中保存了B-Tree索引和數(shù)據(jù)行。
當(dāng)表有聚簇索引時(shí)，它的數(shù)據(jù)行實(shí)際上存放在索引的葉子頁(yè)（leaf page）中。聚簇表示數(shù)據(jù)行和相鄰的鍵值緊湊的存儲(chǔ)在一起。
因?yàn)闊o(wú)法同時(shí)把數(shù)據(jù)行存放在兩個(gè)不同的地方，所以一個(gè)表只能有一個(gè)聚簇索引。

InnoDB將通過主鍵聚簇?cái)?shù)據(jù)，如果沒有定義主鍵，InnoDB會(huì)選擇一個(gè)唯一的非空索引代替。
如果沒有這樣的索引，InnoDB會(huì)隱式定義一個(gè)主鍵來(lái)作為聚簇索引。
聚簇主鍵可能對(duì)性能有幫助，但也可能導(dǎo)致嚴(yán)重的性能問題。所以需要仔細(xì)的考慮聚簇索引，尤其是將表的存儲(chǔ)引擎從InnoDB改成其他引擎的時(shí)候（反過來(lái)也一樣）。

聚簇索引有一些重要的優(yōu)點(diǎn)：

• 可以把相關(guān)數(shù)據(jù)保存在一起。例如實(shí)現(xiàn)電子郵件時(shí)，可以根據(jù)用戶id來(lái)聚集數(shù)據(jù)，這樣只需要從磁盤讀取少量的數(shù)據(jù)頁(yè)就能獲取某個(gè)用戶的全部郵件。如果沒有使用聚簇索引，澤每封郵件可能導(dǎo)致一次磁盤I/O.
• 數(shù)據(jù)訪問更快。聚簇索引將索引和數(shù)據(jù)保存在同一個(gè)B-Tree中，因此從聚簇索引中獲取數(shù)據(jù)通常比非聚簇索引中查找更快。
• 使用覆蓋索引掃描的查詢可以直接使用頁(yè)節(jié)點(diǎn)中的主鍵值。

聚簇索引也有一些缺點(diǎn)：

• 聚簇?cái)?shù)據(jù)最大限度的提高了I/O密集型應(yīng)用的性能，但如果數(shù)據(jù)全部放在內(nèi)存中，則訪問的順序就沒那么重要了，聚簇索引也就沒什么優(yōu)勢(shì)了。
• 插入速度嚴(yán)重依賴插入順序。按照主鍵的順序插入是加載數(shù)據(jù)才InnoDB表中速度最快的方式。但如果不是按照主鍵順序加載數(shù)據(jù)，那么在加載完成后，最好使用 OPTIMIZE TABLE命令重新組織一下表。
• 更新聚簇索引的代價(jià)很高，因?yàn)闀?huì)強(qiáng)制InnoDB將每個(gè)被更新的行移動(dòng)到新的位置。
• 基于聚簇索引的表在插入新行，或者主鍵被更新導(dǎo)致需要移動(dòng)行的時(shí)候，可能面臨“頁(yè)分裂”的問題。當(dāng)行的主鍵值要求必須將這一行插入到某個(gè)已滿的頁(yè)中時(shí)，存儲(chǔ)引擎會(huì)將該頁(yè)分裂成兩個(gè)頁(yè)面來(lái)容納該行，這就是一次頁(yè)分裂操作。頁(yè)分裂會(huì)導(dǎo)致表占用更多的磁盤空間。
• 二級(jí)索引（非聚簇索引）可能比想象的要更大，因?yàn)樵诙?jí)索引的葉子節(jié)點(diǎn)包含了引用行的主鍵列。
• 二級(jí)索引訪問需要兩次索引查找，而不是一次。二級(jí)索引中保存的“行指針”的實(shí)質(zhì)，不是指向行的物理位置的指針，而是行的主鍵值。這意味著通過二級(jí)索引查找行，存儲(chǔ)引擎需要找到二級(jí)索引的葉子節(jié)點(diǎn)獲得對(duì)應(yīng)的主鍵值，然后再根據(jù)這個(gè)值去聚簇索引中查找到對(duì)應(yīng)的行。這里做了重復(fù)的工作，兩次B-Tree查找而不是一次。對(duì)于InnoDB，自適應(yīng)哈希索引能夠減少這樣的重復(fù)工作。

InnoDB和MyISAM的數(shù)據(jù)分布

來(lái)看看InnoDB和MyISAM是如何存儲(chǔ)下面的這個(gè)表的：

create table layout_test (
    col1 int not null,
    col2 int not null,
    primary key(col1),
    key(col2)
);

假設(shè)該表的主鍵取值 1-10000，按照隨機(jī)順序插入并使用 optimize table 命令做了優(yōu)化，也就是說(shuō)，數(shù)據(jù)在磁盤上的存儲(chǔ)方式已經(jīng)最優(yōu)，但行的順序是隨機(jī)的。列 col2 的值是從 1-100之間隨機(jī)賦值，所以有很多 重復(fù)的值。

• MyISAM 的數(shù)據(jù)分布

  
  
  myisam
  
  
  myisam
  
  

  上面兩圖展示了主鍵索引和普通索引的異同。
  事實(shí)上，myisam中主鍵索引和其他索引在結(jié)構(gòu)上沒有什么不同。
  主鍵索引就是一個(gè)名為 primary 的唯一非空索引。

• InnoDB 數(shù)據(jù)分布

  
  
  InnoDB主鍵索引
  
  

  聚簇索引的每一個(gè)葉子節(jié)點(diǎn)都包含了主鍵值，事務(wù)id,用于事務(wù)和MVCC的回滾指針以及所有的剩余列。如果主鍵是一個(gè)前列索引，InnoDB也會(huì)包含完成的主鍵列和剩下 的其他列。

InnoDB的二級(jí)索引和聚簇索引很不同。InnoDB二級(jí)索引的葉子節(jié)點(diǎn)中存儲(chǔ)的不是“行指針”，而是主鍵值，并以此作為指向行的“指針”。
這樣的策略減少了當(dāng)出現(xiàn)移動(dòng)行或者數(shù)據(jù)頁(yè)分裂時(shí)二級(jí)索引的維護(hù)工作。
使用主鍵值當(dāng)做指針會(huì)讓二級(jí)索引占用更多的空間，但換來(lái)的好處是，InnoDB在移動(dòng)行時(shí)，無(wú)需更新二級(jí)索引中的這個(gè)“指針”。

innodb二級(jí)索引

• MyISAM和InnoDB索引區(qū)別

  
  
  聚簇和非聚簇索引的對(duì)比圖

在InnoDB表中按主鍵順序插入行

避免隨機(jī)的（不連續(xù)且值的分布范圍比較大）聚簇索引，特別是對(duì)于I/O密集型的應(yīng)用。
從性能的角度考慮，使用uuid來(lái)作為聚簇索引則會(huì)很糟糕：它使得聚簇索引的插入變得完全隨機(jī)，這是最壞的情況，使得數(shù)據(jù)沒有任何聚集特性。
[圖片上傳失敗...(image-2a8107-1532500130839)]

因?yàn)橹麈I的值是順序的，所以InnoDB把每一條記錄都存在上一條記錄后面。當(dāng)達(dá)到頁(yè)的最大填充因子時(shí)（InnoDB默認(rèn)的最大填充因子是頁(yè)大小的15/16，留出部分空間用于以后修改），下一條記錄就會(huì)寫入新的頁(yè)中。一旦數(shù)據(jù)按照這種順序的方式加載，主鍵頁(yè)就會(huì)近似于被順序的記錄填滿，這也是所期望的結(jié)果（然而，二級(jí)索引可能是不一樣的）。

而使用uuid聚簇索引的表插入數(shù)據(jù)，因?yàn)樾滦械闹麈I值不一定比之前插入的大，所以InnoDB無(wú)法簡(jiǎn)單的總是把新行插入到索引的最后，而是需要為新的行尋找合適的位置--通常是已有數(shù)據(jù)的中間位置--并且分配空間。這會(huì)增加很多額外的工作，并且導(dǎo)致數(shù)據(jù)分布不夠優(yōu)化。

使用uuid做聚簇索引的缺點(diǎn)：

• 寫入的目標(biāo)頁(yè)可能已經(jīng)刷到磁盤上并從緩存中移除，或者是還沒有被加載到緩存中，InnoDB在插入之前不得不先找到并從磁盤讀取目標(biāo)頁(yè)到內(nèi)存中。這將導(dǎo)致大量的隨機(jī)I/O。
• 因?yàn)閷懭胧莵y序的，InnoDB不得不頻繁的做頁(yè)分裂操作，以便為新的行分配空間，頁(yè)分裂將導(dǎo)致移動(dòng)大量的數(shù)據(jù)，一次插入最少需要修改三個(gè)頁(yè)而不是一個(gè)頁(yè)。
• 由于頻繁的頁(yè)分裂，頁(yè)會(huì)變得稀疏并被不規(guī)則地填充，所以最終數(shù)據(jù)會(huì)有碎片。

使用InnoDB時(shí)應(yīng)該盡可能的按主鍵順序插入數(shù)據(jù)，并且盡可能的使用單調(diào)的聚簇鍵的值來(lái)插入新行。

順序的主鍵什么時(shí)候會(huì)最成更壞的結(jié)果？

對(duì)于高并發(fā)負(fù)載，在InnoDB中按主鍵順序插入可能會(huì)造成明顯的爭(zhēng)用。主鍵的上界會(huì)成為“熱點(diǎn)”。因?yàn)樗械牟迦攵及l(fā)生在這里，所以并發(fā)插入可能導(dǎo)致間隙鎖競(jìng)爭(zhēng)。
另一個(gè)熱點(diǎn)可能是 auto_increment 鎖機(jī)制，如果遇到這個(gè)問題，則可能需要考慮重新設(shè)計(jì)表或者應(yīng)用，或者更改 innodb_autoinc_lock_mode 配置。如果你的服務(wù)器還不支持 innodb_autoinc_lock_mode 參數(shù)，可以升級(jí)到新版本的InnoDB，可能對(duì)這種場(chǎng)景會(huì)工作的更好。

覆蓋索引

mysql也可以直接使用索引來(lái)獲取列的數(shù)據(jù)，這樣就不再需要讀取數(shù)據(jù)行。如果索引的葉子節(jié)點(diǎn)中已經(jīng)包含要查找的數(shù)據(jù)，那么還有什么必要再回表查詢呢？
如果一個(gè)索引包含或者說(shuō)覆蓋所有需要查詢的字段的值，我們就稱為“覆蓋索引”。

覆蓋索引的好處：

• 索引條目通常遠(yuǎn)小于數(shù)據(jù)行大小，所以如果只需要讀取索引，那mysql就會(huì)極大的減少數(shù)據(jù)訪問量。這對(duì)緩存的負(fù)載非常重要，因?yàn)檫@種情況下響應(yīng)時(shí)間大部分花費(fèi)在數(shù)據(jù)拷貝上。覆蓋索引對(duì)于I/O密集型的應(yīng)用也有幫助，因?yàn)樗饕葦?shù)據(jù)更小，更容易全部放到內(nèi)存里，這對(duì)于myisam尤其正確，因?yàn)閙yisam能壓縮索引以變的更小。
• 因?yàn)樗饕前凑樟兄淀樞虼鎯?chǔ)的（至少在單個(gè)頁(yè)是如此），所以對(duì)于I/O密集型的范圍查詢會(huì)比隨機(jī)從磁盤讀取每一行數(shù)據(jù)的I/O要少得多。對(duì)于某些存儲(chǔ)引擎，例如myisam和percona xtradb，甚至可以通過 optimize 命令使得索引完全順序排列，這讓簡(jiǎn)單的范圍查找能使用完全順序的索引訪問。
• 一些存儲(chǔ)引擎如myisam在內(nèi)存中只緩存索引，數(shù)據(jù)則依賴于操作系統(tǒng)來(lái)緩存，因此要訪問數(shù)據(jù)需要一次系統(tǒng)調(diào)用。這可能導(dǎo)致嚴(yán)重的性能問題，尤其是那些系統(tǒng)調(diào)用占了數(shù)據(jù)訪問中的最大開銷的場(chǎng)景。
• 由于InnoDB的聚簇索引，覆蓋索引對(duì)InnoDB表特別有用，InnoDB的二級(jí)索引在葉子節(jié)點(diǎn)中保存了行的主鍵值，所以如果耳機(jī)主鍵能夠覆蓋查詢，則可以避免對(duì)主鍵索引的二次查找。

不是所有類型的索引都可以稱為覆蓋索引。覆蓋索引必須要存儲(chǔ)索引列的值，而哈希索引，空間索引和全文索引等都不存儲(chǔ)索引列的值，所以mysql只能使用B-Tree索引做覆蓋索引。

對(duì)于下面這個(gè)查詢：

覆蓋索引查詢

這里索引無(wú)法使用覆蓋查詢，原因：

• 沒有任何索引能夠覆蓋這個(gè)查詢。因?yàn)闆_尋中表中選擇了所有的列，而沒有任何索引覆蓋了所有的列。
• mysql不能在索引中執(zhí)行l(wèi)ike操作。這是底層存儲(chǔ)引擎api限制的。mysql5.5和更早的版本中只允許在索引中做簡(jiǎn)單的比較操作（等于，不等于，大于）。mysql能在索引中做最左前綴的like比較，因?yàn)樵摬僮骺梢赞D(zhuǎn)換為簡(jiǎn)單比較操作，但如果是通配符開頭的like查詢，存儲(chǔ)引擎就無(wú)法做比較匹配。這種情況下，MySql服務(wù)器只能提取數(shù)據(jù)行的值而不是索引值來(lái)比較。