數(shù)據(jù)庫(kù)索引是面試中的高頻考點(diǎn)。下面以 MySQL InnoDB 存儲(chǔ)引擎為主線把索引的數(shù)據(jù)結(jié)構(gòu)、功能分類以及幾個(gè)容易踩坑的細(xì)節(jié)串起來(lái)。一、索引的分類索引的數(shù)據(jù)結(jié)構(gòu)常見的有 Btree 和 Hash 等從功能上還可以劃分主鍵索引、唯一索引、聯(lián)合索引、前綴索引等。一按數(shù)據(jù)結(jié)構(gòu)劃分1. Hash 索引如果只是單純判斷值相等哈希算法確實(shí)非?？焖愠?key 的哈希值直接定位到桶。但數(shù)據(jù)庫(kù)查詢很少只有“等值”這一種形態(tài)范圍查詢、、BETWEEN、排序、最左前綴匹配都無(wú)法用哈希高效完成所以 InnoDB 的主角是 Btree。注意準(zhǔn)確的說(shuō)法要分兩層。InnoDB不允許用戶手動(dòng)創(chuàng)建哈希索引從這個(gè)意義上說(shuō)它“不支持哈希索引”。但 InnoDB 內(nèi)部有一套自適應(yīng)哈希索引Adaptive Hash Index, AHI當(dāng)它發(fā)現(xiàn)某些索引值被頻繁等值查詢、且尋路路徑較長(zhǎng)時(shí)會(huì)在 Buffer Pool 中自動(dòng)為這些熱點(diǎn)頁(yè)建立哈希索引加速等值查找。AHI 完全由 InnoDB 自調(diào)優(yōu)建立DBA 無(wú)法手動(dòng)指定“給某個(gè)字段建哈希索引”。此外AHI 在大量 LIKE、JOIN 場(chǎng)景下可能成為維護(hù)負(fù)擔(dān)必要時(shí)可以手動(dòng)關(guān)閉。2. Btree 索引Btree 是 InnoDB 的默認(rèn)索引結(jié)構(gòu)。主鍵索引聚簇索引和二級(jí)索引非聚簇索引都是 Btree。核心特征非葉子節(jié)點(diǎn)只存 key 和指針不存真正的數(shù)據(jù)行所有數(shù)據(jù)都集中在葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)之間用雙向鏈表連接因此范圍查詢只需要定位到起點(diǎn)再沿鏈表順序掃描即可。查詢過(guò)程大致如圖所示查找索引值為 24 的記錄從根節(jié)點(diǎn)進(jìn)入24 落在 20 和 50 之間沿指針走到“30 節(jié)點(diǎn)”24 小于 30再走到葉子層(20, 24, 26)在葉子節(jié)點(diǎn)中定位到 24。為什么用 Btree 而不是二叉樹InnoDB 以頁(yè)P(yáng)age為磁盤 I/O 的基本單位默認(rèn)一頁(yè) 16KB。二叉樹每個(gè)節(jié)點(diǎn)最多兩個(gè)子節(jié)點(diǎn)數(shù)據(jù)量大時(shí)樹高會(huì)迅速增加每下降一層就意味著一次額外的磁盤 I/O。Btree 的非葉子節(jié)點(diǎn)只放 key 和指針一頁(yè)能容納的 key 數(shù)量扇出遠(yuǎn)大于二叉樹樹高可以壓得很低。以 bigint 主鍵為例一頁(yè)大約能放 1170 個(gè) key如果一行數(shù)據(jù) 1KB一頁(yè)葉子能放約 16 行三層 Btree 大約可以容納 2000 萬(wàn)行級(jí)別日常查詢通常只需 23 次 I/O。為什么不用 B 樹B 樹的非葉子節(jié)點(diǎn)也要存數(shù)據(jù)行。這意味著同樣一頁(yè) 16KBB 樹能放的 key 數(shù)量比 Btree 少扇出更低、樹更高同時(shí) B 樹的查找效率不穩(wěn)定有的記錄在非葉子層就命中有的必須走到葉子層。Btree 把數(shù)據(jù)全部下沉到葉子層每次查詢都要走到葉子效率穩(wěn)定非葉子節(jié)點(diǎn)只做索引扇出更高葉子節(jié)點(diǎn)的雙向鏈表則讓范圍查詢天然高效。二級(jí)索引的查詢過(guò)程二級(jí)索引的葉子節(jié)點(diǎn)存放的是索引列的值 主鍵值而不是完整的行數(shù)據(jù)。用二級(jí)索引查到主鍵值后還需要拿這個(gè)主鍵值回到聚簇索引中再查一次才能得到完整行——這就是回表?；乇硎请S機(jī) I/O數(shù)據(jù)量大時(shí)往往是查詢變慢的主要來(lái)源。3. 全文索引Fulltext全文索引主要服務(wù)于文本字段的關(guān)鍵詞檢索底層是倒排索引從“文檔 → 單詞”反過(guò)來(lái)建立“單詞 → 文檔/位置”的映射從而避免LIKE %關(guān)鍵詞%這種無(wú)法使用 Btree 的全表掃描。使用方式MATCH(字段名) AGAINST(關(guān)鍵詞);版本與中文注意點(diǎn)MySQL 5.6 之前只有 MyISAM 支持全文索引5.6 中 InnoDB 加入全文索引但不支持中文分詞從 5.7.6 開始內(nèi)置ngram 全文解析器才具備可用的中文分詞能力。建全文索引時(shí)需要指定解析器例如FULLTEXT(title, body) WITH PARSER ngram如果沒有 ngram 而直接對(duì)中文建全文索引分詞效果會(huì)很不理想。二按功能劃分主鍵索引、唯一索引、普通索引不再贅述重點(diǎn)說(shuō)聯(lián)合索引和前綴索引。1. 聯(lián)合索引聯(lián)合索引是把多個(gè)字段按順序組合在一起建立的索引。它的關(guān)鍵規(guī)則是最左匹配原則查詢條件必須從索引的最左列開始并且不能跳過(guò)中間的列否則無(wú)法完整利用索引。假設(shè)有聯(lián)合索引idx_a_b_c(a, b, c)各種條件的索引使用情況如下查詢條件索引使用情況原因a 1使用 a 列從最左列開始a 1 AND b 2使用 a、b 列連續(xù)匹配a 1 AND b 2 AND c 3使用 a、b、c 列完整匹配b 2 AND a 1使用 a、b 列優(yōu)化器會(huì)自動(dòng)調(diào)整等值條件的順序a 1 AND c 3僅使用 a 列跳過(guò) b 列c 列無(wú)法使用索引b 2 AND c 3完全無(wú)法使用索引缺少最左列 aa 1 AND b 2僅使用 a 列范圍查詢截?cái)郺 1 AND b 2 AND c 3使用 a、b 列范圍查詢后的 c 列無(wú)法使用容易被忽略的細(xì)節(jié)范圍查詢的截?cái)嘈?yīng)。聯(lián)合索引中一旦某一列使用了范圍查詢、該列右側(cè)的所有列都無(wú)法繼續(xù)用于索引定位。例如WHERE a 1 AND b 2 AND c 3中c不會(huì)走索引。設(shè)計(jì)聯(lián)合索引時(shí)通常把等值條件放在前面、范圍條件放在最后就是為了避免這種截?cái)?。不過(guò)有一個(gè)常見的“例外”和在某些執(zhí)行計(jì)劃下可能不會(huì)像、那樣嚴(yán)格截?cái)嘤覀?cè)列但這依賴于優(yōu)化器的判斷不應(yīng)作為設(shè)計(jì)索引的依據(jù)。穩(wěn)妥的做法仍然是范圍列盡量放在聯(lián)合索引的末尾。另一個(gè)容易混淆的點(diǎn)最左前綴原則不是一條“人為規(guī)定”而是Btree 按聯(lián)合索引列順序排序的自然結(jié)果。聯(lián)合索引先按 a 排序a 相同再按 b 排序b 相同再按 c 排序跳過(guò) a 直接查 bBtree 無(wú)法利用有序性定位只能放棄索引。2. 前綴索引前綴索引只取字段的前幾個(gè)字符建立索引適用于CHAR、VARCHAR、BINARY、VARBINARY類型可以顯著減小索引體積。注意前綴索引的代價(jià)是無(wú)法用于ORDER BY/GROUP BY的完整排序也無(wú)法作為覆蓋索引使用因?yàn)樗饕兄槐Ａ袅饲熬Y不包含完整列值。選擇前綴長(zhǎng)度時(shí)需要保證足夠的區(qū)分度例如用COUNT(DISTINCT LEFT(col, n)) / COUNT(*)來(lái)評(píng)估。二、其他需要注意的點(diǎn)覆蓋索引避免回表的優(yōu)化手段如果一條查詢需要的所有列都已經(jīng)包含在所使用的索引中就不需要回表這就是覆蓋索引。最典型的做法是把查詢涉及的列建成聯(lián)合索引讓二級(jí)索引的葉子節(jié)點(diǎn)直接“覆蓋”查詢需求。在EXPLAIN中覆蓋索引的標(biāo)志是Extra: Using index。注意Using index的含義是“沒有回表索引自己就夠了”而不是“用了索引”走了索引但回了表Extra可能什么都不顯示。索引下推Index Condition Pushdown, ICPMySQL 5.6 引入的優(yōu)化。在沒有 ICP 時(shí)聯(lián)合索引中無(wú)法用于定位的列條件例如被范圍查詢截?cái)嗪蟮暮罄m(xù)列條件只能在 Server 層回表之后再過(guò)濾有了 ICP引擎層會(huì)先用索引中已有的列做一次pre-filter減少不必要的回表次數(shù)。EXPLAIN中對(duì)應(yīng)Extra: Using index condition。常見索引失效場(chǎng)景索引的本質(zhì)是有序的數(shù)據(jù)結(jié)構(gòu)一旦查詢方式破壞了“有序性”或者優(yōu)化器判斷全表掃描代價(jià)更低索引就可能不被使用。常見場(chǎng)景包括對(duì)索引列做函數(shù)或運(yùn)算WHERE YEAR(create_time) 2024、WHERE age 3 24索引列被處理后無(wú)法直接定位。隱式類型轉(zhuǎn)換字符串類型的列用數(shù)字查詢、或數(shù)字列用字符串查詢可能觸發(fā)隱式CAST。尤其要注意方向字符串列與數(shù)字比較時(shí)MySQL 可能將字符串列轉(zhuǎn)為數(shù)字導(dǎo)致該列索引失效反過(guò)來(lái)數(shù)字列與字符串比較時(shí)轉(zhuǎn)換方向不同結(jié)論可能不同不能一概而論應(yīng)以EXPLAIN為準(zhǔn)。LIKE以%開頭LIKE %abc無(wú)法利用 Btree 的前綴有序性LIKE abc%則可以使用索引。違反最左前綴聯(lián)合索引缺少最左列或中間跳列。OR連接了未建索引的列只要OR的一側(cè)沒有可用索引優(yōu)化器可能直接放棄索引走全表掃描。優(yōu)化器基于代價(jià)放棄索引即使寫法“正確”當(dāng)預(yù)估走索引需要大量回表、成本高于全表掃描時(shí)優(yōu)化器仍可能選擇全表掃描。這種情況需要通過(guò)EXPLAIN結(jié)合實(shí)際數(shù)據(jù)分布來(lái)判斷而不是簡(jiǎn)單歸因于“索引失效”。