1、簡(jiǎn)介

索引是存儲(chǔ)引擎用于快速找到記錄的一種數(shù)據(jù)結(jié)構(gòu)。
索引對(duì)于良好的性能非常關(guān)鍵。尤其是當(dāng)表中的數(shù)據(jù)量越來(lái)越大時(shí)，索引對(duì)性能的影響愈發(fā)重要。
在數(shù)據(jù)量較小且負(fù)載較低時(shí)，不恰當(dāng)?shù)乃饕龑?duì)性能的影響可能還不明顯，但是數(shù)據(jù)量逐漸增大時(shí)，性能則會(huì)急劇下降。

推薦索引數(shù)據(jù)結(jié)構(gòu)視頻：https://www.bilibili.com/video/av56821095?p=1
推薦一個(gè)展示各種數(shù)據(jù)結(jié)構(gòu)的網(wǎng)站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

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

需要存下查詢記錄的索引，查詢記錄的地址
索引常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)有：hash、搜索樹(shù)

2.1、hash表

hash表只適合等值查詢，不適合范圍查詢

2.2.1、二叉搜索樹(shù)

二叉搜索樹(shù)的特點(diǎn)是：每個(gè)節(jié)點(diǎn)的左兒子小于父節(jié)點(diǎn)，父節(jié)點(diǎn)又小于右兒子
二叉搜索樹(shù)查詢的時(shí)間復(fù)雜度是O(log(N))，添加新的節(jié)點(diǎn)維護(hù)BST的結(jié)構(gòu)的時(shí)間復(fù)雜度是O(log(N))
對(duì)于順序的輸入BST的效率會(huì)變低。

二叉搜索樹(shù)

2.2.2、紅黑樹(shù)

紅黑樹(shù)是一種自平衡的二叉搜索樹(shù)，能保持O(log(N))搜索時(shí)間。

紅黑樹(shù)

2.2.3、B-Trees【平衡多叉搜索樹(shù)】

度(Degree)-節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)個(gè)數(shù)
葉節(jié)點(diǎn)具有相同的深度
葉節(jié)點(diǎn)的指針為空
節(jié)點(diǎn)中的數(shù)據(jù)key從左到右遞增排序

B-Tree

2.2.4、B+ Trees

B+樹(shù)非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)索引，所以每一層可以存儲(chǔ)更多的索引
B+樹(shù)天然具備排序功能：B+樹(shù)所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時(shí)候更方便，數(shù)據(jù)緊密性很高，緩存的命中率也會(huì)比B樹(shù)高。
B樹(shù)相對(duì)于B+樹(shù)的優(yōu)點(diǎn)是，如果經(jīng)常訪問(wèn)的數(shù)據(jù)離根節(jié)點(diǎn)很近，而B(niǎo)樹(shù)的非葉子節(jié)點(diǎn)本身存有關(guān)鍵字其數(shù)據(jù)的地址，所以這種數(shù)據(jù)檢索的時(shí)候會(huì)要比B+樹(shù)快。

B+ Tree

InnoDB使用了B+樹(shù)索引模型，默認(rèn)節(jié)點(diǎn)(page)大小16k

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';
結(jié)果：Innodb_page_size 16384

以BIGINT為索引為例，一個(gè)非葉子節(jié)點(diǎn)索引將包括(索引，下一個(gè)指針)，BIGINT 8 字節(jié)，下一個(gè)指針6個(gè)字節(jié)，共14字節(jié)。
每一個(gè)page可以存儲(chǔ)： 16k / (8 + 6) =1170， 每個(gè)節(jié)點(diǎn)大概能存儲(chǔ)1170個(gè)索引
假設(shè)葉子節(jié)點(diǎn)每個(gè)索引+data ，占1k，那么每個(gè)節(jié)點(diǎn)可以存16個(gè)索引，
所以三層的B+樹(shù)總的可以存1170 * 1170 * 16 大概2千萬(wàn)個(gè)索引。

3、InnoDB的索引模型

下面為極客時(shí)間的專欄，MySQL實(shí)戰(zhàn)45講/04.深入淺出索引（上）

在InnoDB中，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲(chǔ)方式的表稱為索引組織表。又因?yàn)榍懊嫖覀兲岬降?，InnoDB使用了B+樹(shù)索引模型，所以數(shù)據(jù)都是存儲(chǔ)在B+樹(shù)中的。

每一個(gè)索引在InnoDB里面對(duì)應(yīng)一棵B+樹(shù)。

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

這個(gè)表的建表語(yǔ)句是：
CREATE TABLE T (
    id INT PRIMARY KEY,
    k INT NOT NULL,
    name VARCHAR (16),
    INDEX (k)
) ENGINE = INNODB;

表中R1~R5的(ID,k)值分別為(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，兩棵樹(shù)的示例示意圖如下。

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

根據(jù)上面的索引結(jié)構(gòu)說(shuō)明，我們來(lái)討論一個(gè)問(wèn)題：基于主鍵索引和普通索引的查詢有什么區(qū)別？

如果語(yǔ)句是select * from T where ID=500，即主鍵查詢方式，則只需要搜索ID這棵B+樹(shù)；
如果語(yǔ)句是select * from T where k=5，即普通索引查詢方式，則需要先搜索k索引樹(shù)，得到ID的值為500，再到ID索引樹(shù)搜索一次。這個(gè)過(guò)程稱為回表。
也就是說(shuō)，基于非主鍵索引的查詢需要多掃描一棵索引樹(shù)。因此，我們?cè)趹?yīng)用中應(yīng)該盡量使用主鍵查詢。

索引維護(hù):

B+樹(shù)為了維護(hù)索引有序性，在插入新值的時(shí)候需要做必要的維護(hù)。以上面這個(gè)圖為例，如果插入新的行ID值為700，則只需要在R5的記錄后面插入一個(gè)新記錄。如果新插入的ID值為400，就相對(duì)麻煩了，需要邏輯上挪動(dòng)后面的數(shù)據(jù)，空出位置。

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

當(dāng)然有分裂就有合并。當(dāng)相鄰兩個(gè)頁(yè)由于刪除了數(shù)據(jù)，利用率很低之后，會(huì)將數(shù)據(jù)頁(yè)做合并。合并的過(guò)程，可以認(rèn)為是分裂過(guò)程的逆過(guò)程。

基于上面的索引維護(hù)過(guò)程說(shuō)明，我們來(lái)討論一個(gè)案例：

你可能在一些建表規(guī)范里面見(jiàn)到過(guò)類似的描述，要求建表語(yǔ)句里一定要有自增主鍵。當(dāng)然事無(wú)絕對(duì)，我們來(lái)分析一下哪些場(chǎng)景下應(yīng)該使用自增主鍵，而哪些場(chǎng)景下不應(yīng)該。

自增主鍵是指自增列上定義的主鍵，在建表語(yǔ)句中一般是這么定義的： NOT NULL PRIMARY KEY AUTO_INCREMENT。

插入新記錄的時(shí)候可以不指定ID的值，系統(tǒng)會(huì)獲取當(dāng)前ID最大值加1作為下一條記錄的ID值。

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

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

除了考慮性能外，我們還可以從存儲(chǔ)空間的角度來(lái)看。假設(shè)你的表中確實(shí)有一個(gè)唯一字段，比如字符串類型的身份證號(hào)，那應(yīng)該用身份證號(hào)做主鍵，還是用自增字段做主鍵呢？

由于每個(gè)非主鍵索引的葉子節(jié)點(diǎn)上都是主鍵的值。如果用身份證號(hào)做主鍵，那么每個(gè)二級(jí)索引的葉子節(jié)點(diǎn)占用約20個(gè)字節(jié)，而如果用整型做主鍵，則只要4個(gè)字節(jié)，如果是長(zhǎng)整型（bigint）則是8個(gè)字節(jié)。

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

所以，從性能和存儲(chǔ)空間方面考量，自增主鍵往往是更合理的選擇。

有沒(méi)有什么場(chǎng)景適合用業(yè)務(wù)字段直接做主鍵的呢？還是有的。比如，有些業(yè)務(wù)的場(chǎng)景需求是這樣的：

只有一個(gè)索引；
該索引必須是唯一索引。

你一定看出來(lái)了，這就是典型的KV場(chǎng)景。
由于沒(méi)有其他索引，所以也就不用考慮其他索引的葉子節(jié)點(diǎn)大小的問(wèn)題。
這時(shí)候我們就要優(yōu)先考慮上一段提到的“盡量使用主鍵查詢”原則，直接將這個(gè)索引設(shè)置為主鍵，可以避免每次查詢需要搜索兩棵樹(shù)。

小結(jié)

今天，我跟你分析了數(shù)據(jù)庫(kù)引擎可用的數(shù)據(jù)結(jié)構(gòu)，介紹了InnoDB采用的B+樹(shù)結(jié)構(gòu)，以及為什么InnoDB要這么選擇。B+樹(shù)能夠很好地配合磁盤(pán)的讀寫(xiě)特性，減少單次查詢的磁盤(pán)訪問(wèn)次數(shù)。

由于InnoDB是索引組織表，一般情況下我會(huì)建議你創(chuàng)建一個(gè)自增主鍵，這樣非主鍵索引占用的空間最小。但事無(wú)絕對(duì)，我也跟你討論了使用業(yè)務(wù)邏輯字段做主鍵的應(yīng)用場(chǎng)景。