常見的索引模型：
比較常見、也比較簡單的資料結構：它們分别是哈希表、有序數組、和搜尋樹。
哈希表
是一種以鍵-值存儲的資料結構，我們隻要輸入待查找的值就是key,就可以找到其對應的值即value,
哈希的思路很簡單，用一個函數把key換算成一個确定的位置，然後把value放在這個位置上。
當然不可避免的多個key值，經過哈希函數的計算，會出現同一個值的情況，處理這種情況的方法，就是拉出來一張
連結清單。
圖中，User2和User4根據身份證号算出來的值都是N，但沒關系，後面還跟了一個連結清單。假設，
這時候你要查ID_card_n2對應的名字是什麼，處理步驟就是：首先，将ID_card_n2通過哈希函
數算出N；然後，按順序周遊，找到User2。
需要注意的是，圖中四個ID_card_n的值并不是遞增的，這樣做的好處是增加新的User時速度會
很快，隻需要往後追加。但缺點是，因為不是有序的，是以哈希索引做區間查詢的速度是很慢
的。你可以設想下，如果你現在要找身份證号在[ID_card_X, ID_card_Y]這個區間的所有使用者，就必
須全部掃描一遍了。是以，哈希表這種結構适用于隻有等值查詢的場景，比如Memcached及其他一些NoSQL引
擎。
有序數組
而有序數組在等值查詢和範圍查詢場景中的性能就都非常優秀;
如果僅僅看查詢效率，有序數組就是最好的資料結構了。但是，在需要更新資料的時候就麻煩
了，你往中間插入一個記錄就必須得挪動後面所有的記錄，成本太高。
是以，有序數組索引隻适用于靜态存儲引擎，比如你要儲存的是2017年某個城市的所有人口
資訊，這類不會再修改的資料。
二叉搜尋樹
這樣如果你要查
ID_card_n2的話，按照圖中的搜尋順序就是按照UserA -> UserC -> UserF -> User2這個路徑得到。
二叉樹是搜尋效率最高的，但是實際上大多數的資料庫存儲卻并不使用二叉樹。
其原因是，索引不止存在記憶體中，還要寫到磁盤上。
你可以想象一下一棵100萬節點的平衡二叉樹，樹高20。一次查詢可能需要通路20個資料塊。在
機械硬碟時代，從磁盤随機讀一個資料塊需要10 ms左右的尋址時間。也就是說，對于一個100
萬行的表，如果使用二叉樹來存儲，單獨通路一個行可能需要20個10 ms的時間，這個查詢可真
夠慢的。
為了讓一個查詢盡量少地讀磁盤，就必須讓查詢過程通路盡量少的資料塊。那麼，我們就不應該
使用二叉樹，而是要使用“N叉”樹。這裡，“N叉”樹中的“N”取決于資料塊的大小：
N叉樹
以InnoDB的一個整數字段索引為例，這個N差不多是1200。這棵樹高是4的時候，就可以存
1200的3次方個值，這已經17億了。考慮到樹根的資料塊總是在記憶體中的，一個10億行的表上一
個整數字段的索引，查找一個值最多隻需要通路3次磁盤。其實，樹的第二層也有很大機率在内
存中，那麼通路磁盤的平均次數就更少了。N叉樹由于在讀寫上的性能優點，以及适配磁盤的通路模式，
已經被廣泛應用在資料庫引擎中了。
InnoDB 的索引模型
“B+ 樹是一種樹資料結構，通常用于資料庫和作業系統的檔案系統中。B+ 樹的特點是能夠保持資料穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+ 樹元素自底向上插入，這與二叉樹恰好相反。”
從圖中不難看出，索引類型分為主鍵索引和非主鍵索引；
基于主鍵索引和非主鍵索引的查詢有什麼差別？
如果語句是select * from T where ID=500，即主鍵查詢方式，則隻需要搜尋ID這棵B+樹；
如果語句是select * from T where k=5，即普通索引查詢方式，則需要先搜尋k索引樹，得到ID
的值為500，再到ID索引樹搜尋一次。這個過程稱為回表。
也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹。是以，我們在應用中應該盡量使用主
鍵查詢。
mysql> create
table T(
id int primary key,
k int not null,
name varchar(16),
index (k)
)engine=InnoDB; 索引維護
産生了問題：
B+樹為了維護索引有序性，在插入新值的時候需要做必要的維護。以上面這個圖為例，如果插
入新的行ID值為700，則隻需要在R5的記錄後面插入一個新記錄。如果新插入的ID值為400，就
相對麻煩了，需要邏輯上挪動後面的資料，空出位置。
而更糟的情況是，如果R5所在的資料頁已經滿了，根據B+樹的算法，這時候需要申請一個新的
資料頁，然後挪動部分資料過去。這個過程稱為頁分裂。在這種情況下，性能自然會受影響。
除了性能外，頁分裂操作還影響資料頁的使用率。原本放在一個頁的資料，現在分到兩個頁中，
整體空間使用率降低大約50%。
當然有分裂就有合并。當相鄰兩個頁由于删除了資料，使用率很低之後，會将資料頁做合并。合
并的過程，可以認為是分裂過程的逆過程。
解決辦法：
插入新記錄的時候可以不指定ID的值，系統會擷取目前ID最大值加1作為下一條記錄的ID值。
也就是說，自增主鍵的插入資料模式，正符合了我們前面提到的遞增插入的場景。每次插入一條
新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂。
自增主鍵是指自增列上定義的主鍵，在建表語句中一般是這麼定義的： NOT NULL PRIMARY
KEY AUTO_INCREMENT。
思考：
由于每個非主鍵索引的葉子節點上都是主鍵的值。如果用身份證号做主鍵，
那麼每個二級索引的葉子節點占用約20個位元組，
而如果用整型做主鍵，則隻要4個位元組，如果是長整型（bigint）則是8個位元組。