一、什么是索引
索引是對數(shù)據(jù)庫表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)，使用索引可以快速訪問數(shù)據(jù)庫表中的特定信息。
索引的主要目的就是加快檢索表中數(shù)據(jù)葵擎，是一種輔助查詢的數(shù)據(jù)結(jié)構(gòu)。
二半哟、索引的模型酬滤、實(shí)現(xiàn)方式
可以用于提高讀寫效率的數(shù)據(jù)結(jié)構(gòu)比較多，三種常見的數(shù)據(jù)結(jié)構(gòu)：哈希表寓涨、有序數(shù)組盯串、搜索樹。
哈希表
以鍵值對存儲數(shù)據(jù)的結(jié)構(gòu)戒良√迥螅可直接根據(jù)待查找的鍵key，就可以找到其對應(yīng)的值value蔬墩。
哈希實(shí)現(xiàn)思路 將值存儲在數(shù)組中译打，通過一個哈希函數(shù)把key計算成數(shù)組的一個確定的位置，然后把value放在該位置中拇颅，即存儲位置=f(key)奏司，f 為哈希函數(shù)。
哈希沖突 也稱為 哈希碰撞 指若是多個key經(jīng)過哈希函數(shù)計算得到同一個值(地址)樟插。
哈希沖突解決方案 主要有:
- 開放定址法——發(fā)生沖突時韵洋，繼續(xù)尋找下一塊未被占用的存儲地址竿刁。
- 再散列函數(shù)法。
- 鏈地址法搪缨。HashMap即是采用的此方法食拜，即 數(shù)組+鏈表 （單鏈表）的方式。
適用場景 哈希表適用于只有等值查詢的場景副编，對于區(qū)間查詢需要全部掃描负甸。
有序數(shù)組
適用場景 有序數(shù)組在等值查詢和范圍查詢場景中的性能都非常的優(yōu)秀，但 有序數(shù)組索引只適用于靜態(tài)存儲引擎 痹届，因?yàn)楦虏僮鲿赡軙婕暗揭苿雍竺娴乃袛?shù)據(jù)記錄呻待，成本太高。
搜索樹
二叉搜索樹 也可以用來做索引的數(shù)據(jù)模型队腐，查詢的時間復(fù)雜度為O(log(N))蚕捉，為了維持這個查詢復(fù)雜度，則需要保持這顆樹是 平衡二叉樹 柴淘，為了這個保證迫淹，更新的時間復(fù)雜度也是O(log(N))。
二叉搜索樹 是搜索效率最高的为严，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫存儲卻并不適用二叉樹敛熬，原因是：索引不止存在內(nèi)存中，還要寫到磁盤上梗脾。
為了讓一個查詢盡量少讀磁盤荸型，就必須讓查詢過程訪問盡量少的數(shù)據(jù)塊，這樣的話應(yīng)該適用 N叉樹 炸茧，而不是 二叉樹 瑞妇。 N叉樹 由于在讀寫性能上的優(yōu)點(diǎn)，以及適配磁盤的訪問模式梭冠，被廣泛應(yīng)用在數(shù)據(jù)庫引擎中了辕狰。
三、InnoDB 的索引模型
在MySQL中控漠，索引是在引擎層實(shí)現(xiàn)的蔓倍，所以并沒有統(tǒng)一的索引標(biāo)準(zhǔn)，即不同的存儲引擎的索引的工作方式不一樣盐捷。
索引組織表 在InnoDB中偶翅，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表碉渡。
InnoDB使用了 B+樹索引模型 聚谁，所以數(shù)據(jù)都是存儲在 B+樹 中的，每一個索引在InnoDB里面對應(yīng)一顆 B+樹 滞诺。
索引類型
主要分為：主鍵索引形导、非主鍵索引(唯一索引环疼、普通索引)。
主鍵索引 的葉子節(jié)點(diǎn)保存整行數(shù)據(jù)朵耕。在InnoDB中炫隶，也被稱為 聚簇索引 (clustered index)。
非主鍵索引 的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值阎曹。在InnoDB中伪阶，也被稱為 二級索引 (secondary index)。
主鍵索引與普通索引查詢區(qū)別
主鍵索引查詢芬膝，只需要搜索主鍵索引這顆B+Tree望门。
而普通索引查詢形娇，則要先搜索普通索引樹锰霜，得到主鍵列的值，再到主鍵索引樹搜索一次桐早，這個過程被稱為
回表癣缅。
綜上，基于非主鍵索引的查詢需要多掃描一個索引樹哄酝，因此在使用中應(yīng)盡量使用主鍵查詢友存。
InnoDB索引組織結(jié)構(gòu)示意圖如下，其中ID為表主鍵陶衅，k為非主鍵索引列屡立。
四、索引維護(hù)
B+樹為了維護(hù)索引有序性搀军，在插入新值的時候需要做必要的維護(hù)膨俐。
頁分裂 若是往數(shù)據(jù)中間插入新的數(shù)據(jù)，而對應(yīng)的數(shù)據(jù)頁已滿罩句，根據(jù)B+樹算法焚刺，此時需要申請一個新的數(shù)據(jù)頁，然后挪動部分?jǐn)?shù)據(jù)過去门烂，此過程稱為 頁分裂 乳愉。
頁分裂影響：
- 導(dǎo)致性能下降；
- 影響數(shù)據(jù)頁的利用率屯远，原本可放在一個頁的數(shù)據(jù)被分到兩個頁中蔓姚，整體空間利用率降低約50%。
頁合并 相鄰兩個頁由于數(shù)據(jù)刪除慨丐，利用率很低之后坡脐，會將數(shù)據(jù)頁做合并，合并的過程稱為 頁合并 咖气。
自增主鍵的適用場景
哪些場景下應(yīng)該使用自增主鍵挨措，哪些場景下使用業(yè)務(wù)字段做主鍵挖滤？(ps：業(yè)務(wù)字段做主鍵需保證唯一性)
從 性能 上考慮，自增主鍵模式浅役，符合遞增插入場景斩松，都是追加操作，不涉及數(shù)據(jù)挪動觉既，也不會觸發(fā)葉子節(jié)點(diǎn)的分裂惧盹； 而業(yè)務(wù)字段做主鍵的模式，不容易保證有序插入瞪讼，寫數(shù)據(jù)成本相對較高钧椰。
從 存儲空間 上考慮，由于每個非主鍵索引的葉子節(jié)點(diǎn)上都是主鍵的值符欠，主鍵長度越小嫡霞，普通索引的葉子節(jié)點(diǎn)就越小，普通索引占用的空間也越小希柿。因此在選擇上诊沪，要考慮 業(yè)務(wù)字段 與 自增主鍵字段 本身的長度。
綜上曾撤，從性能和存儲空間方面考量端姚，自增主鍵往往是更合理的選擇。
業(yè)務(wù)字段直接做主鍵的場景
- 只有一個索引挤悉；
- 該索引必須是唯一索引渐裸。
即在沒有其他索引時，也就不用考慮其他索引的葉子節(jié)點(diǎn)大小的問題了装悲。
五昏鹃、小結(jié)
參考資料:
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！
