Categories
程式開發

深入理解MySQL索引


前言

當提到MySQL數據庫的時候,我們的腦海裡會想起幾個關鍵字:索引、事務、數據庫鎖等等,索引是MySQL的靈魂,是平時進行查詢時的利器,也是面試中的重中之重

可能你了解索引的底層是b+樹,會加快查詢,也會在表中建立索引,但這是遠遠不夠的,這裡列舉幾個索引常見的面試題:

1、索引為什麼要用b+樹這種數據結構?

2、聚集索引和非聚集索引的區別?

3、索引什麼時候會失效,最左匹配原則是什麼?

當遇到這些問題的時候,可能會發現自己對索引還是一知半解,今天我們一起學習MySQL的索引。

一、一條查詢語句是如何執行的

首先來看 在MySQL數據庫中,一條查詢語句是如何執行的,索引出現在哪個環節,起到了什麼作用

1.1 應用程序發現SQL到服務端

當執行SQL語句時,應用程序會連接到相應的數據庫服務器,然後服務器對SQL進行處理。

1.2 查詢緩存

接著數據庫服務器會先去查詢是否有該SQL語句的緩存,key是查詢的語句,value是查詢的結果。如果你的查詢能夠直接命中,就會直接從緩存中拿出value來返回客戶端。

注:查詢不會被解析、不會生成執行計劃、不會被執行。

1.3 查詢優化處理,生成執行計劃

如果沒有命中緩存,則開始第三步。

  • 解析SQL:生成解析樹,驗證關鍵字如select,where,left join 等)是否正確。
  • 預處理:進一步檢查解析樹是否合法,如 檢查數據表和列是否存在,驗證用戶權限等。
  • 優化SQL決定使用哪個索引,或者在多個表相關聯的時候決定表的連接順序。緊接著,將SQL語句轉成執行計劃

1.4 將查詢結果返回客戶端

最後,數據庫服務器將查詢結果返回給客戶端。 (如果查詢可以緩存,MySQL也會將結果放到查詢緩存中)

深入理解MySQL索引 1

這就是一條查詢語句的執行流程,可以看到索引出現在優化SQL的流程步驟中,接下來了解索引到底是什麼?

二、索引概述

先簡單地了解一下索引的基本概念。

2.1 索引是什麼

索引是幫助數據庫高效獲取數據的數據結構。

2.2 索引的分類

1)從存儲結構上來劃分

  • Btree索引(B+tree,B-tree)
  • 哈希索引
  • full-index全文索引
  • RTree

2)從應用層次上來劃分

  • 普通索引:即一個索引只包含單個列,一個表可以有多個單列索引。
  • 唯一索引:索引列的值必須唯一,但允許有空值。
  • 複合索引:一個索引包含多個列。

3)從表記錄的排列順序和索引的排列順序是否一致來劃分

  • 聚集索引:表記錄的排列順序和索引的排列順序一致。
  • 非聚集索引:表記錄的排列順序和索引的排列順序不一致。

2.3 聚集索引和非聚集索引

1)簡單概括

  • 聚集索引:就是以主鍵創建的索引。
  • 非聚集索引:就是以非主鍵創建的索引(也叫做二級索引)。

2)詳細概括

  • 聚集索引

聚集索引表記錄的排列順序和索引的排列順序一致,所以查詢效率快,因為只要找到第一個索引值記錄,其餘的連續性的記錄在物理表中也會連續存放,一起就可以查詢到。

缺點:新增比較慢,因為為了保證表中記錄的物理順序和索引順序一致,在記錄插入的時候,會對數據頁重新排序。

  • 非聚集索引

索引的邏輯順序與磁盤上行的物理存儲順序不同,非聚集索引在葉子節點存儲的是主鍵和索引列,當我們使用非聚集索引查詢數據時,需要拿到葉子上的主鍵再去表中查到想要查找的數據。這個過程就是我們所說的回表。

3)聚集索引和非聚集索引的區別

  • 聚集索引在葉子節點存儲的是表中的數據。
  • 非聚集索引在葉子節點存儲的是主鍵和索引列。

舉個例子

比如漢語字典,想要查「阿」字,只需要翻到字典前幾頁,a開頭的位置,接著「啊」「愛」都會出來。也就是說,字典的正文部分本身就是一個目錄,不需要再去查其他目錄來找到需要找的內容。我們 把這種正文內容本身就是一種按照一定規則排列的目錄稱為==聚集索引==

如果遇到不認識的字,只能根據“偏旁部首”進行查找,然後根據這個字後的頁碼直接翻到某頁來找到要找的字。但結合 部首目錄檢字表 而查到的字的排序並不是真正的正文的排序方法。

深入理解MySQL索引 2

比如要查“玉”字,我們可以看到在查部首之後的檢字表中“玉”的頁碼是587頁,然後是珏,是251頁。很顯然,在字典中這兩個字並沒有挨著,現在看到的連續的“玉、珏、瑩”三字實際上就是他們 在非聚集索引中的排序,是字典正文中的字在非聚集索引中的映射。我們可以通過這種方式來找到所需要的字,但它需要兩個過程,先找到目錄中的結果,然後再翻到結果所對應的頁碼。我們 把這種目錄純粹是目錄,正文純粹是正文的排序方式稱為==非聚集索引==

2.4 MySQL如何添加索引

1)添加PRIMARY KEY(主鍵索引)

ALTER TABLE `table_name` ADD PRIMARY KEY ( `column` )

2)添加UNIQUE(唯一索引)

ALTER TABLE `table_name` ADD UNIQUE (`column`)

3)添加INDEX(普通索引)

ALTER TABLE `table_name` ADD INDEX index_name (`column` )

4)添加FULLTEXT(全文索引)

ALTER TABLE `table_name` ADD FULLTEXT (`column`)

5)添加多列索引

ALTER TABLE `table_name` ADD INDEX index_name (`column1`,`column2`,`column3`)

三、索引底層數據結構

了解了索引的基本概念後,可能最好奇的就是 索引的底層是怎麼實現的呢?為什麼索引可以如此高效地進行數據的查找?如何設計數據結構可以滿足我們的要求? 下文通過一般程序員的思維來想一下如果是我們來設計索引,要如何設計來達到索引的效果。

3.1 哈希索引

可能直接想到的就是用哈希表來實現快速查找,就像我們平時用的hashmap一樣,value = get(key) O(1)時間複雜度一步到位,確實,哈希索引 是一種方式。

1)定義

哈希索引就是採用一定的哈希算法,只需一次哈希算法即可立刻定位到相應的位置,速度非常快。本質上就是把鍵值換算成新的哈希值,根據這個哈希值來定位

深入理解MySQL索引 3

2)局限性

  • 哈希索引沒辦法利用索引完成排序。
  • 不能進行多字段查詢。
  • 在有大量重複鍵值的情況下,哈希索引的效率也是極低的(出現哈希碰撞問題)。
  • 不支持範圍查詢。

在MySQL常用的InnoDB引擎中,還是使用B+樹索引比較多。 InnoDB是自適應哈希索引的(hash索引的創建由 ==InnoDB存儲引擎自動優化創建==,我們干預不了)。

3.2 如何設計索引的數據結構呢

假設要查詢某個區間的數據,我們只需要拿到區間的起始值,然後在樹中進行查找。

如數據為:

深入理解MySQL索引 4

1)查詢[7,30]區間的數據

深入理解MySQL索引 5

深入理解MySQL索引 6

當查找到起點節點10後,再順著鍊錶進行遍歷,直到鍊錶中的節點數據大於區間的終止值為止。所有遍歷到的數據,就是符合區間值的所有數據

2)還可以怎麼優化呢?

利用二叉查找樹,區間查詢的功能已經實現了。但是,為了節省內存,我們只能把樹存儲在硬盤中。

那麼,每個節點的讀取或者訪問,都對應一次硬盤IO操作。每次查詢數據時磁盤IO操作的次數,也叫做==IO漸進複雜度==,也就是==樹的高度==

所以,我們要減少磁盤IO操作的次數,也就是 要==降低樹的高度==

結構優化過程如下圖所示:

深入理解MySQL索引 7

深入理解MySQL索引 8

深入理解MySQL索引 9

這裡將二叉樹變為了M叉樹,降低了樹的高度,那麼這個M應該選擇多少才合適呢?

問題:對於相同個數的數據構建m叉樹索引,m叉樹中的m越大,那樹的高度就越小,那m叉樹中的m是不是越大越好呢?到底多大才合適呢?

不管是內存中的數據還是磁盤中的數據,操作系統都是按頁(一頁的大小通常是4kb,這個值可以通過getconfig(PAGE_SIZE)命令查看)來讀取的,一次只會讀取一頁的數據。

如果要讀取的數據量超過了一頁的大小,就會觸發多次IO操作。所以在選擇m大小的時候,要盡量讓每個節點的大小等於一個頁的大小。

一般實際應用中,出度d(樹的分叉數)是非常大的數字,通常超過100;==樹的高度(h)非常小,通常不超過3==

3.3 B樹

順著解決問題的思路知道了我們想要的數據結構是什麼。目前索引常用的數據結構是B+樹,先介紹一下什麼是B樹(也就是B-樹)。

1)B樹的特點:

  • 關鍵字分佈在整棵樹的所有節點。
  • 任何一個關鍵字 出現且只出現在一個節點中
  • 搜索有可能在 非葉子節點 結束。
  • 其搜索性能等價於在關鍵字全集內做一次二分查找。如下圖所示:

深入理解MySQL索引 10

3.4 B+樹

了解了B樹,再來看一下B+樹,也是MySQL索引大部分情況所使用的數據結構。

下圖是一個M=3階的B+樹

深入理解MySQL索引 11

1)B+樹基本特點

  • 非葉子節點的子樹指針與關鍵字個數相同。
  • 非葉子節點的子樹指針P[i],指向關鍵字屬於 [k[k[k[k[i],K[i+1]) 的子樹(注意:區間是前閉後開)。
  • 為所有葉子節點增加一個鏈指針
  • 所有關鍵字都在葉子節點出現

這些基本特點是為了滿足以下的特性。

2)B+樹的特性

  • 所有的關鍵字 都出現在葉子節點的鍊錶中,且鍊錶中的關鍵字是有序的。
  • 搜索只在葉子節點命中
  • 非葉子節點相當於是 葉子節點的索引層,葉子節點是 存儲關鍵字數據的數據層

3)相對B樹,B+樹做索引的優勢

  • B+樹的磁盤讀寫代價更低。B+樹的內部沒有指向關鍵字具體信息的指針,所以其內部節點相對B樹更小,如果把所有關鍵字存放在同一塊盤中,那麼盤中所能容納的關鍵字數量也越多,一次性讀入內存的需要查找的關鍵字也就越多,相應的,IO讀寫次數就降低了
  • 樹的查詢效率更加穩定。 B+樹所有數據都存在於葉子節點,所有關鍵字查詢的路徑長度相同,每次數據的查詢效率相當。而B樹可能在非葉子節點就停止查找了,所以查詢效率不夠穩定。
  • B+樹只需要去遍歷葉子節點就可以實現整棵樹的遍歷

3.5 MongoDB的索引為什麼選擇B樹,而MySQL的索引是B+樹?

因為MongoDB不是傳統的關係型數據庫,而是以Json格式作為存儲的NoSQL非關係型數據庫,目的就是高性能、高可用、易擴展。擺脫了關係模型,所以 範圍查詢和遍歷查詢的需求就沒那麼強烈了

3.6 MyISAM存儲引擎和InnoDB的索引有什麼區別

1)MyISAM存儲引擎

深入理解MySQL索引 12

  • 主鍵索引

MyISAM的索引文件(.MYI)和數據文件(.MYD)文件是分離的,索引文件僅保存記錄所在頁的指針(物理位置),通過這些指針來讀取頁,進而讀取被索引的行。

樹中的葉子節點保存的是對應行的物理位置。通過該值,==存儲引擎能順利地進行回表查詢,得到一行完整記錄==

同時,每個葉子也保存了指向下一個葉子的指針,從而 方便葉子節點的範圍遍歷

  • 輔助索引

在MyISAM中,主鍵索引和輔助索引在結構上沒有任何區別,==只是主鍵索引要求key是唯一的,而輔助索引的key可以重複==

1)Innodb存儲引擎

Innodb的主鍵索引和輔助索引之前提到過,再回顧一次。

  • 主鍵索引

深入理解MySQL索引 13

InnoDB主鍵索引中既存儲了主健值,又存儲了行數據。

  • 輔助索引

深入理解MySQL索引 14

對於輔助索引,InnoDB採用的方式是在葉子節點中保存主鍵值,通過這個主鍵值來回表查詢到一條完整記錄,因此 按輔助索引檢索其實進行了二次查詢,效率是沒有主鍵索引高的

四、MySQL索引失效

在上一節中了解了索引的多種數據結構,以及B樹和B+樹的對比等,大家應該對索引的底層實現有了初步的了解。這一節從應用層的角度出發,看一下如何建索引更能滿足我們的需求,以及MySQL索引什麼時候會失效的問題。

先來思考一個小問題。

問題:當查詢條件為2個及2個以上時,是創建多個單列索引還是創建一個聯合索引好呢?它們之間的區別是什麼?哪個效率高呢?

先來建立一些單列索引進行測試:

深入理解MySQL索引 15

這裡建立了一張表,裡面建立了三個單列索引userId,mobile,billMonth。

然後進行多列查詢。

explain select * from `t_mobilesms_11` where userid = '1' and mobile = '13504679876' and billMonth = '1998-03'

深入理解MySQL索引 16

我們發現查詢時只用到了userid這一個單列索引,這是為什麼呢?因為這取決於 MySQL優化器的優化策略

當多條件聯合查詢時,優化器會評估哪個條件的索引效率高,它會選擇最佳的索引去使用。也就是說,此處三個索引列都可能被用到,只不過優化器判斷只需要使用userid這一個索引就能完成本次查詢,故最終explain展示的key為userid。

4.1 總結

多個單列索引在多條件查詢時優化器會選擇最優索引策略,可能 只用一個索引,也可能將多個索引都用上

但是多個單列索引底層會建立多個B+索引樹,比較佔用空間,也會浪費搜索效率 所以 多條件聯合查詢時最好建聯合索引

那聯合索引就可以三個條件都用到了嗎?會出現索引失效的問題嗎?

4.2 聯合索引失效問題

該部分參考並引用文章:一張圖搞懂MySQL的索引失效(https://segmentfault.com/a/1190000021464570

創建user表,然後建立 name, age, pos, phone 四個字段的聯合索引 全值匹配(索引最佳)。

深入理解MySQL索引 17

索引生效,這是最佳的查詢。

那麼時候會失效呢?

1)違反最左匹配原則

最左匹配原則:最左優先,以最左邊的為起點任何連續的索引都能匹配上,如不連續,則匹配不上。

如:建立索引為(a,b)的聯合索引,那麼只查 where b = 2 則不生效。換句話說:如果建立的索引是(a,b,c),也只有(a),(a,b),(a,b,c)三種查詢可以生效。

深入理解MySQL索引 18

這裡跳過了最左的name字段進行查詢,發現索引失效了。

遇到範圍查詢(>、<、between、like)就會停止匹配。

比如:a= 1 and b = 2 and c>3 and d =4 如果建立(a,b,c,d)順序的索引,d是用不到索引的,因為 c字段是一個範圍查詢,它之後的字段會停止匹配

2)在索引列上做任何操作

如計算、函數、(手動或自動)類型轉換等操作,會導致索引失效而進行全表掃描。

explain select * from user where left(name,3) = 'zhangsan' and age =20

深入理解MySQL索引 19

這裡對name字段進行了left函數操作,導致索引失效。

3)使用不等於(!= 、)

explain select * from user where age != 20;

深入理解MySQL索引 20

explain select * from user where age  20;

深入理解MySQL索引 21

4)like中以通配符開頭(’%abc’)

索引失效

explain select * from user where name like ‘%zhangsan’;

深入理解MySQL索引 22

索引生效

explain select * from user where name like ‘zhangsan%’;

深入理解MySQL索引 23

5)字符串不加單引號索引失效

explain select * from user where name = 2000;

深入理解MySQL索引 24

6)or連接索引失效

explain select * from user where name = ‘2000’ or age = 20 or pos =‘cxy’;

深入理解MySQL索引 25

7)order by

正常(索引參與了排序),沒有違反最左匹配原則。

explain select * from user where name = 'zhangsan' and age = 20 order by age,pos;

深入理解MySQL索引 26

違反最左前綴法則,導致額外的文件排序(會降低性能)。

explain select name,age from user where name = 'zhangsan' order by pos;

深入理解MySQL索引 27

8)group by

正常(索引參與了排序)。

explain select name,age from user where name = 'zhangsan' group by age;

違反最左前綴法則,導致產生臨時表(會降低性能)。

explain select name,age from user where name = 'zhangsan' group by pos,age;

深入理解MySQL索引 28

五、總結

  • 了解一條查詢語句是如何執行的,發現建立索引是一種可以高效查找的數據結構。
  • 了解了索引的各種分類情況,聚集索引和非聚集索引的區別,如何創建各種索引。
  • 通過需求一步步分析出為什麼MySQL要選b+tree作為索引的數據結構,對比了btree和b+tree的區別、 MyISAM和innodb中索引的區別。
  • 了解了索引會失效的多種情況,比較重要的最左匹配原則,相應地我們可以在建索引的時候做一些優化。

希望大家能夠多去使用索引進行SQL優化,有問題歡迎指出。

文章配圖來源於網絡

本文轉載自公眾號宜信技術學院(ID:CE_TECH)。

原文鏈接

https://mp.weixin.qq.com/s/sT-Jz67p8Gadvcft-iO-9g