下面mysql教程欄目帶大家深入剖析下MySQL中的索引，介紹一下MySQL索引的一些知識(shí)，希望對(duì)大家有所幫助！

MySQL 數(shù)據(jù)庫應(yīng)該是最常用的數(shù)據(jù)庫之一，在各種大大小小的公司都可以看到它的身影，你對(duì) MySQL 數(shù)據(jù)庫掌握的如何呢？想要更好的使用它，那么我們就必須先了解它，正所謂的工欲善其事，必先利其器。

本篇文章就帶領(lǐng)大家一起來深入剖析MySQL索引的一些知識(shí)，先來了解什么是索引，以及索引存儲(chǔ)模型的推演，底層數(shù)據(jù)結(jié)構(gòu)為什么會(huì)選擇B+樹其緣由？

索引是什么？

一張表有 500 萬條數(shù)據(jù)，在沒有索引的 name 字段上執(zhí)行一條 where 查詢：

select * from user_innodb where name ='小馬';

如果 name 字段上面有索引呢？在 name 字段上面創(chuàng)建一個(gè)索引，再來執(zhí)行一下相同的查詢。

ALTER TABLE user_innodb DROP INDEX idx_name;  ALTER TABLE user_innodb ADD INDEX idx_name (name);

有索引的查詢和沒有索引的查詢相比，效率相差幾十倍。

通過這個(gè)案例大家應(yīng)該可以非常直觀地感受到，索引對(duì)于數(shù)據(jù)檢索的性能改善是非常大的。

那么索引到底是什么呢？為什么可以對(duì)我們的查詢產(chǎn)生這么大的影響？創(chuàng)建索引的時(shí)候發(fā)生了什么事情？

索引定義

數(shù)據(jù)庫索引，是數(shù)據(jù)庫管理系統(tǒng)（DBMS）中一個(gè)排序的數(shù)據(jù)結(jié)構(gòu)，以協(xié)助快速查詢、更新數(shù)據(jù)庫表中數(shù)據(jù)。

數(shù)據(jù)是以文件的形式存放在磁盤上面的，每一行數(shù)據(jù)都有它的磁盤地址。如果沒有索引的話，我們要從 500 萬行數(shù)據(jù)里面檢索一條數(shù)據(jù)，只能依次遍歷這張表的全部數(shù)據(jù)，直到找到這條數(shù)據(jù)。

但是我們有了索引之后，只需要在索引里面去檢索這條數(shù)據(jù)就行了，因?yàn)樗且环N特殊的專門用來快速檢索的數(shù)據(jù)結(jié)構(gòu)，我們找到數(shù)據(jù)存放的磁盤地址以后，就可以拿到數(shù)據(jù)了。

索引類型

在 InnoDB 里面，索引類型有三種：普通索引、唯一索引（主鍵索引是特殊的唯一索引）、全文索引。

普通（Normal）：也叫非唯一索引，是最普通的索引，沒有任何的限制。

唯一（Unique）：唯一索引要求鍵值不能重復(fù)。另外需要注意的是，主鍵索引是一種特殊的唯一索引，它還多了一個(gè)限制條件，要求鍵值不能為空。主鍵索引用 primay key 創(chuàng)建。

全文（Fulltext）：針對(duì)比較大的數(shù)據(jù)，比如我們存放的是消息內(nèi)容，有幾 KB 的數(shù)據(jù)的這種情況，如果要解決 like 查詢效率低的問題，可以創(chuàng)建全文索引。只有文本類型的字段才可以創(chuàng)建全文索引，比如 char、varchar、text。

索引是一種數(shù)據(jù)結(jié)構(gòu)，那么它到底應(yīng)該選擇一種什么數(shù)據(jù)結(jié)構(gòu)，才能實(shí)現(xiàn)數(shù)據(jù)的高效檢索呢？

索引存儲(chǔ)模型推演

二分查找

雙十一過去之后，你女朋友跟你玩了一個(gè)猜數(shù)字的游戲。 猜猜我昨天買了多少錢，給你五次機(jī)會(huì)。

10000？低了。30000？高了。接下來你會(huì)猜多少？ 20000。為什么你不猜 11000，也不猜 29000 呢？

這個(gè)就是二分查找的一種思想，也叫折半查找，每一次，我們都把候選數(shù)據(jù)縮小了 一半。如果數(shù)據(jù)已經(jīng)排過序的話，這種方式效率比較高。

所以第一個(gè)，我們可以考慮用有序數(shù)組作為索引的數(shù)據(jù)結(jié)構(gòu)。

有序數(shù)組的等值查詢和比較查詢效率非常高，但是更新數(shù)據(jù)的時(shí)候會(huì)出現(xiàn)一個(gè)問題，可能要挪動(dòng)大量的數(shù)據(jù)（改變 index），所以只適合存儲(chǔ)靜態(tài)的數(shù)據(jù)。

為了支持頻繁的修改，比如插入數(shù)據(jù)，我們需要采用鏈表。鏈表的話，如果是單鏈表，它的查找效率還是不夠高。

所以，有沒有可以使用二分查找的鏈表呢？

為了解決這個(gè)問題，BST（Binary [?ba?n?ri] Search Tree）也就是我們所說的二叉查找樹誕生了。

二叉查找樹（ Binary Search Tree）

左子樹所有的節(jié)點(diǎn)都小于父節(jié)點(diǎn)，右子樹所有的節(jié)點(diǎn)都大于父節(jié)點(diǎn)。投影到平面以后，就是一個(gè)有序的線性表。

二叉查找樹既能夠?qū)崿F(xiàn)快速查找，又能夠?qū)崿F(xiàn)快速插入。

但是二叉查找樹有一個(gè)問題：查找耗時(shí)是和這棵樹的深度相關(guān)的，在最壞的情況下時(shí)間復(fù)雜度會(huì)退化成 O(n)。

什么情況是最壞的情況呢？

還是剛才的這一批數(shù)字，如果我們插入的數(shù)據(jù)剛好是有序的，2、10、12、15、 21、28

這個(gè)時(shí)候 BST 會(huì)變成鏈表（ “斜樹”），這種情況下不能達(dá)到加快檢索速度的目的，和順序查找效率是沒有區(qū)別的。

造成它傾斜的原因是什么呢？

因?yàn)樽笥易訕渖疃炔钐螅@棵樹的左子樹根本沒有節(jié)點(diǎn)——也就是它不夠平衡。

所以，我們有沒有左右子樹深度相差不是那么大，更加平衡的樹呢？

這個(gè)就是平衡二叉樹，叫做 Balanced binary search trees，或者 AVL 樹。

平衡二叉樹（AVL Tree）

平衡二叉樹的定義：左右子樹深度差絕對(duì)值不能超過 1。

是什么意思呢？比如左子樹的深度是 2，右子樹的深度只能是 1 或者 3。

這個(gè)時(shí)候我們?cè)侔错樞虿迦?1、2、3、4、5、6，一定是這樣，不會(huì)變成一棵“斜樹”。

那 AVL 樹的平衡是怎么做到的呢？怎么保證左右子樹的深度差不能超過 1 呢？ 例如：插入 1、2、3。

當(dāng)我們插入了 1、2 之后，如果按照二叉查找樹的定義，3 肯定是要在 2 的右邊的，這個(gè)時(shí)候根節(jié)點(diǎn) 1 的右節(jié)點(diǎn)深度會(huì)變成 2，但是左節(jié)點(diǎn)的深度是 0，因?yàn)樗鼪]有子節(jié)點(diǎn)，所以就會(huì)違反平衡二叉樹的定義。

那應(yīng)該怎么辦呢？因?yàn)樗怯夜?jié)點(diǎn)下面接一個(gè)右節(jié)點(diǎn)，右-右型，所以這個(gè)時(shí)候我們要把 2 提上去，這個(gè)操作叫做左旋。

同樣的，如果我們插入 7、6、5，這個(gè)時(shí)候會(huì)變成左左型，就會(huì)發(fā)生右旋操作，把 6 提上去。

所以為了保持平衡，AVL 樹在插入和更新數(shù)據(jù)的時(shí)候執(zhí)行了一系列的計(jì)算和調(diào)整的操作。

平衡的問題我們解決了，那么平衡二叉樹作為索引怎么查詢數(shù)據(jù)？ 在平衡二叉樹中，一個(gè)節(jié)點(diǎn)，它的大小是一個(gè)固定的單位，作為索引應(yīng)該存儲(chǔ)什么內(nèi)容？

第一個(gè)：索引的鍵值。比如我們?cè)?id 上面創(chuàng)建了一個(gè)索引，我在用 where id =1 的條件查詢的時(shí)候就會(huì)找到索引里面的 id 的這個(gè)鍵值。

第二個(gè)：數(shù)據(jù)的磁盤地址，因?yàn)樗饕淖饔镁褪侨ゲ檎覕?shù)據(jù)的存放的地址。

第三個(gè)因?yàn)槭嵌鏄?，它必須還要有左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的引用，這樣我們才能找到下一個(gè)節(jié)點(diǎn)。比如大于 26 的時(shí)候，走右邊，到下一個(gè)樹的節(jié)點(diǎn)，繼續(xù)判斷。

如果是這樣存儲(chǔ)數(shù)據(jù)的話，我們來看一下會(huì)有什么問題。

首先，索引的數(shù)據(jù)，是放在硬盤上的。查看數(shù)據(jù)和索引的大小：

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len,  CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len  from information_schema.TABLES  where table_schema='gupao' and table_name='user_innodb';

當(dāng)我們用樹的結(jié)構(gòu)來存儲(chǔ)索引的時(shí)候，因?yàn)槟玫揭粔K數(shù)據(jù)就要在 Server 層比較是不是需要的數(shù)據(jù)，如果不是的話就要再讀一次磁盤。訪問一個(gè)節(jié)點(diǎn)就要跟磁盤之間發(fā)生一次 IO。InnoDB 操作磁盤的最小的單位是一頁（或者叫一個(gè)磁盤塊），大小是 16K(16384 字節(jié))。

那么，一個(gè)樹的節(jié)點(diǎn)就是 16K 的大小。 如果我們一個(gè)節(jié)點(diǎn)只存一個(gè)鍵值+數(shù)據(jù)+引用，例如整形的字段，可能只用了十幾個(gè)或者幾十個(gè)字節(jié)，它遠(yuǎn)遠(yuǎn)達(dá)不到 16K 的容量，所以訪問一個(gè)樹節(jié)點(diǎn)，進(jìn)行一次 IO 的時(shí)候，浪費(fèi)了大量的空間。

所以如果每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)太少，從索引中找到我們需要的數(shù)據(jù)，就要訪問