三種常見的數(shù)據(jù)結(jié)構(gòu)： 哈希表倦春、有序數(shù)組和搜索樹户敬。
- 哈希表這種結(jié)構(gòu)適用于只有等值查詢的場景，通過key 算出位置（可能會重復）每個位置上的valus是一個數(shù)組睁本，按順序遍歷尿庐，用二分法就可以快速得到，這個時間復雜度是 O(log(N))呢堰。有序數(shù)組索引只適用于靜態(tài)存儲引擎
- 哈希沖突的處理辦法：鏈表
- 二叉樹抄瑟，二叉搜索樹的特點是：父節(jié)點左子樹所有結(jié)點的值小于父節(jié)點的值，右子樹所有結(jié)點的值大于父節(jié)點的值枉疼。這個時間復雜度是 O(log(N))皮假。但是實際上大多數(shù)的數(shù)據(jù)庫存儲卻并不使用二叉樹。其原因是骂维，索引不止存在內(nèi)存中惹资，還要寫到磁盤上。
- N 叉樹由于在讀寫上的性能優(yōu)點航闺，以及適配磁盤的訪問模式褪测，“N 叉”樹中的“N”取決于數(shù)據(jù)塊的大小。
- 數(shù)據(jù)庫存儲大多不適用二叉樹潦刃，因為樹高過高侮措，會適用N叉樹
InnoDB 的索引模型
- 在 InnoDB 中，表都是根據(jù)主鍵順序以索引的形式存放的乖杠，這種存儲方式的表稱為索引組織表分扎。又因為前面我們提到的，InnoDB 使用了 B+ 樹索引模型胧洒，所以數(shù)據(jù)都是存儲在 B+ 樹中的笆包。
- 索引類型分為主鍵索引和非主鍵索引。
- 主鍵索引的葉子節(jié)點存的是整行數(shù)據(jù)略荡。在 InnoDB 里，主鍵索引也被稱為聚簇索引（clustered index）歉胶。
- 非主鍵索引的葉子節(jié)點內(nèi)容是主鍵的值汛兜。在 InnoDB 里，非主鍵索引也被稱為二級索引（secondary index）通今。
- B+樹的葉子節(jié)點是page （頁）粥谬，一個頁里面可以存多個行肛根，內(nèi)部有個有序數(shù)組，二分法
主鍵索引與非主鍵索引查詢區(qū)別
- 非主鍵索引先查詢非索引
- 基于非主鍵索引的查詢需要多掃描一棵索引樹漏策。因此派哲，我們在應用中應該盡量使用主鍵查詢。
索引維護
由于每個非主鍵索引的葉子節(jié)點上都是主鍵的值掺喻。主鍵長度越小芭届，普通索引的葉子節(jié)點就越小，普通索引占用的空間也就越小感耙。
一個數(shù)據(jù)頁滿了褂乍，按照B+Tree算法，新增加一個數(shù)據(jù)頁即硼，叫做頁分裂逃片，會導致性能下降≈凰郑空間利用率降低大概50%褥实。當相鄰的兩個數(shù)據(jù)頁利用率很低的時候會做數(shù)據(jù)頁合并，合并的過程是分裂過程的逆過程裂允。
索引的創(chuàng)建問題
- 重新建索引是可以的
- 重新建主鍵相當于重新建表 （用空的alter操作损离，比如ALTER TABLE t1 ENGINE = InnoDB）
- 刪除數(shù)據(jù)但是存儲空間依然占用很大的問題，因為頁分裂等原因叫胖，導致數(shù)據(jù)頁有空洞草冈，重建索引的過程會創(chuàng)建一個新的索引，把數(shù)據(jù)按順序插入瓮增，這樣頁面的利用率最高怎棱，也就是索引更緊湊、更省空間绷跑。
覆蓋索引
只有索引包含了where條件部分和select返回部分的所有字段才能達到真正的減少回表
- 查詢的字段在索引的葉子節(jié)點中就是覆蓋索引 select id from table where a=100
- 由于覆蓋索引可以減少樹的搜索次數(shù)拳恋，顯著提升查詢性能，所以使用覆蓋索引是一個常用的性能優(yōu)化手段砸捏。
- 聯(lián)合索引谬运，在建立冗余索引來支持覆蓋索引時就需要權(quán)衡考慮了
- 如果查詢條件使用的是普通索引（或是聯(lián)合索引的最左原則字段），查詢結(jié)果是聯(lián)合索引的字段或是主鍵垦藏，不用回表操作梆暖，直接返回結(jié)果，減少IO磁盤讀寫讀取正行數(shù)據(jù)
最左前綴原則與索引下推
- 聯(lián)合索引（a掂骏，b轰驳，c）起作用的索引是 單獨查a 或 （a,b）或 （a,b,c ）然而 單獨查b或c 以及（b，c）不起作用，B+ 樹這種索引結(jié)構(gòu)级解，可以利用索引的“最左前綴”冒黑，來定位記錄。
- （a,b）中b起到作用就是索引下推勤哗，可以在索引遍歷過程中抡爹，對索引中包含的字段先做判斷，直接過濾掉不滿足條件的記錄芒划，減少回表次數(shù)冬竟。在索引內(nèi)部判斷b是否滿足條件，再選擇回表
表的邏輯結(jié)構(gòu)
表的邏輯結(jié)構(gòu) 腊状，表 —> 段 —> 段中存在數(shù)據(jù)段(leaf node segment) 诱咏，索引段( Non-leaf node segment）
例子
- select * from T where k in(1,2,3,4,5) 樹搜索5次 而 select * from T where k between 1 and 5 只需要1次
- mysql的myisam引擎支持事務，通過lock table缴挖，但是這樣只能實現(xiàn)串行化隔離級別袋狞，崩潰也無法修復，
- “a > 5 and a < 10 and b='123'” 在ICP作用下的執(zhí)行過程是什么樣子的映屋？
a) 把 a>5 and b='123'傳入引擎
b) 引擎找到第一個a>5的行（這里是快速定位）苟鸯，如果發(fā)現(xiàn)b='123',找下一個，直到滿足b='123',
c) 把找到的行返回給server層棚点， server層根據(jù)a是否小于10決定要不要取下一個
