容易來(lái)說(shuō)，索引的出現(xiàn)其實(shí)就是為了提升數(shù)據(jù)查詢的效率，就像書的目錄一樣。一本 500 頁(yè)的書，如果你想快速找到其中的某一個(gè)知識(shí)點(diǎn)，在不借助目錄的情況下，那我估計(jì)你可得找一會(huì)兒。同樣，對(duì)于數(shù)據(jù)庫(kù)的表而言，索引其實(shí)就是它的“目錄”。

索引模型

索引的出現(xiàn)是為了提升查詢效率，但是實(shí)現(xiàn)索引的方式卻有很多種，所以這里也就引入了索引模型的概念，一下是常見的三種：

哈希表

哈希表是一種以鍵值對(duì)的方式進(jìn)行存儲(chǔ)的。只要輸入key就可以查找到對(duì)應(yīng)的value，哈希思路很容易，就是放在一個(gè)有序數(shù)組中，通過(guò)一個(gè)可以計(jì)算出hash值的函數(shù)算出key指定一個(gè)位置，然后再將value放到對(duì)應(yīng)的位置上。
不可避免的還有哈希沖突，也就是算出了同一個(gè)哈希值作為key，發(fā)生哈希沖突時(shí)數(shù)據(jù)就會(huì)延升出一個(gè)鏈表，這個(gè)鏈表會(huì)存儲(chǔ)value，value會(huì)有一個(gè)next屬性指向下一個(gè)value。

圖中User1和User4算出了兩個(gè)相同的哈希值,不過(guò)沒(méi)關(guān)系，后面跟了一個(gè)鏈表，假設(shè)，這時(shí)候你要查 ID_1對(duì)應(yīng)的名字是什么，處理步驟就是：首先，將 ID_1 通過(guò)哈希函數(shù)算出 N；然后，按順序遍歷，找到 User1。

圖中的ID不是自增的，這樣做的好處是增加新的 User 時(shí)速度會(huì)很快，只需要往后追加。但缺點(diǎn)是，因?yàn)椴皇怯行虻?#xff0c;所以哈希索引做區(qū)間查詢的速度是很慢的。

你可以設(shè)想下，如果你現(xiàn)在要找ID在[ID_X, ID_Y]這個(gè)區(qū)間的所有用戶，就一定要全部掃描一遍了。所以，哈希表這種結(jié)構(gòu)適用于只有等值查詢的場(chǎng)景。

有序數(shù)組

但是有序數(shù)組在等值查詢的時(shí)候就特別優(yōu)秀，同樣是上面的例子。

這個(gè)數(shù)組就是按照ID號(hào)遞增的順序保存的。這時(shí)候如果你要查 ID3 對(duì)應(yīng)的名字，用二分法就可以快速得到，這個(gè)時(shí)間復(fù)雜度是 O(log(N))。

這個(gè)索引結(jié)構(gòu)支持范圍查詢。你要查ID號(hào)在[ID_X, ID_Y]區(qū)間的 User，可以先用二分法找到 ID_X（如果不存在 ID_X，就找到大于 ID_X 的第一個(gè) User），然后向右遍歷，直到查到第一個(gè)大于 ID_Y 的ID號(hào)，退出循環(huán)。

如果僅僅看查詢效率，有序數(shù)組就是最好的數(shù)據(jù)結(jié)構(gòu)了,但是需要更新時(shí)就很麻煩了，如果要往中間插入數(shù)據(jù)的話就要挪動(dòng)后面所有的數(shù)據(jù)。

一般可以使用在靜態(tài)數(shù)據(jù)或者常年不怎么改變的數(shù)據(jù)進(jìn)行存儲(chǔ)。

搜索樹

二叉搜索樹的特點(diǎn)是：父節(jié)點(diǎn)左子樹所有結(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值，右子樹所有結(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值。

這樣如果你要查 ID_4 的話，按照?qǐng)D中的搜索順序就是按照 UserA -> UserC ->User2 這個(gè)路徑得到。這個(gè)時(shí)間復(fù)雜度是 O(log(N))。

二叉樹是搜索效率最高的，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫(kù)存儲(chǔ)卻并不使用二叉樹。其原因是，索引不止存在內(nèi)存中，還要寫到磁盤上。

如果樹節(jié)點(diǎn)很多，還很高的話，這個(gè)查詢效率是非常底的。為了提升效率就一定要盡量的規(guī)避IO。

InnoDB 的索引模型

在 InnoDB 中，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲(chǔ)方式的表稱為索引組織表。InnoDB 使用了 B+ 樹索引模型，所以數(shù)據(jù)都是存儲(chǔ)在 B+ 樹中的。每一個(gè)索引在 InnoDB 里面對(duì)應(yīng)一棵 B+ 樹。

假設(shè)，我們有一個(gè)主鍵列為 ID 的表，表中有字段 k，并且在 k 上有索引。

mysql> create table T(id int primary key, k int not null, name varchar(16),index (k))engine=InnoDB;

然后假設(shè)表中有五行數(shù)據(jù)：(id,k) 值分別為 (100,1)、(200,2)、(300,3)、(400,4) 和 (500,5)。
兩棵樹的圖：

兩棵樹分為兩個(gè)索引：主鍵索引和非主鍵索引。

• 主鍵索引的葉子節(jié)點(diǎn)存儲(chǔ)的是整行的數(shù)據(jù)。（聚簇索引）
• 非主鍵索引的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值。（二級(jí)索引）

主鍵索引和非主鍵索引的區(qū)別

• 如果語(yǔ)句是 select * from T where ID=500，即主鍵查詢方式，則只需要搜索 ID 這棵 B+ 樹；
• 如果語(yǔ)句是 select * from T where k=5，即普通索引查詢方式，則需要先搜索 k 索引樹，得到 ID 的值為 500，再到 ID 索引樹搜索一次。這個(gè)過(guò)程稱為回表。

普通索引比主鍵索引多出了一次查詢，所有我們要盡可能的使用自增主鍵。

維護(hù)索引

如果需要在id500后面新增id600，就直接在后面插入，如果說(shuō)我要中間的位置插入數(shù)據(jù)的話成本又會(huì)顯的很高。需要邏輯上挪動(dòng)后面的數(shù)據(jù)，空出位置。

如果 R5 所在的數(shù)據(jù)頁(yè)已經(jīng)滿了，根據(jù) B+ 樹的算法，這時(shí)候需要申請(qǐng)一個(gè)新的數(shù)據(jù)頁(yè)，然后挪動(dòng)部分?jǐn)?shù)據(jù)過(guò)去。這個(gè)過(guò)程稱為頁(yè)分裂。在這種情況下，性能自然會(huì)受影響。

頁(yè)分裂操作還影響數(shù)據(jù)頁(yè)的利用率。原本放在一個(gè)頁(yè)的數(shù)據(jù)，現(xiàn)在分到兩個(gè)頁(yè)中，整體空間利用率降低大約 50%，也就是會(huì)挪動(dòng)50%到新的數(shù)據(jù)頁(yè)中。
比如我R3，R4，R5，R6挪動(dòng)50%，到新的數(shù)據(jù)頁(yè)里（新的數(shù)據(jù)頁(yè)中包含R7因?yàn)椴迦霑r(shí)候不夠了所以分頁(yè)了呀），R3，R4，R5，R6、R7（這是挪過(guò)來(lái)的數(shù)據(jù)）。
當(dāng)然有分裂就有合并。

怎么選擇索引，使用自增還是普通的業(yè)務(wù)索引？

自增主鍵的插入數(shù)據(jù)模式，正符合了我們前面提到的遞增插入的場(chǎng)景。每次插入一條新記錄，都是追加操作，都不涉及到挪動(dòng)其他記錄，也不會(huì)觸發(fā)葉子節(jié)點(diǎn)的分裂。

而有業(yè)務(wù)邏輯的字段做主鍵，則往往不容易保證有序插入，這樣寫數(shù)據(jù)成本相對(duì)較高。

還有一方面就是存儲(chǔ)空間的考慮：我們上面也說(shuō)了普通索引的葉子節(jié)點(diǎn)存的主鍵索引的ID。假設(shè)身份證這個(gè)唯一的字符串做主鍵索引的話，其他的普通索引的葉子節(jié)點(diǎn)就會(huì)存儲(chǔ)主鍵索引的值，身份證一般18個(gè)子符，可以想象多占空間，如果用整型就是4字節(jié)。

主鍵長(zhǎng)度越小，普通索引的葉子節(jié)點(diǎn)就越小，普通索引占用的空間也就越小

什么場(chǎng)景適合用業(yè)務(wù)字段直接做主鍵的呢？

• 只有一個(gè)索引；
• 該索引一定要是唯一索引。

典型的 KV 場(chǎng)景。

索引覆蓋

就是主鍵索引和非主鍵索引之間，非主鍵索引總是需要回表。這方面就可以采用索引覆蓋去優(yōu)化，覆蓋索引可以減少樹的搜索次數(shù)，顯著提升查詢性能，所以使用覆蓋索引是一個(gè)常用的性能優(yōu)化手段。

SELECT ID FROM SHADIAO WHERE K 1 BETWEEN 2;

這條語(yǔ)句需要執(zhí)行幾次樹的搜索操作，會(huì)掃描多少行？

去K的索引字段取到k=1，id=100；

再到 id 索引樹查到 id=100 對(duì)應(yīng)的 R1；

再取k=2索引，葉子節(jié)點(diǎn)值是id=200；

再回表到主鍵索引id=200取到R2；

然后k再取下一個(gè)值3，繼續(xù)循環(huán)判斷條件成不成立，不成立循環(huán)結(jié)束。

可以看到這個(gè)過(guò)程非常的繁瑣，來(lái)會(huì)進(jìn)行回表的操作，因?yàn)楦鶕?jù)k查詢的結(jié)果都在主鍵中，所以不得不回表取數(shù)據(jù)。

如果這個(gè)語(yǔ)句只需要查詢ID的值，而ID的值也已經(jīng)在k索引上了，因此可以直接提供查詢結(jié)果，不需要回表了，其實(shí)就是這個(gè)K已經(jīng)覆蓋了我們需要的查詢結(jié)果，被稱為覆蓋索引。

聯(lián)合索引

舉個(gè)栗子：就是如果我有一個(gè)id和身份證號(hào)加姓名這幾個(gè)字段，這個(gè)時(shí)候我要根據(jù)身份證號(hào)去查詢姓名的話，我需不需要把身份證號(hào)和姓名建立聯(lián)合索引（多個(gè)索引合起來(lái)作為一個(gè)聯(lián)合索引，如(card,name，size>1單值索引是聯(lián)合索引size=1的特例）？

答案是肯定的，建立聯(lián)合索引后，查詢身份證號(hào)的時(shí)候就不用去回表去主鍵索引拿到整行數(shù)據(jù)再找到姓名這個(gè)字段了，而是直接將姓名這個(gè)字段結(jié)果返回了。(因?yàn)槁?lián)合索引存的是聯(lián)合字段+主鍵值)。

其實(shí)索引高多了成本也是很高的。

最左前綴

接上個(gè)栗子：給姓名和身份證號(hào)建立聯(lián)合索引（name,card_id）可以看的我是順序排列的，從左往右。
使用語(yǔ)句 like “name%” 這個(gè)索引就會(huì)生效：

• 顧名思義：最左優(yōu)先，以最左邊的為起點(diǎn)任何連續(xù)的索引都能匹配上。同時(shí)遇到范圍查詢(>、<、between、like)就會(huì)停止匹配（like “name%”會(huì)生效，like “%name”不會(huì)生效）。
• 例如：b = 2 如果建立(a,b)順序的索引，是匹配不到(a,b)索引的；但是如果查詢條件是a = 1 and b = 2-或者a=1(又或者是a = 2 and b = 1)就可以，因?yàn)閮?yōu)化器會(huì)自動(dòng)調(diào)整a,b的順序。
• 再比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)順序的索引，d是用不到索引的，因?yàn)閏字段是一個(gè)范圍查詢，它之后的字段會(huì)停止匹配。

索引下垂

還是用（name,card_id）這個(gè)例子，這兩個(gè)是個(gè)聯(lián)合索引，查詢語(yǔ)句 like “name%” 就可以獲取到數(shù)據(jù)了，但是如果我加了一個(gè)條件，語(yǔ)句變成了 like “name%” and card_id=2;
再遍歷這兩個(gè)索引的時(shí)候先對(duì)索引列進(jìn)行判斷，直接過(guò)濾掉不滿足條件的記錄，減少回表次數(shù)。

小結(jié)

如果有了（a,b）兩個(gè)聯(lián)合索引后就不需要去單獨(dú)維護(hù)一個(gè)a的索引了。
如果有一個(gè)基于a、b給自的查詢語(yǔ)句，比如條件里面只有b的話（a,b）索引就不會(huì)生效，這時(shí)候就不得不單獨(dú)維護(hù)一個(gè)單獨(dú)的索引了。
建立聯(lián)合索引可以有效的避免回表次數(shù)。比如（a,b)兩個(gè)索引，這和時(shí)候通過(guò)a去查詢到b的值的時(shí)候就可以直接獲取到b的數(shù)據(jù)而不用回表去查詢了。（聯(lián)合索引包含了字段值+主鍵id）
覆蓋索引是一種優(yōu)化索引，可以減少回表，就是當(dāng)我這個(gè)索引包含了要查詢的字段的值就可以不用回表查詢而是直接返回。

總結(jié)

以上是生活随笔為你收集整理的一篇搞懂mysql中的索引（大白话版）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。