1. 引言

??索引的出現其實就是為了提高數據查詢的效率，就像書的目錄一樣。一本500 頁的書，如果你想快速找到其中的某一個知識點，在不借助目錄的情況下，那我估計你可得找一會兒。同樣，對于數據庫的表而言，索引其實就是它的“目錄”。

2. 索引的常見模型

這里我先給你介紹三種常見、也比較簡單的數據結構，它們分別是哈希表、有序數組和搜索樹。

哈希表

??哈希表是一種以鍵 - 值（key-value）存儲數據的結構，我們只要輸入待查找的值即 key，就可以找到其對應的值即 Value。哈希的思路很簡單，把值放在數組里，用一個哈希函數把key 換算成一個確定的位置，然后把 value 放在數組的這個位置。
??不可避免地，多個 key 值經過哈希函數的換算，會出現同一個值的情況。處理這種情況的一種方法是，拉出一個鏈表。
??假設，你現在維護著一個身份證信息和姓名的表，需要根據身份證號查找對應的名字，這時對應的哈希索引的示意圖如下所示：

??圖中，User2 和 User4 根據身份證號算出來的值都是 N，但沒關系，后面還跟了一個鏈表。假設，這時候你要查ID_card_n2 對應的名字是什么，處理步驟就是：首先，將ID_card_n2 通過哈希函數算出 N；然后，按順序遍歷，找到 User2。
??所以，哈希表這種結構適用于只有等值查詢的場景，比Memcached 及其他一些NoSQL 引擎。

有序數組

??有序數組在等值查詢和范圍查詢場景中的性能就都非常優秀。還是上面這個根據身份證號查名字的例子，如果我們使用有序數組來實現的話，示意圖如下所示：

??這里我們假設身份證號沒有重復，這個數組就是按照身份證號遞增的順序保存的。這時候如果你要查 ID_card_n2 對應的名字，用二分法就可以快速得到，這個時間復雜度是O(log(N))。
??所以，有序數組索引只適用于靜態存儲引擎，比如你要保存的是 2017 年某個城市的所有人口信息，這類不會再修改的數據。

二叉搜索樹

??二叉搜索樹也是課本里的經典數據結構了。還是上面根據身份證號查名字的例子，如果我們用二叉搜索樹來實現的話，示意圖如下所示：

??二叉搜索樹的特點是：每個節點的左兒子小于父節點，父節點又小于右兒子。這樣如果你要查 ID_card_n2 的話，按照圖中的搜索順序就是按照 UserA -> UserC -> UserF -> User2這個路徑得到。這個時間復雜度是 O(log(N))。
??以 InnoDB 的一個整數字段索引為例，這個 N 差不多是1200。這棵樹高是 4 的時候，就可以存 1200 的 3 次方個值，這已經 17 億了。考慮到樹根的數據塊總是在內存中的，一個10 億行的表上一個整數字段的索引，查找一個值最多只需要訪問 3 次磁盤。其實，樹的第二層也有很大概率在內存中，那么訪問磁盤的平均次數就更少了。

3. InnoDB的索引模型

??在 InnoDB 中，表都是根據主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表。又因為前面我們提到的，InnoDB 使用了 B+ 樹索引模型，所以數據都是存儲在 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)，兩棵樹的示例示意圖如下。

從圖中不難看出，根據葉子節點的內容，索引類型分為主鍵索引和非主鍵索引。

主鍵索引的葉子節點存的是整行數據。在 InnoDB 里，主鍵索引也被稱為聚簇索引（clustered index）。

非主鍵索引的葉子節點內容是主鍵的值。在 InnoDB 里，非主鍵索引也被稱為二級索引（secondary index）

基于主鍵索引和普通索引的查詢有什么區別？
3. 如果語句是 select * from T where ID=500，即主鍵查詢方式，則只需要搜索 ID 這棵B+ 樹；
4. 如果語句是 select * from T where k=5，即普通索引查詢方式，則需要先搜索 k 索引樹，得到 ID 的值為 500，再到 ID 索引樹搜索一次。這個過程稱為回表。

4. 索引維護

??B+ 樹為了維護索引有序性，在插入新值的時候需要做必要的維護。以上面這個圖為例，如果插入新的行 ID 值為 700，則只需要在 R5 的記錄后面插入一個新記錄。如果新插入的 ID值為 400，就相對麻煩了，需要邏輯上挪動后面的數據，空出位置。
??而更糟的情況是，如果 R5 所在的數據頁已經滿了，根據 B+ 樹的算法，這時候需要申請一個新的數據頁，然后挪動部分數據過去。這個過程稱為頁分裂。在這種情況下，性能自然會受影響。
??除了性能外，頁分裂操作還影響數據頁的利用率。原本放在一個頁的數據，現在分到兩個頁中，整體空間利用率降低大約 50%。

總結

以上是生活随笔為你收集整理的04 | 深入浅出索引（上）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。