1.索引的基礎(chǔ)知識(shí)

1.1 索引是什么

索引是一種用于快速查詢和檢索的數(shù)據(jù)結(jié)構(gòu)，例如 B 樹(shù)、B+ 樹(shù)和 Hash 表。索引類似目錄的作用，例如查字典的時(shí)候，根據(jù)目錄可以快速找到字的位置。

索引的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：① 索引可以大大加快數(shù)據(jù)的查詢速率；② 索引的唯一性可以保證表中每一行數(shù)據(jù)都有唯一性。
缺點(diǎn)：① 創(chuàng)建和維護(hù)索引需要消耗較多時(shí)間。當(dāng)進(jìn)行增刪改的時(shí)候，索引也需要?jiǎng)討B(tài)修改，導(dǎo)致 SQL 執(zhí)行效率下降；② 索引需要使用物理文件存儲(chǔ)，需要耗費(fèi)一定空間。

1.2 索引的底層數(shù)據(jù)結(jié)構(gòu)

1.2.1 Hash 表

Hash 表通過(guò)哈希算法，可以根據(jù) key（index）快速找到 value。

hash = hashfunc(key)
index = hash % array_size

哈希算法有 Hash 沖突問(wèn)題，即多個(gè)不同的 key 計(jì)算出來(lái)的 index 是相同的。常用的解決方法有開(kāi)放尋址法、再散列法和鏈地址法。JDK 1.8 HashMap 引用了紅黑樹(shù)，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為 8），就會(huì)將鏈表轉(zhuǎn)換成紅黑樹(shù)。

image.png

MySQL 為什么沒(méi)有使用 Hash 表作為索引的數(shù)據(jù)結(jié)構(gòu)？

最大的原因是Hash 表不支持順序和范圍查詢。

// 例如，我們對(duì)數(shù)據(jù)進(jìn)行范圍查詢
SELECT * FROM tb1 WHERE id < 500
// Hash 需要根據(jù)哈希算法，把全量的數(shù)據(jù)進(jìn)行一次 Hash 計(jì)算，如果滿足 id<500，則返回。

1.2.3 B 樹(shù)和 B+ 樹(shù)

B 樹(shù)稱為多路平衡查找樹(shù)，B+ 樹(shù)是 B 樹(shù)的一種變體。MyISAM 引擎和 InnoDB 引擎都是采用 B+ 樹(shù)作為索引的數(shù)據(jù)結(jié)構(gòu)。從主鍵的角度分析，索引分為主鍵索引和二級(jí)索引。從索引和數(shù)據(jù)是否放在一起的角度分析，索引分為聚集索引和非聚集索引，其中 MYISAM 是非聚集索引，InnoDB 是聚集索引。

B 樹(shù)和 B+ 樹(shù)的差異是啥？
① B 樹(shù)的所有節(jié)點(diǎn)同時(shí)存放 key 和 value，而 B+ 樹(shù)只有葉子節(jié)點(diǎn)存放 key 和 value，其余節(jié)點(diǎn)只存放 key；
② B 樹(shù)的葉子節(jié)點(diǎn)都是獨(dú)立的，而 B+ 樹(shù)的葉子節(jié)點(diǎn)有一條引用鏈指向它相鄰的葉子節(jié)點(diǎn)；
③ B 樹(shù)的查詢過(guò)程相當(dāng)于對(duì)范圍內(nèi)的每個(gè)節(jié)點(diǎn)做二分查找，可能沒(méi)有到達(dá)葉子節(jié)點(diǎn)就結(jié)束了，而 B+ 樹(shù)的查詢都是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，查詢效率十分穩(wěn)定。

image.png

2.索引的類別及其原理

2.1 索引分類的角度一：索引和數(shù)據(jù)是否分離

2.1.1 聚集索引

聚集索引是索引結(jié)構(gòu)和數(shù)據(jù)一起存放的索引。主鍵索引屬于聚集索引。

InnoDB 引擎的表的 .ibd 文件包含了索引和數(shù)據(jù)。對(duì)于 InnoDB 引擎表來(lái)說(shuō)，即表的索引（ B+ 樹(shù)）的每個(gè)非葉子節(jié)點(diǎn)存儲(chǔ)索引，葉子節(jié)點(diǎn)存儲(chǔ)索引和索引對(duì)應(yīng)的數(shù)據(jù)。

2.1.2 非聚集索引

非聚集索引是索引結(jié)構(gòu)和數(shù)據(jù)分開(kāi)存放的索引。

MYISAM 引擎表的 .MYI 文件只有表的索引，即表的索引（B+ 樹(shù)）的每個(gè)葉子和非葉子節(jié)點(diǎn)都存儲(chǔ)了索引， 葉子節(jié)點(diǎn)存儲(chǔ)索引和索引對(duì)應(yīng)數(shù)據(jù)的指針，指向 .MYD 文件的數(shù)據(jù)。
說(shuō)明：二級(jí)索引屬于非聚集索引，因此非聚集索引的葉子節(jié)點(diǎn)可能存放了主鍵。

MySQL 的表文件，如下圖所示。

image.png

2.1 索引分類的角度二：是否為主鍵

2.2.1 主鍵索引

表的主鍵就是使用主鍵索引，主鍵索引屬于聚集索引。

如果使用了 InnoDB 存儲(chǔ)引擎，則當(dāng)沒(méi)有顯示地指定表的主鍵時(shí)，InnoDB 會(huì)自動(dòng)先檢查表中是否有唯一索引的字段，如果有則選擇該字段為默認(rèn)的主鍵，否則 InnoDB 將會(huì)自動(dòng)創(chuàng)建一個(gè) 6Byte 的自增主鍵。

樣例：創(chuàng)建表 pl_ranking，其中 id 設(shè)置為主鍵，執(zhí)行下面的 select 語(yǔ)句。如下圖所示，索引和存儲(chǔ)數(shù)據(jù)都存儲(chǔ)到每個(gè)葉子節(jié)點(diǎn)上的，通過(guò)索引就直接可以查找到數(shù)據(jù)。

 select id, plname, ranking from pl_ranking where id=16;

image.png

2.2.2 二級(jí)索引

二級(jí)索引是非聚集索引，其葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是主鍵，即利用二級(jí)索引，可以定位主鍵的位置。

image.png

二級(jí)索引分類
① 唯一索引(Unique Key)：唯一索引也是一種約束。唯一索引的屬性列不能出現(xiàn)重復(fù)的數(shù)據(jù)，但是允許數(shù)據(jù)為 NULL，一張表允許創(chuàng)建多個(gè)唯一索引。 建立唯一索引的目的大部分時(shí)候都是為了該屬性列的數(shù)據(jù)的唯一性，而不是為了查詢效率。
② 普通索引(Index) ：普通索引的唯一作用就是為了快速查詢數(shù)據(jù)，一張表允許創(chuàng)建多個(gè)普通索引，并允許數(shù)據(jù)重復(fù)和 NULL。
③ 前綴索引(Prefix) ：前綴索引只適用于字符串類型的數(shù)據(jù)。前綴索引是對(duì)文本的前幾個(gè)字符創(chuàng)建索引，相比普通索引建立的數(shù)據(jù)更小， 因?yàn)橹蝗∏皫讉€(gè)字符。
④ 全文索引(Full Text) ：全文索引主要是為了檢索大文本數(shù)據(jù)中的關(guān)鍵字的信息，是目前搜索引擎數(shù)據(jù)庫(kù)使用的一種技術(shù)。

樣例：創(chuàng)建表 pl_ranking，其中 plname 設(shè)置為二級(jí)索引，執(zhí)行下面的 select 語(yǔ)句。如下圖所示，索引和主鍵存儲(chǔ)到每個(gè)葉子節(jié)點(diǎn)上的，然后需要通過(guò)主鍵才能查找到數(shù)據(jù)。

select id, plname, ranking from pl_ranking where plname='Java';

image.png