一句話簡單來說，索引的出現(xiàn)其實就是為了提高數(shù)據(jù)查詢的效率，就像書的目錄一樣。
對于數(shù)據(jù)庫的表而言，索引其實就是它的“目錄”。
InnoDB索引的數(shù)據(jù)結(jié)構(gòu)模型
1 索引的常見模型
索引的出現(xiàn)是為了提高查詢效率，但是實現(xiàn)索引的方式卻有很多種，所以這里也就引入了索引模型的概念?？梢杂糜谔岣咦x寫效率的數(shù)據(jù)結(jié)構(gòu)很多，介紹三種常見、也比較簡單的數(shù)據(jù)結(jié)構(gòu)，它們分別是哈希表、有序數(shù)組和搜索樹。
從使用的角度，簡單分析一下這三種模型的區(qū)別。
哈希表是一種以鍵-值（key-value）存儲數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的值即key，就可以找到其對應的值即Value。哈希的思路很簡單，把值放在數(shù)組里，用一個哈希函數(shù)把key換算成一個確定的位置，然后把value放在數(shù)組的這個位置。
不可避免地，多個key值經(jīng)過哈希函數(shù)的換算，會出現(xiàn)同一個值的情況。處理這種情況的一種方法是，拉出一個鏈表。
假設，你現(xiàn)在維護著一個身份證信息和姓名的表，需要根據(jù)身份證號查找對應的名字，這時對應的哈希索引的示意圖如下所示：
圖中，User2和User4根據(jù)身份證號算出來的值都是N，但沒關系，后面還跟了一個鏈表。假設，這時候你要查ID_card_n2對應的名字是什么，處理步驟就是：首先，將ID_card_n2通過哈希函數(shù)算出N；然后，按順序遍歷，找到User2。
需要注意的是，圖中四個ID_card_n的值并不是遞增的，這樣做的好處是增加新的User時速度會很快，只需要往后追加。但缺點是，因為不是有序的，所以哈希索引做區(qū)間查詢的速度是很慢的。
你可以設想下，如果你現(xiàn)在要找身份證號在[ID_card_X, ID_card_Y]這個區(qū)間的所有用戶，就必須全部掃描一遍了。
所以，哈希表這種結(jié)構(gòu)適用于只有等值查詢的場景，比如Memcached及其他一些NoSQL引擎。
而有序數(shù)組在等值查詢和范圍查詢場景中的性能就都非常優(yōu)秀。還是上面這個根據(jù)身份證號查名字的例子，如果我們使用有序數(shù)組來實現(xiàn)的話，示意圖如下所示：
這里我們假設身份證號沒有重復，這個數(shù)組就是按照身份證號遞增的順序保存的。這時候如果你要查ID_card_n2對應的名字，用二分法就可以快速得到，這個時間復雜度是O(log(N))。
同時很顯然，這個索引結(jié)構(gòu)支持范圍查詢。你要查身份證號在[ID_card_X, ID_card_Y]區(qū)間的User，可以先用二分法找到ID_card_X（如果不存在ID_card_X，就找到大于ID_card_X的第一個User），然后向右遍歷，直到查到第一個大于ID_card_Y的身份證號，退出循環(huán)。
如果僅僅看查詢效率，有序數(shù)組就是最好的數(shù)據(jù)結(jié)構(gòu)了。但是，在需要更新數(shù)據(jù)的時候就麻煩了，你往中間插入一個記錄就必須得挪動后面所有的記錄，成本太高。
所以，有序數(shù)組索引只適用于靜態(tài)存儲引擎，比如你要保存的是2017年某個城市的所有人口信息，這類不會再修改的數(shù)據(jù)。
二叉樹--》二叉搜索樹--》 二叉平衡樹 --》 B樹 ---》 B+樹
二叉搜索樹也是課本里的經(jīng)典數(shù)據(jù)結(jié)構(gòu)了。還是上面根據(jù)身份證號查名字的例子，如果我們用二叉搜索樹來實現(xiàn)的話，示意圖如下所示：
二叉搜索樹示意圖
二叉搜索樹的特點是：每個節(jié)點的左兒子小于父節(jié)點，父節(jié)點又小于右兒子。這樣如果你要查ID_card_n2的話，按照圖中的搜索順序就是按照UserA -> UserC -> UserF -> User2這個路徑得到。這個時間復雜度是O(log(N))。
當然為了維持O(log(N))的查詢復雜度，你就需要保持這棵樹是平衡二叉樹。為了做這個保證，更新的時間復雜度也是O(log(N))。
樹可以有二叉，也可以有多叉。多叉樹就是每個節(jié)點有多個兒子，兒子之間的大小保證從左到右遞增。*二叉樹是搜索效率最高的，但是實際上大多數(shù)的數(shù)據(jù)庫存儲卻并不使用二叉樹。其原因是，索引不止存在內(nèi)存中，還要寫到磁盤上。
你可以想象一下一棵100萬節(jié)點的平衡二叉樹，樹高20。一次查詢可能需要訪問20個數(shù)據(jù)塊。在機械硬盤時代，從磁盤隨機讀一個數(shù)據(jù)塊需要10 ms左右的尋址時間。也就是說，對于一個100萬行的表，如果使用二叉樹來存儲，單獨訪問一個行可能需要20個10 ms的時間，這個查詢可真夠慢的。
為了讓一個查詢盡量少地讀磁盤，就必須讓查詢過程訪問盡量少的數(shù)據(jù)塊。那么，我們就不應該使用二叉樹，而是要使用“N叉”樹。這里，“N叉”樹中的“N”取決于數(shù)據(jù)塊的大小。
以InnoDB的一個整數(shù)字段索引為例，這個N差不多是1200。這棵樹高是4的時候，就可以存1200的3次方個值，這已經(jīng)17億了?？紤]到樹根的數(shù)據(jù)塊總是在內(nèi)存中的，一個10億行的表上一個整數(shù)字段的索引，查找一個值最多只需要訪問3次磁盤。其實，樹的第二層也有很大概率在內(nèi)存中，那么訪問磁盤的平均次數(shù)就更少了。
N叉樹由于在讀寫上的性能優(yōu)點，以及適配磁盤的訪問模式，已經(jīng)被廣泛應用在數(shù)據(jù)庫引擎中了。
不管是哈希還是有序數(shù)組，或者N叉樹，它們都是不斷迭代、不斷優(yōu)化的產(chǎn)物或者解決方案。數(shù)據(jù)庫技術發(fā)展到今天，跳表、LSM樹等數(shù)據(jù)結(jié)構(gòu)也被用于引擎設計中，這里我就不再一一展開了。
你心里要有個概念，數(shù)據(jù)庫底層存儲的核心就是基于這些數(shù)據(jù)模型的。每碰到一個新數(shù)據(jù)庫，我們需要先關注它的數(shù)據(jù)模型，這樣才能從理論上分析出這個數(shù)據(jù)庫的適用場景。
截止到這里，我用了半篇文章的篇幅和你介紹了不同的數(shù)據(jù)結(jié)構(gòu)，以及它們的適用場景，你可能會覺得有些枯燥。但是，我建議你還是要多花一些時間來理解這部分內(nèi)容，畢竟這是數(shù)據(jù)庫處理數(shù)據(jù)的核心概念之一，在分析問題的時候會經(jīng)常用到。當你理解了索引的模型后，就會發(fā)現(xiàn)在分析問題的時候會有一個更清晰的視角，體會到引擎設計的精妙之處。
現(xiàn)在，我們一起進入相對偏實戰(zhàn)的內(nèi)容吧。
在MySQL中，索引是在存儲引擎層實現(xiàn)的，所以并沒有統(tǒng)一的索引標準，即不同存儲引擎的索引的工作方式并不一樣。而即使多個存儲引擎支持同一種類型的索引，其底層的實現(xiàn)也可能不同。由于InnoDB存儲引擎在MySQL數(shù)據(jù)庫中使用最為廣泛，所以下面我就以InnoDB為例，和你分析一下其中的索引模型。
2 InnoDB 的索引模型
在InnoDB中，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表。又因為前面我們提到的，InnoDB使用了B+樹索引模型，所以數(shù)據(jù)都是存儲在B+樹中的。
每一個索引在InnoDB里面對應一棵B+樹。
假設，我們有一個主鍵列為ID的表，表中有字段k，并且在k上有索引。
這個表的建表語句是：
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)，兩棵樹的示例示意圖如下。
從圖中不難看出，根據(jù)葉子節(jié)點的內(nèi)容，索引類型分為主鍵索引和非主鍵索引。
主鍵索引的葉子節(jié)點存的是整行數(shù)據(jù)。在InnoDB里，主鍵索引也被稱為聚簇索引（clustered index）。
非主鍵索引的葉子節(jié)點內(nèi)容是主鍵的值。在InnoDB里，非主鍵索引也被稱為二級索引（secondary index）。
根據(jù)上面的索引結(jié)構(gòu)說明，我們來討論一個問題：基于主鍵索引和普通索引的查詢有什么區(qū)別？
如果語句是select * from T where ID=500，即主鍵查詢方式，則只需要搜索ID這棵B+樹；
如果語句是select * from T where k=5，即普通索引查詢方式，則需要先搜索k索引樹，得到ID的值為500，再到ID索引樹搜索一次。這個過程稱為回表。
也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹。因此，我們在應用中應該盡量使用主鍵查詢。
3 索引維護
B+樹為了維護索引有序性，在插入新值的時候需要做必要的維護。以上面這個圖為例，如果插入新的行ID值為700，則只需要在R5的記錄后面插入一個新記錄。如果新插入的ID值為400，就相對麻煩了，需要邏輯上挪動后面的數(shù)據(jù)，空出位置。
而更糟的情況是，如果R5所在的數(shù)據(jù)頁已經(jīng)滿了，根據(jù)B+樹的算法，這時候需要申請一個新的數(shù)據(jù)頁，然后挪動部分數(shù)據(jù)過去。這個過程稱為頁分裂。在這種情況下，性能自然會受影響。
除了性能外，頁分裂操作還影響數(shù)據(jù)頁的利用率。原本放在一個頁的數(shù)據(jù)，現(xiàn)在分到兩個頁中，整體空間利用率降低大約50%。
當然有分裂就有合并。當相鄰兩個頁由于刪除了數(shù)據(jù)，利用率很低之后，會將數(shù)據(jù)頁做合并。合并的過程，可以認為是分裂過程的逆過程。
基于上面的索引維護過程說明，我們來討論一個案例：
你可能在一些建表規(guī)范里面見到過類似的描述，*要求建表語句里一定要有自增主鍵。當然事無絕對，我們來分析一下哪些場景下應該使用自增主鍵，而哪些場景下不應該。
自增主鍵是指自增列上定義的主鍵，在建表語句中一般是這么定義的： NOT NULL PRIMARY KEY AUTO_INCREMENT。
插入新記錄的時候可以不指定ID的值，系統(tǒng)會獲取當前ID最大值加1作為下一條記錄的ID值。
也就是說，自增主鍵的插入數(shù)據(jù)模式，正符合了我們前面提到的遞增插入的場景。每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發(fā)葉子節(jié)點的分裂。
而有業(yè)務邏輯的字段做主鍵，則往往不容易保證有序插入，這樣寫數(shù)據(jù)成本相對較高。
除了考慮性能外，我們還可以從存儲空間的角度來看。假設你的表中確實有一個唯一字段，比如字符串類型的身份證號，那應該用身份證號做主鍵，還是用自增字段做主鍵呢？
由于每個非主鍵索引的葉子節(jié)點上都是主鍵的值。如果用身份證號做主鍵，那么每個二級索引的葉子節(jié)點占用約20個字節(jié)，而如果用整型做主鍵，則只要4個字節(jié)，如果是長整型（bigint）則是8個字節(jié)。
顯然，主鍵長度越小，普通索引的葉子節(jié)點就越小，普通索引占用的空間也就越小。
所以，從性能和存儲空間方面考量，自增主鍵往往是更合理的選擇。
有沒有什么場景適合用業(yè)務字段直接做主鍵的呢？還是有的。比如，有些業(yè)務的場景需求是這樣的：
- 只有一個索引；
- 該索引必須是唯一索引。
你一定看出來了，這就是典型的KV場景。
由于沒有其他索引，所以也就不用考慮其他索引的葉子節(jié)點大小的問題。
這時候我們就要優(yōu)先考慮上一段提到的“盡量使用主鍵查詢”原則，直接將這個索引設置為主鍵，可以避免每次查詢需要搜索兩棵樹。
4 小結(jié)
分析了數(shù)據(jù)庫引擎可用的數(shù)據(jù)結(jié)構(gòu)，介紹了InnoDB采用的B+樹結(jié)構(gòu)，以及為什么InnoDB要這么選擇。
B+樹能夠很好地配合磁盤的讀寫特性，減少單次查詢的磁盤訪問次數(shù)。
由于InnoDB是索引組織表，一般情況下我會建議你創(chuàng)建一個自增主鍵，這樣非主鍵索引占用的空間最小。但事無絕對，我也跟你討論了使用業(yè)務邏輯字段做主鍵的應用場景。
最后，我給你留下一個問題吧。對于上面例子中的InnoDB表T，如果你要重建索引 k，你的兩個SQL語句可以這么寫：
alter table T drop index k;
alter table T add index(k);
如果你要重建主鍵索引，也可以這么寫：
alter table T drop primary key;
alter table T add primary key(id);
我的問題是，對于上面這兩個重建索引的作法，說出你的理解。如果有不合適的，為什么，更好的方法是什么？
上期的問題是，通過兩個alter 語句重建索引k，以及通過兩個alter語句重建主鍵索引是否合理。
為什么要重建索引。我們文章里面有提到，索引可能因為刪除，或者頁分裂等原因，導致數(shù)據(jù)頁有空洞，重建索引的過程會創(chuàng)建一個新的索引，把數(shù)據(jù)按順序插入，這樣頁面的利用率最高，也就是索引更緊湊、更省空間。
這道題目，我給你的“參考答案”是：
重建索引k的做法是合理的，可以達到省空間的目的。但是，重建主鍵的過程不合理。不論是刪除主鍵還是創(chuàng)建主鍵，都會將整個表重建。所以連著執(zhí)行這兩個語句的話，第一個語句就白做了。這兩個語句，你可以用這個語句代替 ： alter table T engine=InnoDB。在專欄的第12篇文章《為什么表數(shù)據(jù)刪掉一半，表文件大小不變？》中，我會和你分析這條語句的執(zhí)行流程。
每一個表是好幾棵B+樹，每個索引一棵樹。
沒有主鍵的表，innodb會給默認創(chuàng)建一個Rowid做主鍵。
總結(jié)：
1.索引的作用：提高數(shù)據(jù)查詢效率
2.常見索引模型：哈希表、有序數(shù)組、搜索樹
3.哈希表：鍵 - 值(key - value)。
4.哈希思路：把值放在數(shù)組里，用一個哈希函數(shù)把key換算成一個確定的位置，然后把value放在數(shù)組的這個位置
5.哈希沖突的處理辦法：鏈表
6.哈希表適用場景：只有等值查詢的場景
7.有序數(shù)組：按順序存儲。查詢用二分法就可以快速查詢，時間復雜度是：O(log(N))
8.有序數(shù)組查詢效率高，更新效率低
9.有序數(shù)組的適用場景：靜態(tài)存儲引擎。
10.二叉搜索樹：每個節(jié)點的左兒子小于父節(jié)點，父節(jié)點又小于右兒子
11.二叉搜索樹：查詢時間復雜度O(log(N))，更新時間復雜度O(log(N))
12.數(shù)據(jù)庫存儲大多不適用二叉樹，因為樹高過高，會使用N叉樹
13.InnoDB中的索引模型：B+Tree
14.索引類型：主鍵索引、非主鍵索引
主鍵索引的葉子節(jié)點存的是整行的數(shù)據(jù)(聚簇索引)，非主鍵索引的葉子節(jié)點內(nèi)容是主鍵的值(二級索引)
15.主鍵索引和普通索引的區(qū)別：主鍵索引只要搜索ID這個B+Tree即可拿到數(shù)據(jù)。普通索引先搜索索引拿到主鍵值，再到主鍵索引樹搜索一次(回表)
16.一個數(shù)據(jù)頁滿了，按照B+Tree算法，新增加一個數(shù)據(jù)頁，叫做頁分裂，會導致性能下降?？臻g利用率降低大概50%。當相鄰的兩個數(shù)據(jù)頁利用率很低的時候會做數(shù)據(jù)頁合并，合并的過程是分裂過程的逆過程。
17.從性能和存儲空間方面考量，自增主鍵往往是更合理的選擇。
思考題：
如果刪除，新建主鍵索引，會同時去修改普通索引對應的主鍵索引，性能消耗比較大。
刪除重建普通索引貌似影響不大，不過要注意在業(yè)務低谷期操作，避免影響業(yè)務。
- 主鍵索引的葉子結(jié)點存儲了整一行的內(nèi)容（聚簇索引），使用主鍵可以快速獲取到整行的數(shù)據(jù)。
- 非主鍵索引的葉子結(jié)點存儲的是主鍵的值，所以主鍵字段占用空間不宜過大。同時，其查找數(shù)據(jù)的過程稱為“回表”，需要先查找自己得到主鍵值，再在主鍵索引上邊查找數(shù)據(jù)內(nèi)容。
- 索引的實現(xiàn)由存儲引擎來決定，InnoDB使用B+樹（N叉樹，比如1200叉樹），把整顆樹的高度維持在很小的范圍內(nèi)，同時在內(nèi)存里緩存前面若干層的節(jié)點，可以極大地降低訪問磁盤的次數(shù)，提高讀的效率。
- B+樹的插入可能會引起數(shù)據(jù)頁的分裂，刪除可能會引起數(shù)據(jù)頁的合并，二者都是比較重的IO消耗，所以比較好的方式是順序插入數(shù)據(jù)，這也是我們一般使用自增主鍵的原因之一。
- 在Key-Value的場景下，只有一個索引且是唯一索引，則適合直接使用業(yè)務字段作為主鍵索引。
