索引

索引常見的幾種類型

索引常見的類型有哈希索引，有序數(shù)組索引，二叉樹索引，跳表等等。本文主要探討 MySQL 的默認(rèn)存儲(chǔ)引擎 InnoDB 的索引結(jié)構(gòu)。

InnoDB的索引結(jié)構(gòu)

在InnoDB中是通過一種多路搜索樹——B+樹實(shí)現(xiàn)索引結(jié)構(gòu)的。在B+樹中是只有葉子結(jié)點(diǎn)會(huì)存儲(chǔ)數(shù)據(jù)，而且所有葉子結(jié)點(diǎn)會(huì)形成一個(gè)鏈表。而在InnoDB中維護(hù)的是一個(gè)雙向鏈表。

你可能會(huì)有一個(gè)疑問，為什么使用 B+樹 而不使用二叉樹或者B樹？

首先，我們知道訪問磁盤需要訪問到指定塊中，而訪問指定塊是需要 盤片旋轉(zhuǎn) 和 磁臂移動(dòng) 的，這是一個(gè)比較耗時(shí)的過程，如果增加樹高那么就意味著你需要進(jìn)行更多次的磁盤訪問，所以會(huì)采用n叉樹。

而使用B+樹是因?yàn)槿绻褂肂樹在進(jìn)行一個(gè)范圍查找的時(shí)候每次都會(huì)進(jìn)行重新檢索，而在B+樹中可以充分利用葉子結(jié)點(diǎn)的鏈表。

在建表的時(shí)候你可能會(huì)添加多個(gè)索引，而 InnDB 會(huì)為每個(gè)索引建立一個(gè) B+樹 進(jìn)行存儲(chǔ)索引。

比如這個(gè)時(shí)候我們建立了一個(gè)簡(jiǎn)單的測(cè)試表 

create table test(  
  id int primary key,  
  a int not null,  
  name varchar,  
  index(a)  
)engine = InnoDB; 

這個(gè)時(shí)候 InnDB 就會(huì)為我們建立兩個(gè) B+索引樹

一個(gè)是 主鍵 的 聚簇索引，另一個(gè)是 普通索引 的 輔助索引，這里我直接貼上 MySQL淺談（索引、鎖） 這篇文章上面的貼圖(因?yàn)槲覒胁幌氘媹D了。。。)

可以看到在輔助索引上面的葉子節(jié)點(diǎn)的值只是存了主鍵的值，而在主鍵的聚簇索引上的葉子節(jié)點(diǎn)才是存上了整條記錄的值。

回表

所以這里就會(huì)引申出一個(gè)概念叫回表，比如這個(gè)時(shí)候我們進(jìn)行一個(gè)查詢操作 

select name from test where a = 30; 

我們知道因?yàn)闂l件 MySQL 是會(huì)走 a 的索引的，但是 a 索引上并沒有存儲(chǔ) name 的值，此時(shí)我們就需要拿到相應(yīng) a 上的主鍵值，然后通過這個(gè)主鍵值去走 聚簇索引 最終拿到其中的name值，這個(gè)過程就叫回表。

我們來(lái)總結(jié)一下回表是什么？MySQL在輔助索引上找到對(duì)應(yīng)的主鍵值并通過主鍵值在聚簇索引上查找所要的數(shù)據(jù)就叫回表。

索引維護(hù)

我們知道索引是需要占用空間的，索引雖能提升我們的查詢速度但是也是不能濫用。

比如我們?cè)谟脩舯砝镉蒙矸葑C號(hào)做主鍵，那么每個(gè)二級(jí)索引的葉子節(jié)點(diǎn)占用約20個(gè)字節(jié)，而如果用整型做主鍵，則只要4個(gè)字節(jié)，如果是長(zhǎng)整型（bigint）則是8個(gè)字節(jié)。也就是說如果我用整型后面維護(hù)了4個(gè)g的索引列表，那么用身份證將會(huì)是20個(gè)g。

所以我們可以通過縮減索引的大小來(lái)減少索引所占空間。

當(dāng)然B+樹為了維護(hù)索引的有序性會(huì)在刪除，插入的時(shí)候進(jìn)行一些必要的維護(hù)(在InnoDB中刪除會(huì)將節(jié)點(diǎn)標(biāo)記為“可復(fù)用”以減少對(duì)結(jié)構(gòu)的變動(dòng))。

比如在增加一個(gè)節(jié)點(diǎn)的時(shí)候可能會(huì)遇到數(shù)據(jù)頁(yè)滿了的情況，這個(gè)時(shí)候就需要做頁(yè)的分裂，這是一個(gè)比較耗時(shí)的工作，而且頁(yè)的分裂還會(huì)導(dǎo)致數(shù)據(jù)頁(yè)的利用率變低，比如原來(lái)存放三個(gè)數(shù)據(jù)的數(shù)據(jù)頁(yè)再次添加一個(gè)數(shù)據(jù)的時(shí)候需要做頁(yè)分裂，這個(gè)時(shí)候就會(huì)將現(xiàn)有的四個(gè)數(shù)據(jù)分配到兩個(gè)數(shù)據(jù)頁(yè)中，這樣就減少了數(shù)據(jù)頁(yè)利用率。

覆蓋索引

上面提到了 回表，而有時(shí)候我們查輔助索引的時(shí)候就已經(jīng)滿足了我們需要查的數(shù)據(jù)，這個(gè)時(shí)候 InnoDB 就會(huì)進(jìn)行一個(gè)叫 覆蓋索引 的操作來(lái)提升效率，減少回表。

比如這個(gè)時(shí)候我們進(jìn)行一個(gè) select 操作 

select id from test where a = 1; 

這個(gè)時(shí)候很明顯我們走了 a 的索引直接能獲取到 id 的值，這個(gè)時(shí)候就不需要進(jìn)行回表，我們這個(gè)時(shí)候就使用了 覆蓋索引。

簡(jiǎn)單來(lái)說 覆蓋索引 就是當(dāng)我們走輔助索引的時(shí)候能獲取到我們所需要的數(shù)據(jù)的時(shí)候不需要再次進(jìn)行回表操作的操作。

聯(lián)合索引

這個(gè)時(shí)候我們新建一個(gè)學(xué)生表 

CREATE TABLE `stu` (  
  `id` int(11) NOT NULL,  
  `class` int(11) DEFAULT NULL,  
  `name` varchar(255) DEFAULT NULL,  
  PRIMARY KEY (`id`),  
  KEY `class_name` (`class`,`name`) USING BTREE  
) ENGINE=InnoDB DEFAULT CHARSET=utf8  

我們使用 class(班級(jí)號(hào)) 和 name 做一個(gè) 聯(lián)合索引，你可能會(huì)問這個(gè)聯(lián)合索引有什么用呢？我們可以結(jié)合著上面的 覆蓋索引 去理解，比如這個(gè)時(shí)候我們有一個(gè)需求，我們需要通過班級(jí)號(hào)去找對(duì)應(yīng)的學(xué)生姓名 。 

select name from stu where class = 102; 

這個(gè)時(shí)候我們就可以直接在 輔助索引 上查找到學(xué)生姓名而不需要再次回表。

總的來(lái)說，設(shè)計(jì)好索引，充分利用覆蓋索引能很大提升檢索速度。

最左前綴原則

這個(gè)是以 聯(lián)合索引 作為基礎(chǔ)的，是一種聯(lián)合索引的匹配規(guī)則。

這個(gè)時(shí)候，我們將上面的需求稍微變動(dòng)一下，這時(shí)我們有個(gè)學(xué)生遲到，但是他在門衛(wèi)記錄信息的時(shí)候只寫了自己的名字張三而沒有寫班級(jí)，所以我們需要通過學(xué)生姓名去查找相應(yīng)的班級(jí)號(hào)。 

select class from stu where name = '張三'; 

這個(gè)時(shí)候我們就不會(huì)走我們的聯(lián)合索引了，而是進(jìn)行了全表掃描。

為什么？因?yàn)?最左匹配原則。我們可以畫一張簡(jiǎn)單的圖來(lái)理解一下。

我們可以看到整個(gè)索引設(shè)計(jì)就是這么設(shè)計(jì)的，所以我們需要查找的時(shí)候也需要遵循著這個(gè)規(guī)則，如果我們直接使用name，那么InnoDB是不知道我們需要干什么的。

當(dāng)然最左匹配原則還有這些規(guī)則

•  全值匹配的時(shí)候優(yōu)化器會(huì)改變順序，也就是說你全值匹配時(shí)的順序和原先的聯(lián)合索引順序不一致沒有關(guān)系，優(yōu)化器會(huì)幫你調(diào)好。
•  索引匹配從最左邊的地方開始，如果沒有則會(huì)進(jìn)行全表掃描，比如你設(shè)計(jì)了一個(gè)(a,b,c)的聯(lián)合索引，然后你可以使用(a),(a,b),(a,b,c) 而你使用 (b),(b,c),(c)就用不到索引了。
•  遇到范圍匹配會(huì)取消索引。比如這個(gè)時(shí)候你進(jìn)行一個(gè)這樣的 select 操作 

select * from stu where class > 100 and name = '張三'; 

這個(gè)時(shí)候 InnoDB 就會(huì)放棄索引而進(jìn)行全表掃描，因?yàn)檫@個(gè)時(shí)候 InnoDB 會(huì)不知道怎么進(jìn)行遍歷索引，所以進(jìn)行全表掃描。

索引下推

我給你挖了個(gè)坑。剛剛的操作在 MySQL5.6 版本以前是需要進(jìn)行回表的，但是5.6之后的版本做了一個(gè)叫 索引下推 的優(yōu)化。 

select * from stu where class > 100 and name = '張三'; 

如何優(yōu)化的呢？因?yàn)閯倓偟淖钭笃ヅ湓瓌t我們放棄了索引，后面我們緊接著會(huì)通過回表進(jìn)行判斷 name，這個(gè)時(shí)候我們所要做的操作應(yīng)該是這樣的

但是有了索引下推之后就變成這樣了，此時(shí) "李四" 和 "小明" 這兩個(gè)不會(huì)再進(jìn)行回表。

因?yàn)檫@里匹配了后面的name = 張三，也就是說，如果最左匹配原則因?yàn)榉秶樵兘K止了，InnoDB還是會(huì)索引下推來(lái)優(yōu)化性能。

一些實(shí)踐

哪些情況需要?jiǎng)?chuàng)建索引？

•  頻繁作為查詢條件的字段應(yīng)創(chuàng)建索引。
•  多表關(guān)聯(lián)查詢的時(shí)候，關(guān)聯(lián)字段應(yīng)該創(chuàng)建索引。
•  查詢中的排序字段，應(yīng)該創(chuàng)建索引。
•  統(tǒng)計(jì)或者分組字段需要?jiǎng)?chuàng)建索引。

哪些情況不需要?jiǎng)?chuàng)建索引

• 表記錄少。
•  經(jīng)常增刪改查的表。
•  頻繁更新的字段。
•  where 條件使用不高的字段。
•  字段很大的時(shí)候。

其他

•  盡量選擇區(qū)分度高的列作為索引。
•  不要對(duì)索引進(jìn)行一些函數(shù)操作，還應(yīng)注意隱式的類型轉(zhuǎn)換和字符編碼轉(zhuǎn)換。
•  盡可能的擴(kuò)展索引，不要新建立索引。比如表中已經(jīng)有了a的索引，現(xiàn)在要加（a,b）的索引，那么只需要修改原來(lái)的索引即可。
•  多考慮覆蓋索引，索引下推，最左匹配。

鎖

全局鎖

MySQL提供了一個(gè)加全局讀鎖的方法，命令是 Flush tables with read lock (FTWRL)。當(dāng)你需要讓整個(gè)庫(kù)處于只讀狀態(tài)的時(shí)候，可以使用這個(gè)命令，之后其他線程的以下語(yǔ)句會(huì)被阻塞：數(shù)據(jù)更新語(yǔ)句（數(shù)據(jù)的增刪改）、數(shù)據(jù)定義語(yǔ)句（包括建表、修改表結(jié)構(gòu)等）和更新類事務(wù)的提交語(yǔ)句。

一般會(huì)在進(jìn)行 全庫(kù)邏輯備份 的時(shí)候使用，這樣就能確保 其他線程不能對(duì)該數(shù)據(jù)庫(kù)做更新操作。

在 MVCC 中提供了獲取 一致性視圖 的操作使得備份變得非常簡(jiǎn)單，如果想了解 MVCC 可以參考

https://juejin.im/post/5da8493ae51d4524b25add55

表鎖

MDL(Meta Data Lock)元數(shù)據(jù)鎖

MDL鎖用來(lái)保證只有一個(gè)線程能對(duì)該表進(jìn)行表結(jié)構(gòu)更改。

怎么說呢？MDL分為 MDL寫鎖 和 MDL讀鎖，加鎖規(guī)則是這樣的

•  當(dāng)線程對(duì)一個(gè)表進(jìn)行 CRUD 操作的時(shí)候會(huì)加 MDL讀鎖
•  當(dāng)線程對(duì)一個(gè)表進(jìn)行 表結(jié)構(gòu)更改 操作的時(shí)候會(huì)加 MDL寫鎖
•  寫鎖和讀鎖，寫鎖和寫鎖互斥，讀鎖之間不互斥

lock tables xxx read/write;

這是給一個(gè)表設(shè)置讀鎖和寫鎖的命令，如果在某個(gè)線程A中執(zhí)行l(wèi)ock tables t1 read, t2 write; 這個(gè)語(yǔ)句，則其他線程寫t1、讀寫t2的語(yǔ)句都會(huì)被阻塞。同時(shí)，線程A在執(zhí)行unlock tables之前，也只能執(zhí)行讀t1、讀寫t2的操作。連寫t1都不允許，自然也不能訪問其他表。

這種表鎖是一種處理并發(fā)的方式，但是在InnoDB中常用的是行鎖。

行鎖

我們知道在5.5版本以前 MySQL 的默認(rèn)存儲(chǔ)引擎是 MyISAM，而 MyISAM 和 InnoDB 最大的區(qū)別就是兩個(gè)

•  事務(wù)
•  行鎖

其中行鎖是我們今天的主題，如果不了解事務(wù)可以去補(bǔ)習(xí)一下。

其實(shí)行鎖就是兩個(gè)鎖，你可以理解為 寫鎖(排他鎖 X鎖)和讀鎖(共享鎖 S鎖)

•  共享鎖（S鎖）：允許一個(gè)事務(wù)去讀一行，阻止其他事務(wù)獲得相同數(shù)據(jù)集的排他鎖。也叫做讀鎖：讀鎖是共享的，多個(gè)客戶可以同時(shí)讀取同一個(gè)資源，但不允許其他客戶修改。
•  排他鎖（X鎖)：允許獲得排他鎖的事務(wù)更新數(shù)據(jù)，阻止其他事務(wù)取得相同數(shù)據(jù)集的共享讀鎖和排他寫鎖。也叫做寫鎖：寫鎖是排他的，寫鎖會(huì)阻塞其他的寫鎖和讀鎖。

而行鎖還會(huì)引起一個(gè)一個(gè)很頭疼的問題，那就是死鎖。

如果事務(wù)A對(duì)行100加了寫鎖，事務(wù)B對(duì)行101加了寫鎖，此時(shí)事務(wù)A想要修改行101而事務(wù)B又想修改行100，這樣占有且等待就導(dǎo)致了死鎖問題，而面對(duì)死鎖問題就只有檢測(cè)和預(yù)防了。

next-key鎖

MVCC 和行鎖是無(wú)法解決 幻讀 問題的，這個(gè)時(shí)候 InnoDB 使用了 一個(gè)叫 GAP鎖(間隙鎖) 的東西，它配合 行鎖 形成了 next-key鎖，解決了幻讀的問題。

但是因?yàn)樗募渔i規(guī)則，又導(dǎo)致了擴(kuò)大了一些加鎖范圍從而減少數(shù)據(jù)庫(kù)并發(fā)能力。具體的加鎖規(guī)則如下：

•  加鎖的基本單位是next-key lock 就是行鎖和GAP鎖結(jié)合。
•  查找過程中訪問到的對(duì)象就會(huì)加鎖。
•  索引上的等值查詢，給唯一索引加鎖的時(shí)候，next-key lock退化為行鎖。
•  索引上的等值查詢，向右遍歷時(shí)且最后一個(gè)值不滿足等值條件的時(shí)候，next-key lock退化為間隙鎖。
•  唯一索引上的范圍查詢會(huì)訪問到不滿足條件的第一個(gè)值為止。

MVCC 解決幻讀的思路比較復(fù)雜，這里就不做過多的驗(yàn)證。

總結(jié)

對(duì)于 MySQL 的索引來(lái)說，我給了很多實(shí)踐，其實(shí)這些實(shí)踐都是從原理來(lái)的，而 InnoDB 其實(shí)就是一個(gè)改進(jìn)版的 B+樹，還有存儲(chǔ)索引的結(jié)構(gòu)。弄懂了這些你就會(huì)得心應(yīng)手起來(lái)。

而對(duì)于 MySQL 的鎖，主要就是在行鎖方面，InnoDB 其實(shí)就是使用了 行鎖，MVCC還有next-key鎖來(lái)實(shí)現(xiàn)事務(wù)并發(fā)控制的。

而對(duì)于MySQL中最重要的其實(shí)就是 鎖和索引 了，因?yàn)閮?nèi)容太多這篇文章僅僅做一些介紹和簡(jiǎn)單的分析，如果想深入了解可以查看相應(yīng)的文章。