MySQL中什麼是索引？索引存儲模型淺析

下面mysql教學專欄帶大家深入剖析下MySQL中的索引，介紹一下MySQL索引的一些知識，希望對大家有幫助！

MySQL 資料庫應該是最常用的資料庫之一，在各種大大小小的公司都可以看到它的身影，你對MySQL 資料庫掌握的如何呢？想要更好的使用它，那麼我們就必須先了解它，正所謂的工欲善其事，必先利其器。

這篇文章就帶領大家一起來深入剖析MySQL索引的一些知識，先來了解什麼是索引，以及索引儲存模型的推演，底層資料結構為什麼會選擇B 樹其緣由？

索引是什麼？

一張表有 500 萬條數據，在沒有索引的 name 欄位上執行 where 查詢：

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

如果 name 欄位上面有索引呢？在 name 欄位上面建立一個索引，再來執行相同的查詢。

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

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

透過這個案例大家應該可以非常直觀地感受到，索引對於資料檢索的效能改善是非常大的。

那麼索引到底是什麼呢？為什麼可以對我們的查詢產生這麼大的影響？創建索引的時候發生了什麼事？

索引定義

資料庫索引，是資料庫管理系統（DBMS）中一個排序的資料結構，以協助快速查詢、更新資料庫表中數據。

資料是以檔案的形式存放在磁碟上面的，每一行資料都有它的磁碟位址。如果沒有索引的話，我們要從 500 萬行數據裡面檢索一條數據，只能依次遍歷這張表的全部數據，直到找到這條數據。

但是我們有了索引之後，只需要在索引裡面去檢索這條資料就行了，因為它是一種特殊的專門用來快速檢索的資料結構，我們找到資料存放的磁碟位址以後，就可以拿到數據了。

索引類型

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

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

唯一（Unique）：唯一索引要求鍵值不能重複。另外要注意的是，主鍵索引是一種特殊的唯一索引，它還多了一個限制條件，要求鍵值不能為空。主鍵索引用 primay key 建立。

全文（Fulltext）：針對比較大的數據，例如我們存放的是訊息內容，有幾KB 的數據的這種情況，如果要解決like 查詢效率低的問題，可以建立全文索引。只有文字類型的欄位可以建立全文索引，例如 char、varchar、text。

索引是一種資料結構，那麼它到底應該選擇什麼資料結構，才能實現資料的高效檢索呢？

索引儲存模型推演

二分查找

#雙十一過去之後，你女朋友跟你玩了一個猜數字的遊戲。猜猜我昨天買了多少錢，給你五次機會。

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

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

所以第一個，我們可以考慮用有序數組作為索引的資料結構。

有序數組的等值查詢和比較查詢效率非常高，但是更新資料的時候會出現一個問題，可能要挪動大量的資料（改變 index），所以只適合儲存靜態的資料。

為了支援頻繁的修改，例如插入數據，我們需要採用鍊錶。鍊錶的話，如果是單鍊錶，它的查找效率還是不夠高。

所以，有沒有可以使用二分來尋找的鍊錶呢？

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

二元查找樹（ Binary Search Tree）

左子樹所有的節點都小於父節點，右子樹所有的節點都大於父節點。投影到平面以後，就是一個有序的線性表。

二叉查找树既能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。

什么情况是最坏的情况呢？

还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、10、12、15、 21、28

这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。

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

因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。

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

这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。

平衡二叉树（AVL Tree）

平衡二叉树的定义：左右子树深度差绝对值不能超过 1。

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

这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。

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

当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。

那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。

同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。

所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？ 在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

第一个：索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。

第二个：数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。

第三个因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。

如果是这样存储数据的话，我们来看一下会有什么问题。

首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：

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';

当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。

那麼，一個樹的節點就是 16K 的大小。如果我們一個節點只存一個鍵值資料引用，例如整形的字段，可能只用了十幾個或幾十個字節，它遠遠達不到16K 的容量，所以訪問一個樹節點，進行一次IO 的時候，浪費了大量的空間。

所以如果每個節點儲存的資料太少，從索引中找到我們需要的數據，就要存取更多的節點，意味著跟磁碟互動次數就會過多。

如果是機械硬碟時代，每次從磁碟讀取資料需要 10ms 左右的尋址時間，互動次數越多，消耗的時間就越多。

例如上面這張圖，我們一張表裡面有6 條數據，當我們查詢id=37 的時候，要查詢兩個子節點，就需要跟磁碟交互3 次，如果我們有幾百萬的數據呢？這個時間更難估計。

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

第一個，就是讓每個節點儲存更多的資料。

第二個，節點上的關鍵字的數量越多，我們的指標數也越多，也就是代表可以有更多的分叉。

因為分叉數越多，樹的深度就會減少（根節點是 0）。這樣，我們的樹是不是從原來的高瘦高瘦的樣子，變成了矮胖矮胖的樣子？

這時候，我們的樹就不再是二元了，而是多叉，或叫做多路。

多路平衡查找樹（B Tree）

跟 AVL 樹一樣，B 樹在枝節點和葉子節點儲存鍵值、資料位址、節點引用。

它有一個特點：分叉數（路數）永遠比關鍵字數多 1。例如我們畫的這棵樹，每個節點都儲存兩個關鍵字，那麼就會有三個指標指向三個子節點。

B Tree 的查找規則是什麼樣的呢？

例如我們要在這張表裡面找 15。因為 15 小於 17，走左邊。因為 15 大於 12，走右邊。在磁碟區塊 7 裡面就找到了 15，只用了 3 次 IO。

這個是不是比 AVL 樹效率更高呢？那 B Tree 又是怎麼實現一個節點儲存多個關鍵字，還保持平衡的呢？跟 AVL 樹有什麼差別？

例如Max Degree（路數）是3 的時候，我們插入資料1、2、3，在插入3 的時候，本來應該在第一個磁碟區塊，但是如果一個節點有三個關鍵字的時候，意味著有4 個指針， 子節點會變成4 路，所以這個時候必須分裂（其實就是B Tree）。把中間的資料 2 提上去，把 1 和 3 變成 2 的子節點。

如果刪除節點，會有相反的合併的操作。

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

我們繼續插入 4 和 5，B Tree 又會出現分裂和合併的操作。

從這個裡面我們也能看到，在更新索引的時候會有大量的索引的結構的調整，所以解釋了為什麼我們不要在頻繁更新的列上建索引，或為什麼不要更新主鍵。

節點的分割與合併，其實就是 InnoDB 頁（page）的分割與合併。

B 樹（加強版B Tree）

B Tree 的效率已經很高了，為什麼MySQL 還要對B Tree 進行改良，最後使用了B Tree 呢？

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

我們來看看InnoDB 裡面的B 樹的儲存結構：

MySQL 中的B Tree 有幾個特點：

1. 它的關鍵字的數量是跟路數相等的；

2. #B Tree 的根節點和枝節點中都不會儲存數據，只有葉子節點才儲存資料。搜尋到關鍵字不會直接返回，會到最後一層的葉子節點。例如我們搜尋 id=28，雖然在第一層直接命中了，但全部的資料都在葉子節點上面，所以我還要繼續往下搜索，一直到葉子節點。

3. B Tree 的每個葉子節點增加了一個指向相鄰葉子節點的指針，它的最後一個數據會指向下一個葉子節點的第一個數據，形成了一個有序鍊錶的結構。

4. 它是根據左閉右開的區間 [ )來檢索資料。

B Tree 的資料搜尋過程：

1. #例如我們要找28，在根節點就找到了鍵值，但因為它不是頁子節點，所以會繼續往下搜尋，28 是[28,66)的左閉右開的區間的臨界值，所以會走中間的子節點，然後繼續搜索，它又是[28,34)的左閉右開的區間的臨界值，所以會走左邊的子節點，最後在葉子節點上找到了需要的數據。

2. 第二個，如果是範圍查詢，例如要查詢從22 到60 的數據，當找到22 之後，只需要順著節點和指針順序遍歷就可以一次訪問到所有的資料節點，這樣就大大提高了區間查詢效率（不需要返回上層父節點重複遍歷查找）。

InnoDB 中的B Tree 的特徵：

1. 它是B Tree 的變種，B Tree 能解決的問題，它都能解決。 B Tree 解決的兩大問題是什麼？ （每個節點儲存更多關鍵字；路數更多） ；

2. 掃庫、掃表能力更強（如果我們要對錶進行全表掃描，只需要遍歷葉子節點就可以了，不需要遍歷整棵B Tree 拿到所有的資料）；

3. B Tree 的磁碟讀寫能力相對於B Tree 來說更強（根節點和枝節點不保存資料區，所以一個節點可以保存更多的關鍵字，一次磁碟載入的關鍵字更多） ;

4. 排序能力更強（因為葉子節點上有下一個資料區的指針，資料形成了鍊錶）;

5. 效率更穩定（B Tree 永遠是在葉子節點拿到數據，所以IO 次數是穩定的）。

後記

看到這裡，相信小夥伴應該都知道了MySQL為什麼選擇使用 B 樹作為索引的資料結構模型。

更多程式相關知識，請造訪：程式設計入門！ ！

以上是MySQL中什麼是索引？索引存儲模型淺析的詳細內容。更多資訊請關注PHP中文網其他相關文章！