MySQL中為什么要使用索引

小編給大家分享一下MySQL中為什么要使用索引，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

索引是什么？

MySQL 官方對索引的定義為：索引是幫助 MySQL 高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

索引的出現(xiàn)就是為了提高查詢效率，就像書的目錄。其實說白了，索引要解決的就是查詢問題。

查詢，是數(shù)據(jù)庫所提供的一個重要功能，我們都想盡可能快的獲取到目標(biāo)數(shù)據(jù)，因此就需要優(yōu)化數(shù)據(jù)庫的查詢算法，選擇合適的查詢模型來實現(xiàn)索引。

另外，為表設(shè)置索引要付出代價的：一是增加了數(shù)據(jù)庫的存儲空間，二是在插入和修改數(shù)據(jù)時要花費較多的時間，因為索引也要隨之變動。

常見查詢模型

索引的實現(xiàn)模型有很多，這里我們先了解一下常用的查詢模型。

順序數(shù)組

順序數(shù)組是一種特殊的數(shù)組，里面的元素，按一定的順序排列。

順序數(shù)組在查詢上有著一定的優(yōu)勢，因為是有序的數(shù)據(jù)，采用二分查找的話，時間復(fù)雜度是 O(log(N))。

順序數(shù)組的優(yōu)點就是查詢效率非常高，但是要更新數(shù)據(jù)的話，就非常麻煩了。刪除和插入元素都要涉及到大量元素位置的移動，成本很高。

因此，對于順序數(shù)組更適合用于查詢的領(lǐng)域，適合存儲一些改動較小的靜態(tài)存儲引擎。

哈希索引

哈希表是一種以 鍵-值（key-value） 存儲數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的值即 key，就可以找到其對應(yīng)的值即 value。

哈希索引采用一定的哈希算法，對于每一行，存儲引擎計算出了被索引字段的哈希碼（Hash Code），把哈希碼保存在索引中，并且保存了一個指向哈希表中的每一行的指針。

這樣在檢索時只需一次哈希算法即可立刻定位到相應(yīng)的位置，速度非?？臁?/p>

Hash 索引結(jié)構(gòu)的特殊性，其檢索效率非常之高，應(yīng)該是 O(1) 的時間復(fù)雜度。

雖然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也帶來了很多限制和弊端，主要有以下這些：

1、Hash索引僅僅能滿足 =，IN 和 <=> 查詢，如果是范圍查詢檢索，這時候哈希索引就毫無用武之地了。

因為原先是有序的鍵值，經(jīng)過哈希算法后，有可能變成不連續(xù)的了，就沒辦法再利用索引完成范圍查詢檢索；

2、Hash 索引無法利用索引完成排序，因為存放的時候是經(jīng)過 Hash 計算過的，計算的 Hash 值和原始數(shù)據(jù)不一定相等，所以無法排序；

3、聯(lián)合索引中，Hash 索引不能利用部分索引鍵查詢。

Hash 索引在計算 Hash 值的時候是聯(lián)合索引鍵合并后再一起計算 Hash 值，而不是單獨計算 Hash 值。

所以對于聯(lián)合索引中的多個列，Hash 是要么全部使用，要么全部不使用。通過前面一個或幾個索引鍵進(jìn)行查詢的時候，Hash 索引也無法被利用。

4、Hash索引在任何時候都不能避免表掃描。

前面已經(jīng)知道，Hash 索引是將索引鍵通過 Hash 運(yùn)算之后，將 Hash 運(yùn)算結(jié)果的 Hash 值和所對應(yīng)的行指針信息存放于一個 Hash 表中，由于不同索引鍵可能存在相同 Hash 值，所以即使取滿足某個 Hash 鍵值的數(shù)據(jù)的記錄條數(shù)，也無法從 Hash 索引中直接完成查詢，還是要通過訪問表中的實際數(shù)據(jù)進(jìn)行相應(yīng)的比較，并得到相應(yīng)的結(jié)果。

5、在有大量重復(fù)鍵值情況下，哈希索引的效率也是極低的，因為存在所謂的哈希碰撞問題。

綜上，哈希表這種結(jié)構(gòu)適用于只有等值查詢的場景，比如 Memcached、redis 及其他一些 NoSQL 引擎。

二叉搜索樹索引

二叉搜索樹的每個節(jié)點都只存儲一個鍵值，并且左子樹（如果有）所有節(jié)點的值都要小于根節(jié)點的值，右子樹（如果有）所有節(jié)點的值都要大于根節(jié)點的值。

當(dāng)二叉搜索樹的所有非葉子節(jié)點的左右子樹的節(jié)點數(shù)目均保持差不多時（平衡），這時樹的搜索性能逼近二分查找；并且它比連續(xù)內(nèi)存空間的二分查找更有優(yōu)勢的是，改變樹結(jié)構(gòu)（插入與刪除結(jié)點）不需要移動大段的內(nèi)存數(shù)據(jù)，甚至通常是常數(shù)開銷。

特殊情況下，根節(jié)點的左右子樹的高度相差不超過 1 時，這樣的二叉樹被稱為平衡二叉樹；與之相對的是，二叉搜索樹有可能退化成線性樹。

下圖展示了一種可能的索引方式。左邊是數(shù)據(jù)表，一共有兩列七條記錄，最左邊的是數(shù)據(jù)記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的）。

為了加快 Col2 的查找，可以維護(hù)一個右邊所示的二叉查找樹，每個節(jié)點分別包含索引鍵值和一個指向?qū)?yīng)數(shù)據(jù)記錄物理地址的指針，這樣就可以運(yùn)用二叉查找在 O(log2n) 的復(fù)雜度內(nèi)獲取到相應(yīng)數(shù)據(jù)。

B樹

看得出來，二叉樹在查詢和修改上做到了一個平衡，都有著不錯的效率，但是現(xiàn)實是很少有數(shù)據(jù)庫引擎使用二叉樹來實現(xiàn)索引，為什么呢？

數(shù)據(jù)庫存儲大多不適用二叉樹，數(shù)據(jù)量較大時，樹高會過高。

你可以想象一下一棵 100 萬節(jié)點的平衡二叉樹，樹高 20，每個葉子結(jié)點就是一個塊，每個塊包含兩個數(shù)據(jù)，塊之間通過鏈?zhǔn)椒绞芥溄印?/p>

樹高 20 的話，就要遍歷 20 個塊才能得到目標(biāo)數(shù)據(jù)，索引存儲在磁盤時，這將是非常耗時的。

因此，為了減少磁盤的讀取，查詢時就要盡量少的遍歷數(shù)據(jù)塊，因此一般使用 N 叉樹。

這里就有了 B樹（Balanced Tree）。

究竟什么是 B 樹？

我們先看一個例子：

從上圖你能輕易的看到，一個內(nèi)結(jié)點 x 若含有 n[x] 個關(guān)鍵字，那么 x 將含有 n[x]+1 個子女。如含有 2 個關(guān)鍵字 D H 的內(nèi)結(jié)點有 3 個子女，而含有 3 個關(guān)鍵字 Q T X 的內(nèi)結(jié)點有 4 個子女。

B 樹的特性

普及一些概念：

節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度；
樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；
葉節(jié)點或終端節(jié)點：度為零的節(jié)點；
非終端節(jié)點或分支節(jié)點：度不為零的節(jié)點；

首先定義兩個變量：d 為大于 1 的一個正整數(shù)，稱為 B 樹的度。h 為一個正整數(shù)，稱為 B 樹的高度。

B 樹是滿足下列條件的數(shù)據(jù)結(jié)構(gòu)：

1、每個非葉子節(jié)點由 n-1 個 key 和 n 個指針組成，其中 d<=n<=2d。

2、每個葉子節(jié)點最少包含一個 key 和兩個指針，最多包含 2d-1 個 key 和 2d 個指針，葉節(jié)點的指針均為 null 。

3、除根結(jié)點和葉子結(jié)點外，其它每個結(jié)點至少有 [ceil(m / 2)] 個孩子（其中 ceil(x) 是一個取上限的函數(shù)）；

4、所有葉節(jié)點具有相同的深度，等于樹高 h，且葉子結(jié)點不包含任何關(guān)鍵字信息。

5、key 和指針互相間隔，節(jié)點兩端是指針。

6、一個節(jié)點中的 key 從左到右非遞減排列。

7、每個指針要么為 null，要么指向另外一個節(jié)點。

8、每個非終端結(jié)點中包含有 n 個關(guān)鍵字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。

其中：
a) Ki (i=1…n) 為關(guān)鍵字，且關(guān)鍵字按順序升序排序 K(i-1)< Ki。 
b) Pi 為指向子樹根的接點，且指針 P(i-1) 指向子樹種所有結(jié)點的關(guān)鍵字均小于 Ki，但都大于 K(i-1)。 
c) 關(guān)鍵字的個數(shù) n 必須滿足： [ceil(m / 2)-1]<= n <= m-1。

B 樹查找過程

由于 B 樹的特性，在 B 樹中按 key 檢索數(shù)據(jù)的算法非常直觀：首先從根節(jié)點進(jìn)行二分查找，如果找到則返回對應(yīng)節(jié)點的 data，否則對相應(yīng)區(qū)間的指針指向的節(jié)點遞歸進(jìn)行查找，直到找到節(jié)點或找到 null 指針，前者查找成功，后者查找失敗。

如上圖所示，我們來模擬下查找文件 29 的過程：

1、根據(jù)根結(jié)點指針找到文件目錄的根磁盤塊 1，將其中的信息導(dǎo)入內(nèi)存。【磁盤 IO 操作 1 次】

2、此時內(nèi)存中有兩個文件名 17、35 和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：17<29<35，因此我們找到指針 p2；

3、根據(jù) p2 指針，我們定位到磁盤塊 3，并將其中的信息導(dǎo)入內(nèi)存?！敬疟P IO 操作 20次】

4、此時內(nèi)存中有兩個文件名 26，30 和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：26<29<30，因此我們找到指針 p2；

5、根據(jù) p2 指針，我們定位到磁盤塊 8，并將其中的信息導(dǎo)入內(nèi)存。【磁盤 IO 操作 3 次】；

6、此時內(nèi)存中有兩個文件名 28，29。根據(jù)算法我們查找到文件名 29，并定位了該文件內(nèi)存的磁盤地址。

分析上面的過程，發(fā)現(xiàn)需要 3 次磁盤 IO 操作和 3 次內(nèi)存查找操作。關(guān)于內(nèi)存中的文件名查找，由于是一個有序表結(jié)構(gòu)，可以利用折半查找提高效率。

B+ 樹

B+ 樹：是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種 B 樹的變形樹。

一棵 m 階的 B+ 樹和 m 階的 B 樹的異同點在于：

1、每個節(jié)點的指針上限為 2d 而不是2d+1。

2、所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大的順序鏈接。（B 樹的葉子節(jié)點并沒有包括全部需要查找的信息）

3、所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹根結(jié)點中最大（或最小）關(guān)鍵字，不存儲 data。（B 樹的非終節(jié)點也包含需要查找的有效信息）

為什么說 B+ 樹比 B 樹更適合做數(shù)據(jù)庫索引？

1）B+ 樹的磁盤讀寫代價更低

B+ 樹的內(nèi)部結(jié)點并沒有存儲關(guān)鍵字具體信息。因此其內(nèi)部結(jié)點相對 B 樹更小。

如果把所有同一內(nèi)部結(jié)點的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對來說 IO 讀寫次數(shù)也就降低了。

2) B+ 樹的查詢效率更加穩(wěn)定

由于非終端結(jié)點并不是最終指向文件內(nèi)容的結(jié)點，而只是葉子結(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路。所有關(guān)鍵字查詢的路徑長度相同，進(jìn)而每一個數(shù)據(jù)的查詢效率相當(dāng)。

幾種樹的對比

以上，為了介紹索引內(nèi)容，我們花費了大量的篇幅介紹了幾種數(shù)據(jù)結(jié)構(gòu)模型，特別是樹的相關(guān)概念。

另外，涉及到樹的添加和刪除元素，操作更加復(fù)雜，本文篇幅有限（其實是小編也搞不太明白），這里就不再展開。

有興趣的，強(qiáng)烈建議鉆研下參考鏈接里的內(nèi)容。

好了，下面我們來看 MySQL 中的 InnoDB 引擎的索引是如何實現(xiàn)的。

MySQL 的索引模型

說了這么多，終于到索引出場了。

索引就是這種神奇?zhèn)ゴ蟮拇嬖?。索引相?dāng)于數(shù)據(jù)庫的表數(shù)據(jù)之外新建的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)段中存儲著字段的值以及指向?qū)嶋H數(shù)據(jù)記錄的指針。

數(shù)據(jù)庫表的索引從數(shù)據(jù)存儲方式上可以分為聚簇索引和非聚簇索引（又叫二級索引）兩種。

1、聚簇索引

表數(shù)據(jù)按照索引的順序來存儲的，也就是說索引項的順序與表中記錄的物理順序一致。

對于聚簇索引，葉子結(jié)點即存儲了真實的數(shù)據(jù)行，不再有另外單獨的數(shù)據(jù)頁。 在一張表上最多只能創(chuàng)建一個聚集索引，因為真實數(shù)據(jù)的物理順序只能有一種。

聚簇集是指實際的數(shù)據(jù)行和相關(guān)的鍵值都保存在一起。

注意：數(shù)據(jù)的物理存放順序與索引順序是一致的，即：只要索引是相鄰的，那么對應(yīng)的數(shù)據(jù)一定也是相鄰地存放在磁盤上的。

如果主鍵不是自增 id，那么可以想象，它會干些什么，不斷地調(diào)整數(shù)據(jù)的物理地址、分頁。如果是自增的，那就簡單了，它只需要一頁一頁地寫，索引結(jié)構(gòu)相對緊湊，磁盤碎片少，效率也高。

聚簇索引的二級索引：葉子節(jié)點不會保存引用的行的物理位置,而是保存了行的主鍵值

2、非聚集索引

表數(shù)據(jù)存儲順序與索引順序無關(guān)。對于非聚集索引，葉結(jié)點包含索引字段值及指向數(shù)據(jù)頁數(shù)據(jù)行的邏輯指針，其行數(shù)量與數(shù)據(jù)表行數(shù)據(jù)量一致。

聚簇索引是對磁盤上實際數(shù)據(jù)重新組織以按指定的一個或多個列的值排序的算法。特點是存儲數(shù)據(jù)的順序和索引順序一致。一般情況下主鍵會默認(rèn)創(chuàng)建聚簇索引，且一張表只允許存在一個聚簇索引。

這兩個名字雖然都叫做索引，但這并不是一種單獨的索引類型，而是一種數(shù)據(jù)存儲方式。

下面，我們可以看一下 MYSQL 中 MyISAM 和 InnoDB 兩種引擎的索引結(jié)構(gòu)。

MyISAM索引實現(xiàn)

MyISAM 引擎使用 B+ 樹作為索引結(jié)構(gòu)，葉節(jié)點的 data 域存放的是數(shù)據(jù)記錄的地址，就是非聚集索引。

下圖是 MyISAM 索引的原理圖：

InnoDB索引實現(xiàn)

雖然 InnoDB 也使用 B+ 樹作為索引結(jié)構(gòu)，但具體實現(xiàn)方式卻與 MyISAM 截然不同。

第一個重大區(qū)別是 InnoDB 的數(shù)據(jù)文件本身就是索引文件。

在 InnoDB 中，表數(shù)據(jù)文件本身就是按 B+ 樹組織的一個索引結(jié)構(gòu)，這棵樹的葉節(jié)點 data 域保存了完整的數(shù)據(jù)記錄。這個索引的 key 是數(shù)據(jù)表的主鍵，因此 InnoDB 表數(shù)據(jù)文件本身就是主索引。

另外，第二個與 MyISAM 索引的不同是 InnoDB 的輔助索引 data 域存儲相應(yīng)記錄主鍵的值而不是地址。

對于聚簇索引存儲來說，行數(shù)據(jù)和主鍵 B+ 樹存儲在一起，輔助索引只存儲輔助鍵和主鍵，主鍵和非主鍵 B+ 樹幾乎是兩種類型的樹。

對于非聚簇索引存儲來說，主鍵 B+ 樹在葉子節(jié)點存儲指向真正數(shù)據(jù)行的指針，而非主鍵。

為了更形象說明這兩種索引的區(qū)別，我們假想一個表如下圖存儲了 4 行數(shù)據(jù)。其中 Id 作為主索引，Name 作為輔助索引。圖示清晰的顯示了聚簇索引和非聚簇索引的差異。

若使用輔助索引進(jìn)行查詢，對 Name 列進(jìn)行條件搜索，則需要兩個步驟：

1、第一步在輔助索引 B+ 樹中檢索 Name，到達(dá)其葉子節(jié)點獲取對應(yīng)的主鍵。
2、第二步根據(jù)主鍵在主索引 B+ 樹種再執(zhí)行一次 B+ 樹檢索操作，最終到達(dá)葉子節(jié)點即可獲取整行數(shù)據(jù)。這個過程稱為回表。

聚簇索引的優(yōu)勢在哪？

1、由于行數(shù)據(jù)和葉子節(jié)點存儲在一起，這樣主鍵和行數(shù)據(jù)是一起被載入內(nèi)存的，找到葉子節(jié)點就可以立刻將行數(shù)據(jù)返回了，如果按照主鍵 Id 來組織數(shù)據(jù)，獲得數(shù)據(jù)更快。

2、輔助索引使用主鍵作為指針而不是使用地址值作為指針的好處是，減少了當(dāng)出現(xiàn)行移動或者數(shù)據(jù)頁分裂時輔助索引的維護(hù)工作。

使用主鍵值當(dāng)作指針會讓輔助索引占用更多的空間，換來的好處是 InnoDB 在移動行時無須更新輔助索引中的這個指針。

也就是說行的位置會隨著數(shù)據(jù)庫里數(shù)據(jù)的修改而發(fā)生變化，使用聚簇索引就可以保證不管這個主鍵 B+ 樹的節(jié)點如何變化，輔助索引樹都不受影響。

以上是“MySQL中為什么要使用索引”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！