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

本文是在看極客時間《Mysql實戰45講》時記的筆記，整理下加深理解。

簡單來說，數據庫索引就是為了提高數據庫查詢的效率，就像書的目錄一樣，可以根據目錄快速的找到其中的某一個知識點。

哈希表

有序數組

搜索樹

簡單的介紹下以上三種模型：

==哈希表==是一種以鍵-值(key-value)存儲的數據結構，我們只要輸入待查找的key值，就可以找到其對應的值value，哈希的思路很簡單，把值放在數組里，通過一個哈希函數把key換算成一個確定的位置，然后把value放在數組的這個位置。不可避免的情況下，多個Key值經過哈希運算會出現同一個值的情況，處理這種情況的一種方法是拉出一個鏈表。

由于哈希表內部的排序并不是遞增的，所以新增元素的時候速度會很快，但缺點是因為不是有序的，所以哈希表做區間查詢的速度是很慢的。所以，哈希表這種結構只適用于只有等值查詢的場景，比如Memcached以及其他Nosql引擎。

==有序數組==在等值查詢和范圍查詢場景中的性能都非常優秀。但是在需要更新數據的時候就很麻煩了，如果在中間插入一個記錄就必須挪動后面所有的記錄，成本太高。所以有序數組只適用于靜態存儲引擎。

N叉樹在讀寫上的性能優點，以及適配磁盤的訪問模式，已經被廣泛應用于數據庫引擎中了。

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

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

從圖中我們可以看出來，根據葉子節點的內容，索引分為主鍵索引和非主鍵索引。

主鍵索引的葉子節點存放的是整行的數據，非主鍵索引的葉子節點存放的是主鍵的值。

根據上面的索引結構說明，我們可以得出一個問題，基于主鍵索引和普通索引的查詢區別：

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

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

也就是說基于非主鍵索引查詢會多掃描一次索引樹。

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

建表時，盡量保持有自增主鍵。每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂。

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

同時主鍵的長度越小，普通索引的葉子節點就越小，普通索引占用的空間就越小。

所以從性能和存儲空間來看，自增主鍵往往是更合理的選擇。

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

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

第一原則是，如果通過調整順序，可以少維護一個索引，那么這個順序往往就是需要優先考慮采用的。

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

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

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

總之在滿足語句需求的情況下，盡量地減少訪問資源是數據庫設計的重要原則之一。我們在使用數據庫的時候，尤其在設計表結構時，也要以減少資源消耗為目標。

極客時間《Mysql實戰45講》