什么是索引？
索引的出現(xiàn)就是為了提高數(shù)據(jù)查詢的效率。
索引的常見模型
索引的出現(xiàn)時(shí)為了提高查詢效率，但是實(shí)現(xiàn)索引的方式卻又很多種，其中常見的有：哈希表、有序數(shù)組和搜索樹。
哈希表：
? ? 一種以鍵-值存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，只需要輸入待查找的值key，就可以找到其對(duì)應(yīng)的值value。哈希的思路很簡(jiǎn)單，把值放在數(shù)組里，用一個(gè)哈希函數(shù)把key換算成一個(gè)確定的位置，然后把value放在數(shù)組的這個(gè)位置。
有可能出現(xiàn)多個(gè)key值經(jīng)過哈希函數(shù)的換算會(huì)出現(xiàn)同一個(gè)值的情況。處理這種情況的一種方法是拉出一個(gè)鏈表。
哈希表結(jié)構(gòu)的使用場(chǎng)景
????從上圖可以看出哈希表索引的值并不是遞增的，這樣做的好處是增加新的User時(shí)速度會(huì)很快，只需要往后追加。但缺點(diǎn)是，因?yàn)椴皇怯行虻模怨Ｋ饕鰠^(qū)間查詢的速度是很慢的。
? ? 哈希表這種結(jié)構(gòu)適用于只有等值查詢的場(chǎng)景，比如memcached及其他一些Nosql引擎。
有序數(shù)組
有序數(shù)組因?yàn)槭怯行虻臄?shù)值存儲(chǔ)，在等值查詢和范圍查詢場(chǎng)景中的性能是非常優(yōu)秀的
適用場(chǎng)景
如果僅僅是看查詢效率，有序數(shù)組就是最好的數(shù)據(jù)結(jié)構(gòu)了。但是在需要更新數(shù)據(jù)的時(shí)候就麻煩了，
因?yàn)橥虚g插入一個(gè)記錄就必須要挪動(dòng)后面所有的記錄成本太高，所以，有序數(shù)組索引只適用于靜態(tài)存儲(chǔ)引擎。
二叉索引樹
二次叉搜索樹的特點(diǎn)是：每個(gè)節(jié)點(diǎn)的左兒子小于父節(jié)點(diǎn)，父節(jié)點(diǎn)又小于右兒子。以下圖為例子，如果要查ID_card_n2的話，按照?qǐng)D中的搜索順序就是按照UserA->UserC->UserF->User2這個(gè)路徑得到，這個(gè)時(shí)間復(fù)雜度是O(log(N))。
當(dāng)然為了維持O(log(N))的查詢復(fù)雜度，就需要保持這顆樹是平衡二叉樹，為了 做這個(gè)保證，更新的時(shí)間復(fù)雜度也是O(log(N))。
N叉樹
多叉樹就是每個(gè)節(jié)點(diǎn)有多個(gè)兒子，兒子之間的大小保證從左到右遞增。二叉樹是搜索效率最高的，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫存儲(chǔ)卻并不使用二叉樹。其原因是，索引不止存在內(nèi)存中，還要寫到磁盤上。為了讓一個(gè)查詢盡量少地讀磁盤，就必須讓查詢過程訪問盡量少的數(shù)據(jù)塊。那么，我們就不應(yīng)該使用二叉樹，而是要使用“N叉”樹，這里，“N叉”樹中的"N"取決于數(shù)據(jù)塊的大小。
InnoDB的索引模型
在InnoDB中，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲(chǔ)方式的表稱為索引組織表。又因?yàn)榍懊嫖覀兲岬降?，InnoDB使用了B+樹索引模型，所以數(shù)據(jù)都是存儲(chǔ)在B+樹中的。
每一個(gè)索引在InnoDB里面對(duì)應(yīng)一顆B+樹。
舉例：
假設(shè)，我們有一個(gè)主鍵列為ID的表，表中有字段K,并且在K上有索引
從圖中可以看出，根據(jù)葉子節(jié)點(diǎn)的內(nèi)容，索引類型分為逐漸索引和非主鍵索引。
主鍵索引的葉子節(jié)點(diǎn)存的是整行數(shù)據(jù)。在InnoDB里，主鍵索引也被稱為聚簇索引。
非主鍵索引的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值。在InnoDB里，非主鍵索引也被稱為二級(jí)索引。
主鍵索引和普通索引的區(qū)別？
索引維護(hù)
自增主鍵的適用場(chǎng)景
自增主鍵是指自增列上定義的主鍵，在建表語句中一般是這么定義的，NOT NULL PRIMARY KEY AUTO_INCREMENT。插入新記錄的時(shí)候可以不指定ID的值，系統(tǒng)會(huì)獲取當(dāng)前ID最大值加1作為下一條記錄的ID值。
也就是說，自增主鍵的插入數(shù)據(jù)模式，正符合了我們前面提到的遞增插入的場(chǎng)景。每次插入一條新記錄，都是追加操作，不涉及到挪動(dòng)其他記錄，也不會(huì)觸發(fā)葉子節(jié)點(diǎn)的分裂。
覆蓋索引
1、selec的數(shù)據(jù)列只用從索引中就能夠取到，不必從數(shù)據(jù)表中讀取，換句話說查詢列要被所使用的索引覆蓋；
2、索引是高效找到行的一個(gè)方法，當(dāng)能通過檢索索引就可以讀取想要的數(shù)據(jù)，那就不需要再到數(shù)據(jù)表中讀取行了。如果一個(gè)索引包含了滿足查詢語句中字段與條件的數(shù)據(jù)就叫做覆蓋索引；
3、是非聚集組合索引的一種形式，它包括再查詢里的select、join和where子句用到的所有列。
不是所有類型的索引都可以成為覆蓋索引。覆蓋索引必須要存儲(chǔ)索引的列，而哈希索引、空間索引和全文索引等都不存儲(chǔ)索引列的值，所以MySQL只能使用B-Tree索引做覆蓋索引
最左前綴原則
在建立聯(lián)合索引的時(shí)候，需要考慮如何安排索引內(nèi)的字段順序，因?yàn)榭梢灾С肿钭笄熬Y，所以當(dāng)已經(jīng)有了(a,b)這個(gè)聯(lián)合索引后，一般就不需要單獨(dú)再a上建立索引了。因此，第一原則是，如果通過調(diào)整順序，可以少維護(hù)一個(gè)索引，那么這個(gè)順序往往就是需要優(yōu)先考慮采用的。
索引下推
