下面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）也就是我們所謂的二元查找樹誕生了。
左子樹所有的節點都小於父節點，右子樹所有的節點都大於父節點。投影到平面以後，就是一個有序的線性表。
二叉查找树既能够实现快速查找，又能够实现快速插入。
但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。
什么情况是最坏的情况呢？
还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、10、12、15、 21、28
这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。
造成它倾斜的原因是什么呢？
因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。
所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？
这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。
平衡二叉树的定义：左右子树深度差绝对值不能超过 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）。這樣，我們的樹是不是從原來的高瘦高瘦的樣子，變成了矮胖矮胖的樣子？
這時候，我們的樹就不再是二元了，而是多叉，或叫做多路。
跟 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 Tree 的效率已經很高了，為什麼MySQL 還要對B Tree 進行改良，最後使用了B Tree 呢？
總體來說，這個 B 樹的改良版本解決的問題比 B Tree 更全面。
我們來看看InnoDB 裡面的B 樹的儲存結構：
MySQL 中的B Tree 有幾個特點：
它的關鍵字的數量是跟路數相等的；
#B Tree 的根節點和枝節點中都不會儲存數據，只有葉子節點才儲存資料。搜尋到關鍵字不會直接返回，會到最後一層的葉子節點。例如我們搜尋 id=28，雖然在第一層直接命中了，但全部的資料都在葉子節點上面，所以我還要繼續往下搜索，一直到葉子節點。
B Tree 的每個葉子節點增加了一個指向相鄰葉子節點的指針，它的最後一個數據會指向下一個葉子節點的第一個數據，形成了一個有序鍊錶的結構。
它是根據左閉右開的區間 [ )來檢索資料。
B Tree 的資料搜尋過程：
#例如我們要找28，在根節點就找到了鍵值，但因為它不是頁子節點，所以會繼續往下搜尋，28 是[28,66)的左閉右開的區間的臨界值，所以會走中間的子節點，然後繼續搜索，它又是[28,34)的左閉右開的區間的臨界值，所以會走左邊的子節點，最後在葉子節點上找到了需要的數據。
第二個，如果是範圍查詢，例如要查詢從22 到60 的數據，當找到22 之後，只需要順著節點和指針順序遍歷就可以一次訪問到所有的資料節點，這樣就大大提高了區間查詢效率（不需要返回上層父節點重複遍歷查找）。
InnoDB 中的B Tree 的特徵：
它是B Tree 的變種，B Tree 能解決的問題，它都能解決。 B Tree 解決的兩大問題是什麼？ （每個節點儲存更多關鍵字；路數更多） ；
掃庫、掃表能力更強（如果我們要對錶進行全表掃描，只需要遍歷葉子節點就可以了，不需要遍歷整棵B Tree 拿到所有的資料）；
B Tree 的磁碟讀寫能力相對於B Tree 來說更強（根節點和枝節點不保存資料區，所以一個節點可以保存更多的關鍵字，一次磁碟載入的關鍵字更多） ;
排序能力更強（因為葉子節點上有下一個資料區的指針，資料形成了鍊錶）;
效率更穩定（B Tree 永遠是在葉子節點拿到數據，所以IO 次數是穩定的）。
看到這裡，相信小夥伴應該都知道了MySQL為什麼選擇使用 B 樹作為索引的資料結構模型。
更多程式相關知識，請造訪：程式設計入門！ ！
以上是MySQL中什麼是索引？索引存儲模型淺析的詳細內容。更多資訊請關注PHP中文網其他相關文章！
