索引是什么意思(MySQL中索引指的是什么)

索引是什么?

一張表有 500 萬條數據,在沒有索引的 name 字段上執行一條 where 查詢:

select*fromuser_innodbwherename='小馬';

如果 name 字段上面有索引呢?在 name 字段上面創建一個索引,再來執行一下相同的查詢。

ALTERTABLEuser_innodbDROPINDEXidx_name;ALTERTABLEuser_innodbADDINDEXidx_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 的時候,走右邊,到下一個樹的節點,繼續判斷。

如果是這樣存儲數據的話,我們來看一下會有什么問題。

首先,索引的數據,是放在硬盤上的。查看數據和索引的大小:

selectCONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB')ASdata_len,concat(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB')asindex_lenfrominformation_schema.TABLESwheretable_schema='gupao'andtable_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 次數是穩定的)。