MySQL索引常見的模型及優(yōu)缺點總結(jié)

什么是索引蘑辑？索引又是用來干什么的骡显？

一句話概括就是：索引就是為了調(diào)高數(shù)據(jù)的查詢效率

就像書的目錄一樣星爪，如果你想找到某個知識點浆西，通常我們都是翻看書的目錄。同樣顽腾，索引其實就是數(shù)據(jù)庫表的“目錄”近零。

索引的常見模型

實現(xiàn)索引的數(shù)據(jù)結(jié)構(gòu)有很多，最常見的也是比較簡單的數(shù)據(jù)結(jié)構(gòu)有哈希表抄肖，有序數(shù)組和搜索樹久信。

哈希表

哈希表是一種以鍵-值（key-value）形式存儲數(shù)據(jù)的結(jié)構(gòu)，我們只需要輸入查找的鍵key漓摩，就可以得到對應(yīng)的值value裙士。哈希的思路是，把值放在數(shù)組里管毙，用一個哈希函數(shù)把key換成一個確定的位置腿椎，然后把value放在數(shù)組的這個位置。

但是會有一種情況锅风，就是多個不同的key有可能通過哈希函數(shù)的換算得到相同的位置，解決這種情況就是在這個位置拉出一個鏈表鞍泉。

假如我們有一張用戶表皱埠，用戶昵稱（nickname）字段使用的是哈希索引，我們需要根據(jù)昵稱查詢用戶信息咖驮，這時哈希索引的示意圖如下所示：

哈希表

示意圖中边器，user3和user4根據(jù)nickname字段算出來的位置都是4，所以在4位置用了一個鏈表表示托修，當(dāng)我們在查詢的時候忘巧，比如我們根據(jù)nickname4查詢，查詢步驟就是：先使用哈希函數(shù)計算nickname3得到4睦刃，然后遍歷鏈表直到找到user4砚嘴。

優(yōu)點：因為哈希索引是根據(jù)索引字段計算位置，所以它的插入和根據(jù)key的查找會很快。

缺點：因為哈希索引是計算位置际长，而這個位置不一定是遞增的耸采，所以使用哈希索引做范圍查詢速度會很慢。如果要根據(jù)范圍查找數(shù)據(jù)工育，就必須全部掃描一遍索引才能找到虾宇。

適合場景：哈希表適用于等值查詢的場景，比如Redis或者其他的NoSQL數(shù)據(jù)庫如绸。

有序數(shù)組

還是上面的例子嘱朽，如果是使用有序數(shù)組索引的話，示意圖如下：

有序數(shù)組

這個數(shù)組是根據(jù)nickname遞增順序保存的怔接，如果我們要查nickname2對應(yīng)的用戶信息搪泳，用二分查找就可以很快找到對應(yīng)的結(jié)果，時間復(fù)雜度為O(log(N))蜕提。

當(dāng)然這個數(shù)據(jù)結(jié)構(gòu)也是支持范圍查詢的森书，如果我們想要查到[nicknameX,nicknameY]這個區(qū)間的用戶信息，我們只需要根據(jù)二分查找找到第一個nicknameX谎势，然后向右遍歷數(shù)組凛膏，找到找到最后一個nicknameY的用戶即可。

優(yōu)點：有序數(shù)組因為存入的數(shù)據(jù)已經(jīng)是排好序的脏榆，所以根據(jù)等值查到和范圍查到都比較快猖毫。

缺點：如果我們需要往數(shù)組中間插入一個值或者刪除中間的某個值，那就需要挪動這個值所在位置后面的所有元素须喂，成本比較高吁断。

適合場景：有序數(shù)組適用于靜態(tài)存儲引擎，存儲不會再修改的數(shù)據(jù)坞生，比如某個城市過去的人口數(shù)仔役。

二叉搜索樹

還是上面的例子，如果是二叉搜索樹的話是己，示意圖如下：

二叉搜索樹

二叉樹特點：每個節(jié)點的左兒子小于父節(jié)點又兵，父節(jié)點小于右兒子。如果我們要查user2的話卒废，跟著上圖我們的查詢路徑就是：userA -> userB -> userD -> user2沛厨。時間復(fù)雜度為O(log(N))。

優(yōu)點：查詢效率高

缺點：因為索引不止存在于內(nèi)存中摔认，也要寫到磁盤里逆皮。如果一個二叉樹高度為20，我們查詢某個用戶信息就要訪問20次磁盤参袱，這個效率是非常低的电谣。

適用場景：二叉樹適用于表數(shù)據(jù)比較少的引擎秽梅。

為了減少樹的高度，也就是減少對磁盤的訪問辰企，數(shù)據(jù)庫索引就不能用二叉樹风纠。那么既然有二叉數(shù)，那就有N叉樹牢贸，這里的N取決于數(shù)據(jù)塊的大小竹观。

在MySQL中，索引是在存儲引擎層實現(xiàn)的潜索，不同存儲引擎的索引使用的數(shù)據(jù)結(jié)構(gòu)可能都不一樣臭增。InnoDB的索引使用的數(shù)據(jù)結(jié)構(gòu)為B+樹。

InnoDB的索引模型

在InnoDB中竹习，表都是根據(jù)主鍵順序以索引的i形式存放的誊抛，這種存儲方式的表稱為索引組織表。每一個索引在InndDB中都對應(yīng)一棵B+樹整陌。

假如我們有下面一張表：

create table T(
   id int primary key, 
   k int not null, 
   index (k)
)engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分別為 (100,1)拗窃、(200,2)、(300,3)泌辫、(500,5) 和 (600,6)随夸，兩棵樹的示例示意圖如下：

B+樹

從圖中可以看出，根據(jù)葉子節(jié)點的數(shù)據(jù)震放，索引類型分為主鍵索引和非主鍵索引宾毒。

主鍵索引和非主鍵索引的區(qū)別：

主鍵索引的葉子節(jié)點存的是整行數(shù)據(jù)，在InnoDB里殿遂，主鍵索引也叫做聚簇索引诈铛；非主鍵索引的葉子節(jié)點存的內(nèi)容是主鍵的值，在InnoDB里墨礁，非主鍵索引也叫做二級索引幢竹。
如果根據(jù)主鍵查詢，則只需要查找id索引樹即可恩静；如果根據(jù)非主鍵索引查找（查找的數(shù)據(jù)不只有主鍵）焕毫，則需要查找k索引樹找到對應(yīng)的主鍵，然后根據(jù)主鍵到id索引在查找一次蜕企。這個過程叫回表咬荷。

結(jié)束冠句！