04 | 深入淺出索引（上） 索引的出現其實就是為了提高數據查詢的效率，就像書的目錄一樣 索引的常見模型 哈希表、有序數組和搜索樹 哈希表 User2 和 User4 根據身份證號算出來的值都是 N，但沒關係，後面還跟了一個鏈表。 需要註意的是，圖中四個 ID_card_n hash 出來的值並不是 ...
04 | 深入淺出索引（上）
索引的出現其實就是為了提高數據查詢的效率，就像書的目錄一樣
索引的常見模型
哈希表、有序數組和搜索樹
哈希表
User2 和 User4 根據身份證號算出來的值都是 N，但沒關係，後面還跟了一個鏈表。
需要註意的是，圖中四個 ID_card_n hash 出來的值並不是遞增的，這樣做的好處是增加新的 User 時速度會很快，只需要往後追加。但缺點是，因為不是有序的，所以哈希索引做區間查詢的速度是很慢的，需要全部掃描一遍。
所以，哈希表這種結構適用於只有等值查詢的場景，比如 Memcached 及其他一些 NoSQL 引擎。
有序數組
有序數組在等值查詢和範圍查詢場景中的性能就都非常優秀
數組就是按照身份證號遞增的順序保存的。這時候如果你要查 ID_card_n2 對應的名字，用二分法就可以快速得到，這個時間複雜度是 O(log(N))
同樣可以通過二分找到大於範圍和小於範圍的兩個值
更新數據的時候必須得挪動後面所有的記錄，成本太高
有序數組索引只適用於靜態存儲引擎
二叉樹
二叉搜索樹：一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；二叉搜索樹的左、右子樹也分別為二叉搜索樹。
平衡二叉樹：平衡二叉樹是在二叉搜索樹的基礎上引入的，指的是結點的左子樹和右子樹的深度差不超過 1.
多叉樹：每個結點可以有多個子結點，子節點的大小從左到右依次遞增。
二叉搜索樹的特點是：每個節點的左兒子小於父節點，父節點又小於右兒子。這樣如果你要查 ID_card_n2 的話，按照圖中的搜索順序就是按照 UserA -> UserC -> UserF -> User2 這個路徑得到。這個時間複雜度是 O(log(N))
當然為了維持 O(log(N)) 的查詢複雜度，你就需要保持這棵樹是平衡二叉樹。為了做這個保證，更新的時間複雜度也是 O(log(N))
一棵 100 萬節點的平衡二叉樹，樹高 20。一次查詢可能需要訪問 20 個數據塊
Q：為什麼樹高20就是20個數據塊？
A：每個葉子結點就是一個塊，每個塊包含兩個數據（？），塊之間通過鏈式方式鏈接。樹高20的話，就要遍歷20個塊。因為是二叉樹結構，每次指針查找很大概率是觸發隨機磁碟讀（比如很難剛好碰上一個節點和他的左右兒子剛好相鄰）
資料庫中的所有數據都存儲於數據塊中，而葉子節點塊只是數據塊的一種，因為它位於索引b*tree結構中的最末端（root(根)-->branch(分枝)-->leaf(葉子)），所以，就稱為葉子節點塊（leaf node block）
《個人理解》參照下麵的B+樹，一個葉子塊中可以存放多條索引和數據
為了讓一個查詢儘量少地讀磁碟，就必須讓查詢過程訪問儘量少的數據塊。那麼，我們就不應該使用二叉樹，而是要使用“N 叉”樹。這裡，“N 叉”樹中的“N”取決於數據塊的大小。
Q：B+樹是一顆N叉樹，N是由什麼決定的？能否調整？
A:
-
通過修改page的大小來間接調整N的大小。一個節點上的所有數據都在一個page中，頁越大，每頁存放的索引就越多，N就越大。數據頁調整後，如果數據頁太小層數會太深，數據頁太大，載入到記憶體的時間和單個數據頁查詢時間會提高，需要達到平衡才行。
-
修改索引的大小。每個索引包括固定位元組數的Point指針和索引欄位內容，索引欄位越小，每頁能存的索引就越多，N就越大。
以 InnoDB 的一個整數欄位索引為例，這個 N 差不多是 1200。這棵樹高是 4 的時候，就可以存 1200 的 3 次方個值，這已經 17 億了。考慮到樹根的數據塊總是在記憶體中的，一個 10 億行的表上一個整數欄位的索引，查找一個值最多只需要訪問 3 次磁碟。其實，樹的第二層也有很大概率在記憶體中，那麼訪問磁碟的平均次數就更少了。
InnoDB 的索引模型
在 InnoDB 中，表都是根據主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表。
InnoDB 使用了 B+ 樹索引模型，所以數據都是存儲在 B+ 樹中的。
假設，我們有一個主鍵列為 ID 的表，表中有欄位 k，並且在 k 上有索引。
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）。
Q：基於主鍵索引和普通索引的查詢有什麼區別？
A：
- 如果語句是 select * from T where ID=500，即主鍵查詢方式，則只需要搜索 ID 這棵 B+ 樹；
- 如果語句是 select * from T where k=5，即普通索引查詢方式，則需要先搜索 k 索引樹，得到 ID 的值為 500，再到 ID 索引樹搜索一次。這個過程稱為回表。
索引維護
B+ 樹為了維護索引有序性，在插入新值的時候需要做必要的維護。
以上面這個圖為例，
如果插入新的行 ID 值為 700，則只需要在 R5 的記錄後面插入一個新記錄。
如果新插入的 ID 值為 400，就相對麻煩了，需要邏輯上挪動後面的數據，空出位置。
而更糟的情況是，如果 R5 所在的數據頁已經滿了，根據 B+ 樹的演算法，這時候需要申請一個新的數據頁，然後挪動部分數據過去。這個過程稱為頁分裂。
當相鄰兩個頁由於刪除了數據，利用率很低之後，會將數據頁做合併。
Q：如果插入的數據是在主鍵樹葉子結點的中間，後面的所有頁如果都是滿的狀態，是不是會造成後面的每一頁都會去進行頁分裂操作，直到最後一個頁申請新頁移過去最後一個值?
A: 不會不會，只會分裂它要寫入的那個頁面。每個頁面之間是用指針串的，改指針就好了，不需要“後面的全部挪動
ps:數據塊和數據頁的含義應該是一致的
自增主鍵
自增主鍵是指自增列上定義的主鍵，在建表語句中一般是這麼定義的： NOT NULL PRIMARY KEY AUTO_INCREMENT。
好處：（存，查，插）
- 插入新記錄的時候可以不指定 ID 的值，系統會獲取當前 ID 最大值加 1 作為下一條記錄的 ID 值。每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂。
- 自增欄位為整形或長整型，每個非主鍵索引的葉子節點上都是主鍵的值，主鍵長度越小，普通索引的葉子節點就越小，普通索引占用的空間也就越小。
- 業務邏輯欄位不容易保證索引樹結點有序插入，這樣寫入成本較高。
Q:有沒有什麼場景適合用業務欄位直接做主鍵的呢？
A:典型的 KV 場景
-
只有一個索引；
-
該索引必須是唯一索引
這時候我們就要優先考慮上一段提到的“儘量使用主鍵查詢”原則，直接將這個索引設置為主鍵，可以避免每次查詢需要搜索兩棵樹。
自增ID用完了怎麼辦？
表的自增 id 達到上限後，再申請時它的值就不會改變，進而導致繼續插入數據時報主鍵衝突的錯誤
索引重建
重建普通索引時，直接先刪除索引，再重新創建即可。
alter table T drop index k;
alter table T add index(k);
主鍵索引不能通過上面的語句去重建，因為刪除主鍵索引後，innodb會如下處理:
- 如果存在非空且欄位類型為數值的唯一索引（INT and NOT NULL and UNIQUE INDEX）， 會將第一個滿足條件的索引作為主鍵索引, _rowid為對應主鍵，值與唯一索引相同。(可通過
select _rowid from table查詢)。 - 如果找不到合適的索引，那麼 InnoDB 會自動生成一個不可見的名為 ROW_ID 的列名為 GEN_CLUST_INDEX 的主鍵索引，該列是一個 6 位元組的自增數值，隨著插入而自增。
所以刪除主鍵索引的結果其實是修改了主鍵欄位，而普通索引的葉子節點存的是主鍵的值，所以，一旦修改了主鍵欄位，普通索引也會有影響，葉子節點的值將被修改成新的主鍵欄位。
當主鍵索引需要重建時，更好的做法是直接使用alter table t engine=innodb重建表。
05 | 深入淺出索引（下）
Q ：執行 select * from T where k between 3 and 5，需要執行幾次樹的搜索操作，會掃描多少行？
A：
- 在 k 索引樹上找到 k=3 的記錄，取得 ID = 300；
- 再到 ID 索引樹查到 ID=300 對應的 R3；
- 在 k 索引樹取下一個值 k=5，取得 ID=500；
- 再回到 ID 索引樹查到 ID=500 對應的 R4；
- 在 k 索引樹取下一個值 k=6，不滿足條件，迴圈結束。
由於查詢結果所需要的數據只在主鍵索引上有，所以不得不回表。那麼，有沒有可能經過索引優化，避免回表過程呢？
覆蓋索引
如果執行的語句是 select ID from T where k between 3 and 5，這時只需要查 ID 的值，而 ID 的值已經在 k 索引樹上了，因此可以直接提供查詢結果，不需要回表。也就是說，在這個查詢裡面，索引 k 已經“覆蓋了”我們的查詢需求，我們稱為覆蓋索引。
由於覆蓋索引可以減少樹的搜索次數，顯著提升查詢性能，所以使用覆蓋索引是一個常用的性能優化手段。
在高頻請求考慮建立聯合索引（例如：（身份證號、姓名）），就是用到了覆蓋索引，不再需要回表查整行記錄，減少語句的執行時間。
最左首碼原則
「聯合索引的多個欄位中，只有當查詢條件為聯合索引的第一個欄位時，查詢才能使用該索引。」
這個最左首碼可以是聯合索引的最左 N 個欄位
「索引可以根據欄位值最左若幹個字元進行模糊查詢。」
分析（name，age）這個聯合索引，可以看到，索引項是按照索引定義裡面出現的欄位順序排序的。當你的邏輯需求是查到所有名字是“張三”的人時，可以快速定位到 ID4，然後向後遍歷得到所有需要的結果。如果你要查的是所有名字第一個字是“張”的人，你的 SQL 語句的條件是"where name like ‘張 %’"。這時，你也能夠用上這個索引，查找到第一個符合條件的記錄是 ID3，然後向後遍歷，直到不滿足條件為止。
現在，假設我們有一下三種查詢情景：
- 查出用戶名的第一個字是 “張” 開頭的人的密碼。即查詢條件子句為 "where username like ' 張 %'"
- 查處用戶名中含有 “張” 字的人的密碼。即查詢條件子句為 "where username like '% 張 %'"
- 查出用戶名以 “張” 字結尾的人的密碼。即查詢條件子句為 "where username like '% 張 '"
以上三種情況下，只有第 1 種能夠使用（username,password）聯合索引來加快查詢速度。
Q：表id為主鍵，username為普通索引，問select id, username from user_table where username like '%張%' 能否使用到 (username) 索引？
A：答案是可以的，因為查詢的所有欄位 (id, username) 在二級索引（username）中都存在，二級索引樹比主鍵索引樹小很多，所以會直接遍歷二級索引。值得註意的是，這裡是遍歷整個索引樹，而不是在索引樹中快速定位數據。
首碼索引
Q：需要根據 email 欄位查找用戶信息的需求，當然我們可以直接給 email 欄位創建一個索引，但我們仔細想想，有必要為整個 email 欄位創建索引嗎？
A：其實沒必要的，因為郵箱地址是有一個格式的，都是 "[email protected]", 所以其實 email 欄位的後面幾位區分度不高。這時為整個 email 欄位創建索引很浪費空間，我們可以創建首碼索引，將欄位的前幾個字元作為索引即可。
mysql 中使用 ADD KEY (column_name (prefix_length)) 為欄位創建首碼索引。
首碼索引設計的好壞在於選擇合適的首碼索引長度。如果選擇太長，會造成索引空間的浪費；如果選擇太短，會導致索引樹大量重覆的 key，索引效果不理想
問題：
- 使用首碼索引可能會增加記錄掃描次數與回表次數，影響性能
- 使用首碼索引就用不上覆蓋索引對查詢性能的優化了
首碼索引的區分度不夠高怎麼辦
一個很常見的解決手段就是 Hash。
對這個超長欄位 a 進行 hash(假設命名為 a_hash) 存入資料庫，然後對這個 hash 值建立索引，由於 hash 值同樣可能存在衝突，也就是說兩個不同的 a 通過 Hash 函數得到的結果可能是相同的，所以我們在查詢語句的 where 部分還需要進行一次精確判斷
索引下推
對於 user_table 表，我們現在有（username,age）聯合索引 如果現在有一個需求，查出名稱中以 “張” 開頭且年齡小於等於 10 的用戶信息，語句 C 如下：
"select * from user_table where username like ' 張 %' and age > 10".
語句 C 會根據（username,age）聯合索引查詢所有滿足名稱以 “張” 開頭的索引，然後直接再篩選出年齡小於等於 10 的索引，之後再回表查詢全行數據
第二種方式需要回表查詢的全行數據比較少，這就是 mysql 的索引下推，在索引遍歷過程中，對索引中包含的欄位先做判斷，直接過濾掉不滿足條件的記錄，減少回表次數。
https://copyfuture.com/blogs-details/20211116185246587T#_157
