數(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)確的說法要分兩層。InnoDB不允許用戶手動(dòng)創(chuàng)建哈希索引從這個(gè)意義上說它“不支持哈希索引”。但 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)再沿鏈表順序掃描即可。查詢過程大致如圖所示查找索引值為 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í)索引的查詢過程二級(jí)索引的葉子節(jié)點(diǎn)存放的是索引列的值 主鍵值而不是完整的行數(shù)據(jù)。用二級(jí)索引查到主鍵值后還需要拿這個(gè)主鍵值回到聚簇索引中再查一次才能得到完整行——這就是回表。回表是隨機(jī) I/O數(shù)據(jù)量大時(shí)往往是查詢變慢的主要來(lái)源。3. 全文索引Fulltext全文索引主要服務(wù)于文本字段的關(guān)鍵詞檢索底層是倒排索引從“文檔 → 單詞”反過來(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)說聯(lián)合索引和前綴索引。1. 聯(lián)合索引聯(lián)合索引是把多個(gè)字段按順序組合在一起建立的索引。它的關(guān)鍵規(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 列跳過 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)?。不過有一個(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 排序跳過 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 層回表之后再過濾有了 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)致該列索引失效反過來(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)化器仍可能選擇全表掃描。這種情況需要通過EXPLAIN結(jié)合實(shí)際數(shù)據(jù)分布來(lái)判斷而不是簡(jiǎn)單歸因于“索引失效”。