摘要：深入淺出索引本文是在看極客時(shí)間實(shí)戰(zhàn)講時(shí)記的筆記，整理下加深理解。也就是說(shuō)基于非主鍵索引查詢會(huì)多掃描一次索引樹。

本文是在看極客時(shí)間《Mysql實(shí)戰(zhàn)45講》時(shí)記的筆記，整理下加深理解。

簡(jiǎn)單來(lái)說(shuō)，數(shù)據(jù)庫(kù)索引就是為了提高數(shù)據(jù)庫(kù)查詢的效率，就像書的目錄一樣，可以根據(jù)目錄快速的找到其中的某一個(gè)知識(shí)點(diǎn)。

哈希表

有序數(shù)組

搜索樹

簡(jiǎn)單的介紹下以上三種模型：

==哈希表==是一種以鍵-值(key-value)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，我們只要輸入待查找的key值，就可以找到其對(duì)應(yīng)的值value，哈希的思路很簡(jiǎn)單，把值放在數(shù)組里，通過(guò)一個(gè)哈希函數(shù)把key換算成一個(gè)確定的位置，然后把value放在數(shù)組的這個(gè)位置。不可避免的情況下，多個(gè)Key值經(jīng)過(guò)哈希運(yùn)算會(huì)出現(xiàn)同一個(gè)值的情況，處理這種情況的一種方法是拉出一個(gè)鏈表。

由于哈希表內(nèi)部的排序并不是遞增的，所以新增元素的時(shí)候速度會(huì)很快，但缺點(diǎn)是因?yàn)椴皇怯行虻模?strong>所以哈希表做區(qū)間查詢的速度是很慢的。所以，哈希表這種結(jié)構(gòu)只適用于只有等值查詢的場(chǎng)景，比如Memcached以及其他Nosql引擎。

==有序數(shù)組==在等值查詢和范圍查詢場(chǎng)景中的性能都非常優(yōu)秀。但是在需要更新數(shù)據(jù)的時(shí)候就很麻煩了，如果在中間插入一個(gè)記錄就必須挪動(dòng)后面所有的記錄，成本太高。所以有序數(shù)組只適用于靜態(tài)存儲(chǔ)引擎。

N叉樹在讀寫上的性能優(yōu)點(diǎn)，以及適配磁盤的訪問(wèn)模式，已經(jīng)被廣泛應(yīng)用于數(shù)據(jù)庫(kù)引擎中了。

不管是哈希還是有序數(shù)組，或者 N 叉樹，它們都是不斷迭代、不斷優(yōu)化的產(chǎn)物或者解決方案。在我們心里要有個(gè)概念，數(shù)據(jù)庫(kù)底層存儲(chǔ)的核心就是基于這些數(shù)據(jù)模型的，每碰到一個(gè)新的數(shù)據(jù)庫(kù)，我們都應(yīng)先關(guān)注他的數(shù)據(jù)模型，這樣才能從理論上分析出這個(gè)數(shù)據(jù)庫(kù)的應(yīng)用場(chǎng)景。

在InnoDB中，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲(chǔ)方式的表稱為索引組織表。InnoDB使用了B+樹索引模型，所以數(shù)據(jù)都是存儲(chǔ)在B+樹中的。

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

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

這個(gè)表的建表語(yǔ)句：

mysql> 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),兩棵樹的示意圖如下：

從圖中我們可以看出來(lái)，根據(jù)葉子節(jié)點(diǎn)的內(nèi)容，索引分為主鍵索引和非主鍵索引。

主鍵索引的葉子節(jié)點(diǎn)存放的是整行的數(shù)據(jù)，非主鍵索引的葉子節(jié)點(diǎn)存放的是主鍵的值。

根據(jù)上面的索引結(jié)構(gòu)說(shuō)明，我們可以得出一個(gè)問(wèn)題，基于主鍵索引和普通索引的查詢區(qū)別：

如果語(yǔ)句是select * from T where ID = 500;,即主鍵查詢方式，則只需要搜索ID這顆B+樹；

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

也就是說(shuō)基于非主鍵索引查詢會(huì)多掃描一次索引樹。

B+樹為了維護(hù)索引的有序性，在插入新值的時(shí)候需要做必要的維護(hù)。

建表時(shí)，盡量保持有自增主鍵。每次插入一條新記錄，都是追加操作，都不涉及到挪動(dòng)其他記錄，也不會(huì)觸發(fā)葉子節(jié)點(diǎn)的分裂。

而有業(yè)務(wù)邏輯的字段做主鍵，則往往不容易保證有序插入。

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

所以從性能和存儲(chǔ)空間來(lái)看，自增主鍵往往是更合理的選擇。

如果執(zhí)行的語(yǔ)句是 select ID from T where k between 3 and 5，這時(shí)只需要查 ID 的值，而ID 的值已經(jīng)在 k 索引樹上了，因此可以直接提供查詢結(jié)果，不需要回表。也就是說(shuō)，在這個(gè)查詢里面，索引 k 已經(jīng)“覆蓋了”我們的查詢需求，我們稱為覆蓋索引。

由于覆蓋索引可以減少樹的搜索次數(shù)，顯著提升查詢性能，所以使用覆蓋索引是常用的性能優(yōu)化手段。

第一原則是，如果通過(guò)調(diào)整順序，可以少維護(hù)一個(gè)索引，那么這個(gè)順序往往就是需要優(yōu)先考慮采用的。

其次考慮的就是空間，比如name 字段是比 age 字段大的 ，那我就建議你創(chuàng)建一個(gè)(name,age) 的聯(lián)合索引和一個(gè) (age) 的單字段索引。

在Mysql5.6之前，只能從最左前綴查詢到ID開始一個(gè)個(gè)回表，到主鍵索引上找出數(shù)據(jù)行，再對(duì)比字段值。

Mysql5.6之后，引入索引下推的優(yōu)化，可以在遍歷過(guò)程中，對(duì)索引中包含的字段先做判斷，直接過(guò)濾掉不滿足條件的記錄，減少回表次數(shù)。

總之在滿足語(yǔ)句需求的情況下，盡量地減少訪問(wèn)資源是數(shù)據(jù)庫(kù)設(shè)計(jì)的重要原則之一。我們?cè)谑褂脭?shù)據(jù)庫(kù)的時(shí)候，尤其在設(shè)計(jì)表結(jié)構(gòu)時(shí)，也要以減少資源消耗為目標(biāo)。

極客時(shí)間《Mysql實(shí)戰(zhàn)45講》