04 索引

索引：為了提高數據查詢的效率，就像書的目錄一樣。

索引的常見模型

哈希表

圖中，User2 和 User4 根據身份證號算出來的值都是 N，後面還跟了一個鏈表。假設，這時候你要查 ID_card_n2 對應的名字是什麼，處理步驟就是：首先，將 ID_card_n2 通過哈希函數算出 N；然後，按順序遍歷，找到 User2。

需要註意的是，圖中四個 ID_card_n 的值並不是遞增的，好處是增加新的 User 時速度會很快，只需要往後追加。缺點是，因為不是有序的，所以哈希索引做區間查詢的速度是很慢的。****

哈希表結構適用於只有等值查詢的場景。

有序數組

有序數組在等值查詢和範圍查詢場景中的性能就都非常優秀。

要查 ID_card_n2 對應的名字，用二分法就可以快速得到，時間複雜度是 O(log(N))。同時很顯然，這個索引結構也支持範圍查詢。

僅僅看查詢效率，有序數組就是最好的數據結構。但是，在需要更新數據的時候就麻煩了，往中間插入一個記錄就必須得挪動後面所有的記錄，成本太高。

所以，有序數組索引只適用於靜態存儲引擎。

N 叉樹

二叉搜索樹的特點是：父節點左子樹所有結點的值小於父節點的值，右子樹所有結點的值大於父節點的值。

如果你要查 ID_card_n2 的話，圖中的搜索順序就是按照 UserA -> UserC -> UserF -> User2 這個路徑得到。時間複雜度是 O(log(N))。

為了維持 O(log(N)) 的查詢複雜度，需要保持這棵樹是平衡二叉樹。為了做這個保證，更新的時間複雜度也是 O(log(N))。

二叉樹是搜索效率最高的，但是實際上大多數的資料庫存儲卻並不使用二叉樹。其原因是，索引不止存在記憶體中，還要寫到磁碟上。

InnoDB 的索引模型

在 MySQL 中，索引是在存儲引擎層實現的。

InnoDB 使用了 B+ 樹索引模型，每一個索引在 InnoDB 裡面對應一棵 B+ 樹。

一個主鍵列為 ID 的表，表中有欄位 k，並且在 k 上有索引。

表中 R1~R5 的 (ID,k) 值分別為 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，兩棵樹的示例示意圖如下。

根據葉子節點的內容，索引類型分為主鍵索引和非主鍵索引。

• 主鍵索引的葉子節點存的是整行數據。在 InnoDB 里，主鍵索引也被稱為聚簇索引（clustered index）。
• 非主鍵索引的葉子節點內容是主鍵的值。在 InnoDB 里，非主鍵索引也被稱為二級索引（secondary index）。

基於主鍵索引和普通索引的查詢區別？：

• select * from T where ID=500，即主鍵查詢方式，則只需要搜索 ID 這棵 B+ 樹；
• select * from T where k=5，即普通索引查詢方式，需要先搜索 k 索引樹，得到 ID 值為 500，再到 ID 索引樹搜索一次。這個過程稱為回表。

基於非主鍵索引的查詢需要多掃描一棵索引樹，因此在應用中應該儘量使用主鍵查詢。

索引維護

• 主鍵長度越小，普通索引的葉子節點就越小，普通索引占用的空間也就越小。
• 有業務邏輯的欄位做主鍵，則往往不容易保證有序插入，寫數據成本相對較高。

從性能和存儲空間方面考量，自增主鍵往往是更合理的選擇。

同時適合用業務欄位直接做主鍵的場景是：

• 只有一個索引；
• 該索引必須是唯一索引。

由於沒有其他索引，所以也就不用考慮其他索引的葉子節點大小的問題。

這時候優先考慮“儘量使用主鍵查詢”原則，直接將這個索引設置為主鍵，可以避免每次查詢需要搜索兩棵樹。

問：對於 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);

對於上面這兩個重建索引的作法，說出你的理解。

答：為什麼要重建索引。索引可能因為刪除，或者頁分裂等原因，導致數據頁有空洞，重建索引的過程會創建一個新的索引，把數據按順序插入，重建索引使得頁面的利用率最高，也就是索引更緊湊、更省空間。

重建索引 k 的做法是合理的，可以達到省空間的目的。但是，重建主鍵的過程不合理。

不論是刪除主鍵還是創建主鍵，都會將整個表重建。所以連著執行這兩個語句的話，第一個語句就白做了。這兩個語句，你可以用這個語句代替 ： alter table T engine=InnoDB。