索引分類(lèi)

索引和數(shù)據(jù)就是位于存儲(chǔ)引擎中：

• 按「數(shù)據(jù)結(jié)構(gòu)」分類(lèi)：B+tree索引、Hash索引、Full-text索引。
• 按「物理存儲(chǔ)」分類(lèi)：聚簇索引（主鍵索引）、二級(jí)索引（輔助索引）。
• 按「字段特性」分類(lèi)：主鍵索引、唯一索引、普通索引、前綴索引。
• 按「字段個(gè)數(shù)」分類(lèi)：單列索引、聯(lián)合索引。

為什么 MySQL InnoDB 選擇 B+tree 作為索引的數(shù)據(jù)結(jié)構(gòu)？

1、B+Tree vs B Tree

• B+Tree 只在葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，而 B 樹(shù) 的非葉子節(jié)點(diǎn)也要存儲(chǔ)數(shù)據(jù)，所以 B+Tree 的單個(gè)節(jié)點(diǎn)的數(shù)據(jù)量更小，在相同的磁盤(pán) I/O 次數(shù)下，就能查詢更多的節(jié)點(diǎn)。

• 另外，B+Tree 葉子節(jié)點(diǎn)采用的是雙鏈表連接，適合 MySQL 中常見(jiàn)的基于范圍的順序查找，而 B 樹(shù)無(wú)法做到這一點(diǎn)。

2、B+Tree vs 二叉樹(shù)

• 對(duì)于有 N 個(gè)葉子節(jié)點(diǎn)的 B+Tree，其搜索復(fù)雜度為O(logdN)，其中 d 表示節(jié)點(diǎn)允許的最大子節(jié)點(diǎn)個(gè)數(shù)為 d 個(gè)。

• 在實(shí)際的應(yīng)用當(dāng)中， d 值是大于100的，這樣就保證了，即使數(shù)據(jù)達(dá)到千萬(wàn)級(jí)別時(shí)，B+Tree 的高度依然維持在 3~4 層左右，也就是說(shuō)一次數(shù)據(jù)查詢操作只需要做 3~4 次的磁盤(pán) I/O 操作就能查詢到目標(biāo)數(shù)據(jù)。

• 而二叉樹(shù)的每個(gè)父節(jié)點(diǎn)的兒子節(jié)點(diǎn)個(gè)數(shù)只能是 2 個(gè)，意味著其搜索復(fù)雜度為 O(logN)，這已經(jīng)比 B+Tree 高出不少，因此二叉樹(shù)檢索到目標(biāo)數(shù)據(jù)所經(jīng)歷的磁盤(pán) I/O 次數(shù)要更多。

3、B+Tree vs Hash

• Hash 在做等值查詢的時(shí)候效率賊快，搜索復(fù)雜度為 O(1)。

• Hash需要一次性將數(shù)據(jù)加載到內(nèi)存中，如果數(shù)據(jù)比較大，則加載時(shí)間長(zhǎng)，而B(niǎo)+tree是分節(jié)點(diǎn)加載數(shù)據(jù)

• 但是 Hash 表不適合做范圍查詢，它更適合做等值的查詢，這也是 B+Tree 索引要比 Hash 表索引有著更廣泛的適用場(chǎng)景的原因。

聚簇索引（主鍵索引）、二級(jí)索引（輔助索引）

• 主鍵索引的 B+Tree 的葉子節(jié)點(diǎn)存放的是實(shí)際數(shù)據(jù)，所有完整的用戶記錄都存放在主鍵索引的 B+Tree 的葉子節(jié)點(diǎn)里；
  二級(jí)索引的 B+Tree 的葉子節(jié)點(diǎn)存放的是主鍵值，而不是實(shí)際數(shù)據(jù)。
• 覆蓋索引
  • 在查詢時(shí)使用了二級(jí)索引，如果查詢的數(shù)據(jù)能在二級(jí)索引里查詢的到(也就是查詢的數(shù)據(jù)是主鍵值)，不需要讀取索引中的數(shù)據(jù)，只需要查一個(gè) B+ 樹(shù)就能找到數(shù)據(jù)，那么就不需要回表，這個(gè)過(guò)程就是覆蓋索引。
• 回表
  • 如果某個(gè)查詢語(yǔ)句使用了二級(jí)索引，但是查詢的數(shù)據(jù)不是主鍵值，這時(shí)找到對(duì)應(yīng)的葉子節(jié)點(diǎn)，獲取到主鍵值后，需要去聚簇索引中獲得數(shù)據(jù)行，就能查詢到數(shù)據(jù)了，這個(gè)過(guò)程就是回表。

InnoDB 在創(chuàng)建聚簇索引時(shí)，會(huì)根據(jù)不同的場(chǎng)景選擇不同的列作為索引：

• 如果有主鍵，默認(rèn)會(huì)使用主鍵作為聚簇索引的索引鍵；
• 如果沒(méi)有主鍵，就選擇第一個(gè)不包含 NULL 值的唯一列作為聚簇索引的索引鍵；
• 在上面兩個(gè)都沒(méi)有的情況下，InnoDB 將自動(dòng)生成一個(gè)隱式自增 id 列作為聚簇索引的索引鍵；

一張表只能有一個(gè)聚簇索引，那為了實(shí)現(xiàn)非主鍵字段的快速搜索，就引出了二級(jí)索引

字段特性

主鍵索引：

• 建立在主鍵字段上的索引，通常在創(chuàng)建表的時(shí)候一起創(chuàng)建，一張表最多只有一個(gè)主鍵索引，索引列的值不允許有空值。

唯一索引：

• 建立在 UNIQUE 字段上的索引，一張表可以有多個(gè)唯一索引，索引列的值必須唯一，但是允許有空值。

普通索引：

• 就是建立在普通字段上的索引，既不要求字段為主鍵，也不要求字段為 UNIQUE。

前綴索引

• 是指對(duì)字符類(lèi)型字段的前幾個(gè)字符建立的索引，而不是在整個(gè)字段上建立的索引，前綴索引可以建立在字段類(lèi)型為 char、 varchar、binary、varbinary 的列上。使用前綴索引的目的是為了減少索引占用的存儲(chǔ)空間，提升查詢效率。

單列索引和聯(lián)合索引

• 建立在單列上的索引稱為單列索引，比如主鍵索引；
• 建立在多列上的索引稱為聯(lián)合索引；

聯(lián)合索引范圍

• 聯(lián)合索引查詢，不代表聯(lián)合索引中的所有字段都用到了聯(lián)合索引進(jìn)行索引查詢，可能存在部分字段用到聯(lián)合索引的 B+Tree，部分字段沒(méi)有用到聯(lián)合索引的 B+Tree 的情況。
• 聯(lián)合索引的最左匹配原則會(huì)一直向右匹配直到遇到「范圍查詢」就會(huì)停止匹配。也就是范圍查詢的字段可以用到聯(lián)合索引，但是在范圍查詢字段的后面的字段無(wú)法用到聯(lián)合索引。
• 注意，對(duì)于 >=、<=、BETWEEN、like 前綴匹配的范圍查詢，并不會(huì)停止匹配

select * from t_table where a > 1 and b = 2

單列索引與聯(lián)合索引區(qū)別

• 組成方式：單列索引只包含一列，而聯(lián)合索引則由多列組成。
• 使用范圍：單列索引適用于單列查詢，聯(lián)合索引適用于多列查詢
• 索引大小：聯(lián)合索引的大小通常比單列索引大
• 更新操作：聯(lián)合索引，如果更新操作涉及到了索引的任何一列，都會(huì)導(dǎo)致索引重建，單列索引，只有更新涉及到了該列才會(huì)導(dǎo)致索引重建
• 單列索引適用于單列查詢，適用于頻繁更新的情況；而聯(lián)合索引適用于多列查詢，適用于讀操作多、寫(xiě)操作少的情況

聯(lián)合索引相比單列索引有什么優(yōu)點(diǎn)

• 聯(lián)合索引在進(jìn)行查詢過(guò)程中，可能索引列就是我們要查詢的數(shù)據(jù)，使用覆蓋索引，避免了回表操作，減少I(mǎi)O次數(shù)，提高查詢性能

最左匹配原則

• 在使用多列索引時(shí)，如果查詢中包含索引的第一個(gè)列，則可以利用該索引進(jìn)行搜索；如果查詢中不包含索引的第一個(gè)列，則無(wú)法使用該索引。

索引下推原理

• 一般在聯(lián)合索引來(lái)優(yōu)化查詢，但是，在某些情況下，聯(lián)合索引并不完全適用于所有的查詢條件，于是從 MySQL 5.6 之后使用索引下推
• 可以在聯(lián)合索引遍歷過(guò)程中，對(duì)聯(lián)合索引中包含的字段先做判斷，直接過(guò)濾掉不滿足條件的記錄，減少回表次數(shù)。（在引擎層判斷數(shù)據(jù)是否合法，如果合法直接返回，如果不合法繼續(xù)判斷，減少回表操作）

索引下推原理

• 截?cái)嗟淖侄尾粫?huì)在 Server 層進(jìn)行條件判斷，而是會(huì)被下推到「存儲(chǔ)引擎層」進(jìn)行條件判斷（因?yàn)?c 字段的值是在 (a, b, c) 聯(lián)合索引里的），然后過(guò)濾出符合條件的數(shù)據(jù)后再返回給 Server 層。由于在引擎層就過(guò)濾掉大量的數(shù)據(jù)，無(wú)需再回表讀取數(shù)據(jù)來(lái)進(jìn)行判斷，減少回表次數(shù)，從而提升了性能。

Innodb的B+Tree、BTree、二級(jí)索引、MyISAM的B+Tree

• Innodb的B+Tree：非葉子節(jié)點(diǎn)存放索引值，葉子結(jié)點(diǎn)存放數(shù)值(索引即文件)
• BTree：非葉子結(jié)點(diǎn)與葉子結(jié)點(diǎn)都存放數(shù)據(jù)
• 二級(jí)索引：非葉子結(jié)點(diǎn)存放索引值，葉子結(jié)點(diǎn)存放的是主鍵值
• MyISAM的B+Tree：非葉子結(jié)點(diǎn)存放索引值，葉子結(jié)點(diǎn)存放指向數(shù)據(jù)的指針。（索引與文件分開(kāi)）

索引失效

• 當(dāng)我們使用左或者左右模糊匹配的時(shí)候，也就是 like %xx 或者 like %xx%這兩種方式都會(huì)造成索引失效；
• 當(dāng)我們?cè)诓樵儣l件中對(duì)索引列使用函數(shù)，就會(huì)導(dǎo)致索引失效。
• 當(dāng)我們?cè)诓樵儣l件中對(duì)索引列進(jìn)行表達(dá)式計(jì)算，也是無(wú)法走索引的。
• MySQL 在遇到字符串和數(shù)字比較的時(shí)候，會(huì)自動(dòng)把字符串轉(zhuǎn)為數(shù)字，然后再進(jìn)行比較。如果字符串是索引列，而條件語(yǔ)句中的輸入?yún)?shù)是數(shù)字的話，那么索引列會(huì)發(fā)生隱式類(lèi)型轉(zhuǎn)換，由于隱式類(lèi)型轉(zhuǎn)換是通過(guò) CAST 函數(shù)實(shí)現(xiàn)的，等同于對(duì)索引列使用了函數(shù)，所以就會(huì)導(dǎo)致索引失效。
• 聯(lián)合索引要能正確使用需要遵循最左匹配原則，也就是按照最左優(yōu)先的方式進(jìn)行索引的匹配，否則就會(huì)導(dǎo)致索引失效。
• 在 WHERE 子句中，如果在 OR 前的條件列是索引列，而在 OR 后的條件列不是索引列，那么索引會(huì)失效。

MySQL 使用 like “%x“，索引不一定會(huì)失效

• 當(dāng)表中的字段全部都使用到了索引，例如表中只有id和name倆列，id為主鍵索引，name為二級(jí)索引
• 這張表的字段沒(méi)有「非索引」字段，所以select *相當(dāng)于 select id,name，然后這個(gè)查詢的數(shù)據(jù)都在二級(jí)索引的 B+ 樹(shù)，因?yàn)槎?jí)索引的 B+ 樹(shù)的葉子節(jié)點(diǎn)包含「索引值+主鍵值」，所以查二級(jí)索引的 B+ 樹(shù)就能查到全部結(jié)果了，這個(gè)就是覆蓋索引。
• 但是執(zhí)行計(jì)劃里的 type 是 index，這代表著是通過(guò)全掃描二級(jí)索引的 B+ 樹(shù)的方式查詢到數(shù)據(jù)的，也就是遍歷了整顆索引樹(shù)。
  

文章總結(jié)https://www.xiaolincoding.com/