10分鐘梳理MySQL索引核心知識(shí)點(diǎn)

MySQL核心-索引

索引的概念、數(shù)據(jù)結(jié)構(gòu)、原理等

索引是啥

數(shù)據(jù)庫索引可以類比為一本書的目錄，主要的目的就是快速的定位到目標(biāo)。這需要支持快速搜索的數(shù)據(jù)結(jié)構(gòu)的支持，比如哈希表、有序數(shù)組和搜索樹。

索引的幾種形態(tài)

根據(jù)底層數(shù)據(jù)結(jié)構(gòu)的不同，大致有三種類型的索引結(jié)構(gòu)

1）基于哈希表的索引

適用于等值查詢的場景
缺點(diǎn)：對(duì)區(qū)間查找不友好

2）有序數(shù)組：

優(yōu)點(diǎn)：利用二分查找，等值查詢和范圍查詢性能都很好
缺點(diǎn)：對(duì)動(dòng)態(tài)插入、刪除、更新不友好

適用于靜態(tài)數(shù)據(jù)或變動(dòng)不頻繁的場景

3）搜索樹

目前大部分?jǐn)?shù)據(jù)庫引擎都用的該方案，這里引出幾個(gè)問題

為什么不用二叉搜索樹？

答：因?yàn)槎鏄涞母叨群芨撸饕龝?huì)存放在磁盤上，這將導(dǎo)致數(shù)據(jù)查詢過程需要多次訪問磁盤，這會(huì)大幅降低搜索效率，所以使用多(1000+)叉樹

B 樹和 B+ 樹的區(qū)別？

答：B+ 樹和 B 樹相比，主要的不同點(diǎn)在以下3項(xiàng)：

• 內(nèi)部節(jié)點(diǎn)中，關(guān)鍵字的個(gè)數(shù)與其子樹的個(gè)數(shù)相同，不像B樹，子樹的個(gè)數(shù)總比關(guān)鍵字個(gè)數(shù)多1個(gè)
• 所有指向文件的關(guān)鍵字及其指針都在葉子節(jié)點(diǎn)中，不像B樹，有的指向文件的關(guān)鍵字是在內(nèi)部節(jié)點(diǎn)中。換句話說，B+樹中，內(nèi)部節(jié)點(diǎn)僅僅起到索引的作用，真正的數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)
• 在搜索過程中，如果查詢和內(nèi)部節(jié)點(diǎn)的關(guān)鍵字一致，那么搜索過程不停止，而是繼續(xù)向下搜索這個(gè)分支，直到葉子節(jié)點(diǎn)

根據(jù)B+樹的結(jié)構(gòu)，我們可以發(fā)現(xiàn)B+樹相比于B樹，在文件系統(tǒng)，數(shù)據(jù)庫系統(tǒng)當(dāng)中，更有優(yōu)勢(shì)，原因如下：

• B+樹的磁盤讀寫代價(jià)更低

• B+樹的內(nèi)部結(jié)點(diǎn)并沒有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B樹更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中,那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來說I/O讀寫次數(shù)也就降低了。

• B+樹的查詢效率更加穩(wěn)定

• 由于內(nèi)部結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢的路徑長度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)。

• B+樹更有利于對(duì)數(shù)據(jù)庫的掃描

• B樹在提高了磁盤IO性能的同時(shí)并沒有解決元素遍歷的效率低下的問題，而B+樹只需要遍歷葉子節(jié)點(diǎn)就可以解決對(duì)全部關(guān)鍵字信息的掃描，所以對(duì)于數(shù)據(jù)庫中頻繁使用的range query，B+樹有著更高的性能。

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

InnoDB與MyISAM

MyISAM使用的是B+Tree，葉節(jié)點(diǎn)存放的數(shù)據(jù)是記錄的地址，即一份映射關(guān)系。主鍵索引樹和非主鍵索引樹結(jié)構(gòu)上沒區(qū)別

InnoDB使用的也是B+Tree，和MyISAM相比最大的區(qū)別是他的數(shù)據(jù)文件本身就是索引文件，而MyISAM索引文件和數(shù)據(jù)文件是分離的。非主鍵樹葉子節(jié)點(diǎn)存放的是主鍵的值，而主鍵樹葉子節(jié)點(diǎn)存放的是整條記錄。因此InnoDB要求表必須要有主鍵，如果未配置那么會(huì)默認(rèn)生成一個(gè)主鍵。同樣的如果重建主鍵索引（先drop再add），相當(dāng)于整個(gè)表都要重建（包括其他非聚合索引樹）

延伸：兩種引擎最大的區(qū)別就是InnoDB支持事務(wù)處理、外鍵和行級(jí)鎖；MyISAM強(qiáng)調(diào)的是性能，更多適用讀的場景。

頁分裂與優(yōu)化

• B+樹索引的維護(hù)
• 如果是業(yè)務(wù)主鍵無法保證有序遞增，這可能會(huì)導(dǎo)致移位（50%分裂） 降低空間利用率
• 在其他非主鍵索引構(gòu)成的樹中，葉子存放的是主鍵，所以使用自增主鍵占用的空間更小
• 主鍵長度越小，普通索引的葉子節(jié)點(diǎn)就越小，普通索引占用的空間就越小
• 頁分裂
• InnoDB為每個(gè)索引頁維護(hù)了一個(gè)上次插入的位置，以及上次的單調(diào)情況
• 頁滿了之后，申請(qǐng)新的空間并不移動(dòng)老數(shù)據(jù)
• 針對(duì)遞增遞減場景很合適，如果隨機(jī)插入反而不如50%策略
• 分裂后，兩個(gè)page數(shù)據(jù)各占50%
• 會(huì)導(dǎo)致空間利用率下降，優(yōu)點(diǎn)是適合于隨機(jī)插入的場景
• 目前InnoDB的優(yōu)化策略（0%分裂策略）
• 根據(jù)這些信息判斷插入到頁面的記錄是否滿足單調(diào)條件，如果滿足那么執(zhí)行0%分裂，否則執(zhí)行50%分裂
• 這樣會(huì)有bug，3,4,5,6在一個(gè)塊且遞增，接下來插入9->8->7都會(huì)執(zhí)行0%策略導(dǎo)致頁利用率極低
• 優(yōu)化策略，分裂時(shí)采用『1策略』，至少帶著最后一位一起分裂
• 插入尾部無影響（追加操作；自增主鍵就是這樣做的）
• 插入中間需要移位
• 新插入數(shù)據(jù)，要在主鍵樹節(jié)點(diǎn)（存放在Page中：類似數(shù)組）中插入
• 如果Page滿了，還需要進(jìn)行頁分裂，要申請(qǐng)一個(gè)新的數(shù)據(jù)頁并移動(dòng)數(shù)據(jù)，性能很差
• 因刪除操作而導(dǎo)致的頁合并
• 為什么經(jīng)常要求table有一個(gè)自增主鍵？

聯(lián)合索引的原理

key ‘Index_Uni’ (‘name’,’age’) 假設(shè)根據(jù)name和age兩個(gè)字段建立了聯(lián)合索引，那么這顆樹葉子節(jié)點(diǎn)應(yīng)該是這樣的
(‘luyu’,10) (‘luyu’,11) (‘luyu’,12) (‘mike’,10) (‘mike’,12) … 當(dāng)我們執(zhí)行如下查詢

select * from table where name = 'luyu' and age = 12;

此時(shí)第一步會(huì)根據(jù)二分查找定位到’luyu’

PS：這里有個(gè)猜測，因?yàn)檎业健痩uyu’之后如果要找age=12的記錄采用遍歷的話時(shí)間復(fù)雜度較高，所以找到’luyu’應(yīng)該是第一個(gè)和最后一個(gè)，然后再根據(jù)age在[10,12]這里進(jìn)行二分查找

聯(lián)合索引實(shí)例

只有待查詢的數(shù)據(jù)在當(dāng)前范圍內(nèi)有序才能使用索引

a/b/c聯(lián)合索引：

select a from table where a = 10 and b <= 20 and c > 20  
-- a b會(huì)生效  
select a from table where a < 10 and b <= 20 and c > 20  
-- a會(huì)生效

name/age聯(lián)合索引：

select * from table1 where name like ‘張%’ and age = 12;  
-- 只有name會(huì)生效

為什么會(huì)有最左匹配

看了聯(lián)合索引樹葉子節(jié)點(diǎn)的排列形式應(yīng)該就清楚為什么要最左匹配了
因?yàn)槿绻钭蠖疾黄ヅ涓緹o法獲取當(dāng)前列的有序數(shù)據(jù)，更別提使用算法去查找了

索引覆蓋

為了避免回表（額外訪問1次主鍵樹）
比如select Id from t where k = 1此時(shí)Id已經(jīng)存在葉子節(jié)點(diǎn)了，無需回表

select v from t where k = 1如果存在 k v的聯(lián)合索引，此時(shí)也無需回表查詢
這也是常見的一種優(yōu)化手段。

索引下推

key ‘Index_Uni’ (‘name’,’age’)

select * from tuser where name like ‘張%’ and age=10;  

此時(shí)只有name的索引會(huì)生效，MySQL5.6之后采用了優(yōu)化策略，在定位到’張%’后，無需立即回表查詢對(duì)應(yīng)age=10的記錄，而是可以先在索引樹上遍歷age=10的記錄再回表查詢。

數(shù)據(jù)庫索引的查詢算法

t1(a int primary key, b int key)

select * from t1 where b >= 4;

上面sql等價(jià)于查找第一個(gè)b=4的位置

select * from t1 where b <= 4;

上面sql等價(jià)于查找最后一個(gè)b=4的位置

后續(xù)會(huì)單獨(dú)寫一篇二分查找的文章解決類似的問題

一條SQL語句慢的原因

偶爾慢

1. 數(shù)據(jù)庫在刷頁，redo log和內(nèi)存中的事務(wù)刷到磁盤中
2. 拿不到鎖，block住

日常慢

1. 沒有索引
2. 有索引但是沒用到
3. 索引field函數(shù)操作/不符合最左匹配
4. 數(shù)據(jù)庫選錯(cuò)索引

有時(shí)候即使一個(gè)字段上有索引也不會(huì)走，數(shù)據(jù)庫會(huì)判斷走索引和全表掃描的優(yōu)劣，判斷是通過采樣來決定的（這意味著有可能判斷錯(cuò)誤），此時(shí)可以使用force index(xx)。