date: 2019-05-25 16:53:22
常見索引模型
哈希表
- 插入很快次乓，只需要在對應位置插入值即可 O(1)
- 等值查詢也很快O(1)
- 區(qū)間查詢只能全表掃描 O(N) ， 因為索引是無序的
哈希表適合無需區(qū)間查詢的場景。
有序數(shù)組
- 等值查詢和范圍查詢都很快
- 插入操作需要后移所有元素婚夫，消耗很大
有序數(shù)組索引適合靜態(tài)存儲引擎，如2017年某個城市的人口數(shù)據(jù)這類不會改動的數(shù)據(jù)裸违。
排序樹
- crud都有O(logN)的速度
- 為了盡量減少隨機訪問呢岗，增加數(shù)的叉數(shù)，降低樹的高度儒喊；所以可以有二叉排序樹镣奋，也可以有多叉排序樹
InnoDB的索引模型
InnoDB使用了B+樹索引模型
主鍵索引和非主鍵索引
主鍵索引的葉子節(jié)點存的是整行數(shù)據(jù)
非主鍵索引的葉子節(jié)點內(nèi)容是主鍵的值
普通索引查詢方式，則需要先搜索非主鍵索引樹怀愧，得到主鍵的值侨颈，再到主鍵索引樹搜索一次，這個過程稱為回表芯义。也就是說哈垢，基于非主鍵索引的查詢需要多掃描一棵索引樹。因此扛拨，我們在應用中應該盡量使用主鍵查詢耘分。
索引維護
三種情況
- 索引樹葉子節(jié)點右側(cè)追加，直接插入即可
- 插入葉子節(jié)點間绑警，需邏輯上挪動后面的數(shù)據(jù)
- 數(shù)據(jù)頁已滿求泰，需要申請新的數(shù)據(jù)頁，然后挪部分數(shù)據(jù)過去计盒，這個過程成為頁分裂渴频；這種情況下不僅影響性能，還會降低數(shù)據(jù)頁的利用率
問題1：自增主鍵的意義北启？
盡量保證每次操作都是第一種情況卜朗，即有序插入，追加節(jié)點
問題2：如果有身份證號這種業(yè)務上能保證一致的列咕村，能否直接設置為主鍵场钉？
如果這個表中除了主鍵還有其他索引，那么不建議懈涛，因為這會導致其他非主鍵索引中存儲的值會變長惹悄。
如果只有一個唯一索引，那就可以放心大膽的設置它為主鍵了肩钠，這樣可以避免非主鍵索引的回表操作泣港；這里描述的場景就是典型的kv場景暂殖。
覆蓋索引
表T的結(jié)構(gòu)如下
| id(主鍵) | k(索引) | s |
|---|---|---|
| 100 | 1 | aa |
| 200 | 2 | bb |
| 300 | 3 | cc |
| 500 | 5 | ee |
| 600 | 6 | ff |
| 700 | 7 | gg |
當我們執(zhí)行select * from T where k between 3 and 5時，它的執(zhí)行流程如下：
- 在k索引樹上找到k=3的記錄当纱，取得 ID = 300呛每；
- 再到ID索引樹查到ID=300對應的R3；
- 在k索引樹取下一個值k=5坡氯，取得ID=500晨横；
- 再回到ID索引樹查到ID=500對應的R4；
- 在k索引樹取下一個值k=6箫柳，不滿足條件手形，循環(huán)結(jié)束。
在這個過程中悯恍，回到主鍵索引樹搜索的過程库糠，我們稱為回表′毯粒可以看到瞬欧，這個查詢過程讀了k索引樹的3條記錄（步驟1、3和5）罢防，回表了兩次（步驟2和4）艘虎。
問題：如何避免回表過程？
執(zhí)行語句select ID from T where k between 3 and 5咒吐，因為要查詢的ID的值已經(jīng)在k的索引樹上了野建，所以不再需要回表。
在這個查詢里面恬叹，索引k已經(jīng)“覆蓋了”我們的查詢需求候生，我們稱為覆蓋索引
Tips：利用覆蓋索引優(yōu)化性能
市民信息表中，有身份證號和姓名兩個字段妄呕，如果有高頻需求是根據(jù)身份證號查詢姓名陶舞，那我們可以考慮給身份證號和姓名建立聯(lián)合索引嗽测，以便利用覆蓋索引提高查詢性能绪励。
最左前綴
基本概念
當已經(jīng)有了(a,b)這個聯(lián)合索引后，一般就不需要單獨在a上建立索引了
如果通過調(diào)整順序唠粥，可以少維護一個索引疏魏，那么這個順序往往就是需要優(yōu)先考慮采用的
考慮空間
如果既有聯(lián)合查詢，又有基于a晤愧、b各自的查詢呢大莫？查詢條件里面只有b的語句，是無法使用(a,b)這個聯(lián)合索引的官份，這時候你不得不維護另外一個索引只厘，也就是說你需要同時維護(a,b)烙丛、(b) 這兩個索引。
這時候羔味，我們要考慮的原則就是空間了河咽。比如上面這個市民表的情況，name字段是比age字段大的 赋元，那我就建議你創(chuàng)建一個（name,age)的聯(lián)合索引和一個(age)的單字段索引忘蟹。
索引下推
在MySQL5.6中引入了索引下推優(yōu)化，可以在索引遍歷過程中搁凸，對索引中包含的字段先做判斷媚值，直接過濾掉不滿足條件的記錄，減少回表次數(shù)护糖。
舉個栗子
假設現(xiàn)在有聯(lián)合索引（name, age）褥芒，執(zhí)行select * from tuser where name like '張%' and age=10 and ismale=1;
