??索引的出現(xiàn)是為了提高數(shù)據(jù)查詢效率，就像一本書的目錄。

一、索引的常見類型

1. 哈希表
2. 有序數(shù)組
3. 搜索樹

1、哈希表
??哈希表是一種鍵-值存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，通過哈希函數(shù)把key轉(zhuǎn)換成數(shù)組中一個(gè)確定的位置，然后把value放到這個(gè)位置。不同key得到相同位置時(shí)，一種解決方法是拉出一個(gè)鏈表，查找該值時(shí)遍歷該鏈表。
??但是可以想象，做區(qū)間查詢時(shí)速度會(huì)很慢，需要掃描全部的數(shù)據(jù)。因此，哈希表這種結(jié)構(gòu)適用于只有等值查詢的場(chǎng)景，比如Memcached及其他一些NoSQL引擎。

2、有序數(shù)組
??有序數(shù)組在等值查詢和范圍查詢場(chǎng)景中的性能都很優(yōu)秀?？梢酝ㄟ^二分法O(log(N))快速查到一個(gè)遞增數(shù)組中的值。僅看查詢效率，有序數(shù)組是最好的數(shù)據(jù)結(jié)構(gòu)。但是，更新數(shù)據(jù)時(shí)，往中間插入一個(gè)記錄就必須挪動(dòng)后面所有的記錄，成本太高。因此，有序數(shù)組適用用靜態(tài)存儲(chǔ)引擎，如2017年某個(gè)城市的人口信息。

3、搜索樹
??二叉搜索樹的特點(diǎn)是每個(gè)節(jié)點(diǎn)的左兒子小于父節(jié)點(diǎn)，父節(jié)點(diǎn)小于右節(jié)點(diǎn)。查詢時(shí)間復(fù)雜度為O(log(N))。為了維護(hù)O(log(N))的復(fù)雜度，要保證這棵樹為平衡二叉樹，更新的時(shí)間復(fù)雜度也是O(log(N))。
??樹有二叉，也有多叉。二叉樹搜索效率最高，然而大多數(shù)數(shù)據(jù)庫存儲(chǔ)不使用二叉。因?yàn)樗饕恢淮嬖趦?nèi)存中，還要寫到磁盤上。想象下一顆100萬節(jié)點(diǎn)的平衡二叉樹，樹高20，一次查詢可能需要訪問20個(gè)數(shù)據(jù)塊。機(jī)械硬盤時(shí)代，從磁盤讀一數(shù)據(jù)塊需要10ms左右的尋址時(shí)間，訪問一個(gè)100萬行的表如果用二叉樹存儲(chǔ)，可能需要20*10ms毫秒的時(shí)間，可真夠慢的。
??為了讓一個(gè)查詢盡量少讀磁盤，就必須讓查詢過程訪問盡量少的數(shù)據(jù)塊，因此使用'N叉'。
??InnoDB的整數(shù)字段索引，這個(gè)N差不多是1200。當(dāng)樹高為4時(shí)，1200的三次方已經(jīng)可以存儲(chǔ)17億行數(shù)據(jù)了?？紤]到樹根總在內(nèi)存中，一個(gè)10億行表上的整數(shù)字段索引，查找一個(gè)值最多只需要訪問三次磁盤。其實(shí)第二層很大概率也在內(nèi)存中，因此訪問磁盤的平均次數(shù)就更少了。

二、InnoDB的索引引擎

??InnoDB中，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲(chǔ)方式的表稱為索引組織表。InnoDB使用B+樹索引模型，所有的數(shù)據(jù)都是存在B+樹中的。
??每個(gè)索引在InnoDB里對(duì)應(yīng)一顆B+樹，一張表就是1或者幾個(gè)B+樹組成的。
??如下表：

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)，兩棵樹的示例示意圖如下。

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

??索引類型根據(jù)葉子節(jié)點(diǎn)的內(nèi)容，分為主鍵索引和非主鍵索引。
??主鍵索引葉子結(jié)點(diǎn)存的是整行數(shù)據(jù)，主鍵索引也稱為聚簇索引(clustered index)。
??非主鍵索引葉子結(jié)點(diǎn)存的是主鍵的值，非主鍵索引也稱為二級(jí)索引(secondary index)。

基于主鍵索引和普通索引的查詢有什么區(qū)別?

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

三、索引維護(hù)

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

??而更糟的情況是，如果 R5 所在的數(shù)據(jù)頁已經(jīng)滿了，根據(jù) B+ 樹的算法，這時(shí)候需要申請(qǐng)一個(gè)新的數(shù)據(jù)頁，然后挪動(dòng)部分?jǐn)?shù)據(jù)過去。這個(gè)過程稱為頁分裂。在這種情況下，性能自然會(huì)受影響。頁分裂操作還影響數(shù)據(jù)頁的利用率。原本放在一個(gè)頁的數(shù)據(jù)，現(xiàn)在分到兩個(gè)頁中，整體空間利用率降低大約 50%。

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

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

除了考慮性能外，我們還可以從存儲(chǔ)空間的角度來看。

??假設(shè)你的表中確實(shí)有一個(gè)唯一字段，比如字符串類型的身份證號(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ǔ)空間方面考量，自增主鍵往往是更合理的選擇。**

本文是對(duì)極客時(shí)間中林曉斌老師的《Mysql實(shí)戰(zhàn)45講》的筆記總結(jié)，長(zhǎng)期更新。
如有侵權(quán)，請(qǐng)聯(lián)系我立刻刪除。