MySQL中索引指的是什么

這篇文章將為大家詳細(xì)講解有關(guān)MySQL中索引指的是什么，小編覺得挺實(shí)用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

索引是什么？

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

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

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

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

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

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

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

索引定義

數(shù)據(jù)庫索引，是數(shù)據(jù)庫管理系統(tǒng)（DBMS）中一個排序的數(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ù)。另外需要注意的是，主鍵索引是一種特殊的唯一索引，它還多了一個限制條件，要求鍵值不能為空。主鍵索引用 primay key 創(chuàng)建。

全文（Fulltext）：針對比較大的數(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ù)的高效檢索呢？

索引存儲模型推演

二分查找

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

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

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

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

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

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

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

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

二叉查找樹（ Binary Search Tree）

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

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

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

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

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

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

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

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

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

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

平衡二叉樹（AVL Tree）

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

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

這個時(shí)候我們再按順序插入 1、2、3、4、5、6，一定是這樣，不會變成一棵“斜樹”。

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

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

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

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

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

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

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

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

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

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

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

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)來存儲索引的時(shí)候，因?yàn)槟玫揭粔K數(shù)據(jù)就要在 Server 層比較是不是需要的數(shù)據(jù)，如果不是的話就要再讀一次磁盤。訪問一個節(jié)點(diǎn)就要跟磁盤之間發(fā)生一次 IO。InnoDB 操作磁盤的最小的單位是一頁（或者叫一個磁盤塊），大小是 16K(16384 字節(jié))。

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

所以如果每個節(jié)點(diǎn)存儲的數(shù)據(jù)太少，從索引中找到我們需要的數(shù)據(jù)，就要訪問更多的節(jié)點(diǎn)，意味著跟磁盤交互次數(shù)就會過多。

如果是機(jī)械硬盤時(shí)代，每次從磁盤讀取數(shù)據(jù)需要 10ms 左右的尋址時(shí)間，交互次數(shù)越多，消耗的時(shí)間就越多。

比如上面這張圖，我們一張表里面有 6 條數(shù)據(jù)，當(dāng)我們查詢 id=37 的時(shí)候，要查詢兩個子節(jié)點(diǎn)，就需要跟磁盤交互 3 次，如果我們有幾百萬的數(shù)據(jù)呢？這個時(shí)間更加難以估計(jì)。

所以我們的解決方案是什么呢？

第一個，就是讓每個節(jié)點(diǎn)存儲更多的數(shù)據(jù)。

第二個，節(jié)點(diǎn)上的關(guān)鍵字的數(shù)量越多，我們的指針數(shù)也越多，也就是意味著可以有更多的分叉。

因?yàn)榉植鏀?shù)越多，樹的深度就會減少（根節(jié)點(diǎn)是 0）。這樣，我們的樹是不是從原來的高瘦高瘦的樣子，變成了矮胖矮胖的樣子？

這個時(shí)候，我們的樹就不再是二叉了，而是多叉，或者叫做多路。

多路平衡查找樹（B Tree）

跟 AVL 樹一樣，B 樹在枝節(jié)點(diǎn)和葉子節(jié)點(diǎn)存儲鍵值、數(shù)據(jù)地址、節(jié)點(diǎn)引用。

它有一個特點(diǎn)：分叉數(shù)（路數(shù)）永遠(yuǎn)比關(guān)鍵字?jǐn)?shù)多 1。比如我們畫的這棵樹，每個節(jié)點(diǎn)存儲兩個關(guān)鍵字，那么就會有三個指針指向三個子節(jié)點(diǎn)。

B Tree 的查找規(guī)則是什么樣的呢？

比如我們要在這張表里面查找 15。 因?yàn)?15 小于 17，走左邊。 因?yàn)?15 大于 12，走右邊。 在磁盤塊 7 里面就找到了 15，只用了 3 次 IO。

這個是不是比 AVL 樹效率更高呢？ 那 B Tree 又是怎么實(shí)現(xiàn)一個節(jié)點(diǎn)存儲多個關(guān)鍵字，還保持平衡的呢？跟 AVL 樹有什么區(qū)別？

比如 Max Degree（路數(shù)）是 3 的時(shí)候，我們插入數(shù)據(jù) 1、2、3，在插入 3 的時(shí)候，本來應(yīng)該在第一個磁盤塊，但是如果一個節(jié)點(diǎn)有三個關(guān)鍵字的時(shí)候，意味著有 4 個指針， 子節(jié)點(diǎn)會變成 4 路，所以這個時(shí)候必須進(jìn)行分裂（其實(shí)就是 B+Tree）。把中間的數(shù)據(jù) 2 提上去，把 1 和 3 變成 2 的子節(jié)點(diǎn)。

如果刪除節(jié)點(diǎn)，會有相反的合并的操作。

注意這里是分裂和合并，跟 AVL 樹的左旋和右旋是不一樣的。

我們繼續(xù)插入 4 和 5，B Tree 又會出現(xiàn)分裂和合并的操作。

從這個里面我們也能看到，在更新索引的時(shí)候會有大量的索引的結(jié)構(gòu)的調(diào)整，所以解釋了為什么我們不要在頻繁更新的列上建索引，或者為什么不要更新主鍵。

節(jié)點(diǎn)的分裂和合并，其實(shí)就是 InnoDB 頁（page）的分裂和合并。

B+樹（加強(qiáng)版B Tree）

B Tree 的效率已經(jīng)很高了，為什么 MySQL 還要對 B Tree 進(jìn)行改良，最終使用了 B+Tree 呢？

總體上來說，這個 B 樹的改良版本解決的問題比 B Tree 更全面。

我們來看一下 InnoDB 里面的 B+樹的存儲結(jié)構(gòu)：

MySQL 中的 B+Tree 有幾個特點(diǎn)：

1. 它的關(guān)鍵字的數(shù)量是跟路數(shù)相等的；

2. B+Tree 的根節(jié)點(diǎn)和枝節(jié)點(diǎn)中都不會存儲數(shù)據(jù)，只有葉子節(jié)點(diǎn)才存儲數(shù)據(jù)。搜索到關(guān)鍵字不會直接返回，會到最后一層的葉子節(jié)點(diǎn)。比如我們搜索 id=28，雖然在第一層直接命中了，但是全部的數(shù)據(jù)在葉子節(jié)點(diǎn)上面，所以我還要繼續(xù)往下搜索，一直到葉子節(jié)點(diǎn)。

3. B+Tree 的每個葉子節(jié)點(diǎn)增加了一個指向相鄰葉子節(jié)點(diǎn)的指針，它的最后一個數(shù)據(jù)會指向下一個葉子節(jié)點(diǎn)的第一個數(shù)據(jù)，形成了一個有序鏈表的結(jié)構(gòu)。

4. 它是根據(jù)左閉右開的區(qū)間 [ )來檢索數(shù)據(jù)。

B+Tree 的數(shù)據(jù)搜尋過程：

1. 比如我們要查找 28，在根節(jié)點(diǎn)就找到了鍵值，但是因?yàn)樗皇琼撟庸?jié)點(diǎn)，所以會繼續(xù)往下搜尋，28 是[28,66)的左閉右開的區(qū)間的臨界值，所以會走中間的子節(jié)點(diǎn)，然后繼續(xù)搜索，它又是[28,34)的左閉右開的區(qū)間的臨界值，所以會走左邊的子節(jié)點(diǎn)，最后在葉子節(jié)點(diǎn)上找到了需要的數(shù)據(jù)。

2. 第二個，如果是范圍查詢，比如要查詢從 22 到 60 的數(shù)據(jù)，當(dāng)找到 22 之后，只需要順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有的數(shù)據(jù)節(jié)點(diǎn)，這樣就極大地提高了區(qū)間查詢效率（不需要返回上層父節(jié)點(diǎn)重復(fù)遍歷查找）。

InnoDB 中的 B+Tree 的特點(diǎn)：

1. 它是 B Tree 的變種，B Tree 能解決的問題，它都能解決。B Tree 解決的兩大問題是什么？（每個節(jié)點(diǎn)存儲更多關(guān)鍵字；路數(shù)更多） ；

2. 掃庫、掃表能力更強(qiáng)（如果我們要對表進(jìn)行全表掃描，只需要遍歷葉子節(jié)點(diǎn)就可以了，不需要遍歷整棵 B+Tree 拿到所有的數(shù)據(jù)） ；

3. B+Tree 的磁盤讀寫能力相對于 B Tree 來說更強(qiáng)（根節(jié)點(diǎn)和枝節(jié)點(diǎn)不保存數(shù)據(jù)區(qū)，所以一個節(jié)點(diǎn)可以保存更多的關(guān)鍵字，一次磁盤加載的關(guān)鍵字更多） ；

4. 排序能力更強(qiáng)（因?yàn)槿~子節(jié)點(diǎn)上有下一個數(shù)據(jù)區(qū)的指針，數(shù)據(jù)形成了鏈表） ；

5. 效率更加穩(wěn)定（B+Tree 永遠(yuǎn)是在葉子節(jié)點(diǎn)拿到數(shù)據(jù)，所以 IO 次數(shù)是穩(wěn)定的）。

關(guān)于“MySQL中索引指的是什么”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。