索引的出現(xiàn)其實(shí)就是為了提高數(shù)據(jù)查詢(xún)的效率，就像書(shū)的目錄一樣。
【索引的常見(jiàn)模型】哈希表、有序數(shù)組和搜索樹(shù)。數(shù)據(jù)庫(kù)底層存儲(chǔ)的核心就是基于這些數(shù)據(jù)模型的。每碰到一個(gè)新數(shù)據(jù)庫(kù)，我們需要先關(guān)注它的數(shù)據(jù)模型，這樣才能從理論上分析出這個(gè)數(shù)據(jù)庫(kù)的適用場(chǎng)景。
1. 哈希表模型。key-value。把值放在數(shù)組里，用一個(gè)哈希函數(shù)把 key 換算成一個(gè)確定的位置，然后把 value 放在數(shù)組的這個(gè)位置。當(dāng)多個(gè)key換算出的哈希值相同時(shí)，拉出一個(gè)鏈表，存儲(chǔ)對(duì)應(yīng)的value.
哈希表結(jié)構(gòu)適用于只有等值查詢(xún)的場(chǎng)景，比如 Memcached 及其他一些 NoSQL 引擎。
2. 有序數(shù)組模型。
查詢(xún)快，插入慢。適用于靜態(tài)存儲(chǔ)引擎。
3. 搜索樹(shù)
每個(gè)節(jié)點(diǎn)的左兒子小于父節(jié)點(diǎn)，父節(jié)點(diǎn)小于右兒子。查詢(xún)指定節(jié)點(diǎn)的時(shí)間復(fù)雜度是 O(log(N))，保持樹(shù)的平衡，插入節(jié)點(diǎn)的時(shí)間復(fù)雜度也是O(log(N))。
二叉樹(shù)搜索效率最高，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫(kù)存儲(chǔ)并不使用二叉樹(shù)，而使用N叉樹(shù)。因?yàn)樗饕恢勾嬖趦?nèi)存中，還要寫(xiě)到磁盤(pán)上，索引過(guò)多會(huì)導(dǎo)致占用大量的磁盤(pán)空間，且在磁盤(pán)上分多塊數(shù)據(jù)，當(dāng)程序進(jìn)行讀取時(shí)就要多次讀取磁盤(pán)的不同塊，時(shí)間效率大幅降低。
【InnoDB的索引模型】
舉例：R1~R5 的 (ID,k) 值分別為 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)。
根據(jù)葉子節(jié)點(diǎn)的內(nèi)容，索引類(lèi)型分為主鍵索引和非主鍵索引。
主鍵索引的葉子節(jié)點(diǎn)存的是整行數(shù)據(jù)。在 InnoDB 里，主鍵索引也被稱(chēng)為聚簇索引（clustered index）。
非主鍵索引的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值。在 InnoDB 里，非主鍵索引也被稱(chēng)為二級(jí)索引（secondary index）。
基于非主鍵索引的查詢(xún)需要多掃描一棵索引樹(shù)。因此，我們?cè)趹?yīng)用中應(yīng)該盡量使用主鍵查詢(xún)。
【索引維護(hù)】
插入數(shù)據(jù)時(shí)，為了保證順序性，可能需要調(diào)整節(jié)點(diǎn)的邏輯順序。當(dāng)某數(shù)據(jù)頁(yè)滿時(shí)，需要申請(qǐng)一個(gè)新的數(shù)據(jù)頁(yè)，挪動(dòng)部分?jǐn)?shù)據(jù)至新申請(qǐng)的數(shù)據(jù)頁(yè)中，即頁(yè)分裂；反之，如果刪除數(shù)據(jù)后，頁(yè)利用率很低，則需要進(jìn)行頁(yè)合并。頁(yè)分裂會(huì)降低數(shù)據(jù)頁(yè)的使用率，頁(yè)合并可以增加頁(yè)使用率但每頁(yè)容量有限。上述操作，都可能降低數(shù)據(jù)庫(kù)整體的性能。
我們可以設(shè)置自增主鍵：自增主鍵是指自增列上定義的主鍵，在建表語(yǔ)句中一般是這么定義的： NOT NULL PRIMARY KEY AUTO_INCREMENT。
自增主鍵的數(shù)據(jù)庫(kù)表，在插入數(shù)據(jù)時(shí)，可以避免調(diào)整其他數(shù)據(jù)，同時(shí)避免了頁(yè)分裂和頁(yè)合并。
主鍵長(zhǎng)度越小，普通索引的葉子節(jié)點(diǎn)就越小，普通索引占用的空間也就越小。所以一般情況下建議使用自增主鍵。
業(yè)務(wù)字段直接做主鍵的情景：1.只有一個(gè)索引，2.該索引在業(yè)務(wù)上必須是唯一索引
重建索引k：
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);
以上兩句可以用alter table T engine=InnoDB代替（（（（（這里暫時(shí)不太懂）））））
【覆蓋索引】
回到主鍵索引樹(shù)搜索的過(guò)程，我們稱(chēng)為回表。顯然，回表會(huì)在一定程度上降低查找的效率。
覆蓋索引，即一種使用索引來(lái)直接獲取列的數(shù)據(jù)方式。如果索引的葉子節(jié)點(diǎn)包含了要查詢(xún)的數(shù)據(jù)，那么就不用回表查詢(xún)了，也就是說(shuō)這種索引包含（亦稱(chēng)覆蓋）所有需要查詢(xún)的字段的值，我們稱(chēng)這種索引為覆蓋索引。
覆蓋索引可以減少樹(shù)的搜索次數(shù)，顯著提升查詢(xún)性能，所以使用覆蓋索引是一個(gè)常用的性能優(yōu)化手段。在建立冗余索引來(lái)支持覆蓋索引時(shí)就需要權(quán)衡考慮空間的代價(jià)和查詢(xún)時(shí)間的優(yōu)化。這正是業(yè)務(wù) DBA，或者稱(chēng)為業(yè)務(wù)數(shù)據(jù)架構(gòu)師的工作。
【最左前綴原則】
B+ 樹(shù)索引結(jié)構(gòu)，可以利用索引的“最左前綴”，來(lái)定位記錄。
在建立聯(lián)合索引的時(shí)候，如何安排索引內(nèi)的字段順序？這里我們的評(píng)估標(biāo)準(zhǔn)是，索引的復(fù)用能力。
第一原則——如果通過(guò)調(diào)整順序，可以少維護(hù)一個(gè)索引，那么這個(gè)順序往往就是需要優(yōu)先考慮采用的。
其次——空間。
【索引下推優(yōu)化】
MySQL 5.6 引入的索引下推優(yōu)化（index condition pushdown)， 可以在索引遍歷過(guò)程中，對(duì)索引中包含的字段先做判斷，直接過(guò)濾掉不滿足條件的記錄，減少回表次數(shù)。
