Mysql索引

索引介紹

索引是什么

官方介紹索引是幫助MySQL高效獲取資料的資料結構，更通俗的說，資料庫索引好比是一本書前面的目錄，能加快資料庫的查詢速度，
一般來說索引本身也很大，不可能全部存盤在記憶體中，因此索引往往是存盤在磁盤上的檔案中的（可能存盤在單獨的索引檔案中，也可能和資料一起存盤在資料檔案中），
我們通常所說的索引，包括聚集索引、覆寫索引、組合索引、前綴索引、唯一索引等，沒有特別說明，默認都是使用B+樹結構組織（多路搜索樹，并不一定是二叉的）的索引，

索引的優勢和劣勢

優勢：

可以提高資料檢索的效率，降低資料庫的IO成本，類似于書的目錄，
通過索引列對資料進行排序，降低資料排序的成本，降低了CPU的消耗，
- 被索引的列會自動進行排序，包括【單列索引】和【組合索引】，只是組合索引的排序要復雜一些，
- 如果按照索引列的順序進行排序，對應order by陳述句來說，效率就會提高很多，

劣勢：

索引會占據磁盤空間
索引雖然會提高查詢效率，但是會降低更新表的效率，比如每次對表進行增刪改操作，MySQL不僅要保存資料，還有保存或者更新對應的索引檔案，

索引型別

主鍵索引

索引列中的值必須是唯一的，不允許有空值，

普通索引

MySQL中基本索引型別，沒有什么限制，允許在定義索引的列中插入重復值和空值，

唯一索引

索引列中的值必須是唯一的，但是允許為空值，

全文索引

只能在文本型別CHAR,VARCHAR,TEXT型別欄位上創建全文索引，欄位長度比較大時，如果創建普通索引，在進行like模糊查詢時效率比較低，這時可以創建全文索引， MyISAM和InnoDB中都可以使用全文索引，

空間索引

MySQL在5.7之后的版本支持了空間索引，而且支持OpenGIS幾何資料模型，MySQL在空間索引這方面遵循OpenGIS幾何資料模型規則，

前綴索引

在文本型別如CHAR,VARCHAR,TEXT類列上創建索引時，可以指定索引列的長度，但是數值型別不能指定，

其他（按照索引列數量分類）

單列索引
組合索引

組合索引的使用，需要遵循最左前綴匹配原則（最左匹配原則），一般情況下在條件允許的情況下使用組合索引替代多個單列索引使用，

索引的資料結構

Hash表

Hash表，在Java中的HashMap，TreeMap就是Hash表結構，以鍵值對的方式存盤資料，我們使用Hash表存盤表資料Key可以存盤索引列，Value可以存盤行記錄或者行磁盤地址，Hash表在等值查詢時效率很高，時間復雜度為O(1)；但是不支持范圍快速查找，范圍查找時還是只能通過掃描全表方式，

顯然這種并不適合作為經常需要查找和范圍查找的資料庫索引使用，

二叉查找樹

二叉樹，我想大家都會在心里有個圖，

在這里插入圖片描述

二叉樹特點：每個節點最多有2個分叉，左子樹和右子樹資料順序左小右大，

這個特點就是為了保證每次查找都可以這折半而減少IO次數，但是二叉樹就很考驗第一個根節點的取值，因為很容易在這個特點下出現我們并發想發生的情況“樹不分叉了”，這就很難受很不穩定，

在這里插入圖片描述

顯然這種情況不穩定的我們再選擇設計上必然會避免這種情況的

平衡二叉樹

平衡二叉樹是采用二分法思維，平衡二叉查找樹除了具備二叉樹的特點，最主要的特征是樹的左右兩個子樹的層級最多相差1，在插入洗掉資料時通過左旋/右旋操作保持二叉樹的平衡，不會出現左子樹很高、右子樹很矮的情況，

使用平衡二叉查找樹查詢的性能接近于二分查找法，時間復雜度是 O(log2n)，查詢id=6，只需要兩次IO，

在這里插入圖片描述

就這個特點來看，可能各位會覺得這就很好，可以達到二叉樹的理想的情況了，然而依然存在一些問題：

時間復雜度和樹高相關，樹有多高就需要檢索多少次，每個節點的讀取，都對應一次磁盤 IO 操作，樹的高度就等于每次查詢資料時磁盤 IO 操作的次數，磁盤每次尋道時間為10ms，在表資料量大時，查詢性能就會很差，（1百萬的資料量，log2n約等于20次磁盤IO，時間20*10=0.2s）
平衡二叉樹不支持范圍查詢快速查找，范圍查詢時需要從根節點多次遍歷，查詢效率不高，

B樹：改造二叉樹

MySQL的資料是存盤在磁盤檔案中的，查詢處理資料時，需要先把磁盤中的資料加載到記憶體中，磁盤IO 操作非常耗時，所以我們優化的重點就是盡量減少磁盤 IO 操作，訪問二叉樹的每個節點就會發生一次IO，如果想要減少磁盤IO操作，就需要盡量降低樹的高度，那如何降低樹的高度呢？

假如key為bigint=8位元組，每個節點有兩個指標，每個指標為4個位元組，一個節點占用的空間16個位元組（8+4*2=16），

因為在MySQL的InnoDB存盤引擎一次IO會讀取的一頁（默認一頁16K）的資料量，而二叉樹一次IO有效資料量只有16位元組，空間利用率極低，為了最大化利用一次IO空間，一個簡單的想法是在每個節點存盤多個元素，在每個節點盡可能多的存盤資料，每個節點可以存盤1000個索引（16k/16=1000），這樣就將二叉樹改造成了多叉樹，通過增加樹的叉樹，將樹從高瘦變為矮胖，構建1百萬條資料，樹的高度只需要2層就可以（1000*1000=1百萬），也就是說只需要2次磁盤IO就可以查詢到資料，磁盤IO次數變少了，查詢資料的效率也就提高了，

這種資料結構我們稱為B樹，B樹是一種多叉平衡查找樹，如下圖主要特點：

B樹的節點中存盤著多個元素，每個內節點有多個分叉，
節點中的元素包含鍵值和資料，節點中的鍵值從大到小排列，也就是說，在所有的節點都儲存資料，
父節點當中的元素不會出現在子節點中，
所有的葉子結點都位于同一層，葉節點具有相同的深度，葉節點之間沒有指標連接，

在這里插入圖片描述

舉個例子，在b樹中查詢資料的情況：

假如我們查詢值等于10的資料，查詢路徑磁盤塊1->磁盤塊2->磁盤塊5，

第一次磁盤IO：將磁盤塊1加載到記憶體中，在記憶體中從頭遍歷比較，10<15，走左路，到磁盤尋址磁盤塊2，

第二次磁盤IO：將磁盤塊2加載到記憶體中，在記憶體中從頭遍歷比較，7<10，到磁盤中尋址定位到磁盤塊5，

第三次磁盤IO：將磁盤塊5加載到記憶體中，在記憶體中從頭遍歷比較，10=10，找到10，取出data，如果data存盤的行記錄，取出data，查詢結束，如果存盤的是磁盤地址，還需要根據磁盤地址到磁盤中取出資料，查詢終止，

相比二叉平衡查找樹，在整個查找程序中，雖然資料的比較次數并沒有明顯減少，但是磁盤IO次數會大大減少，同時，由于我們的比較是在記憶體中進行的，比較的耗時可以忽略不計，B樹的高度一般2至3層就能滿足大部分的應用場景，所以使用B樹構建索引可以很好的提升查詢的效率，

程序如圖：

看到這里一定覺得B樹就很理想了，但是前輩們會告訴你依然存在可以優化的地方：

B樹不支持范圍查詢的快速查找，你想想這么一個情況如果我們想要查找10和35之間的資料，查找到15之后，需要回到根節點重新遍歷查找，需要從根節點進行多次遍歷，查詢效率有待提高，

如果data存盤的是行記錄，行的大小隨著列數的增多，所占空間會變大，這時，一個頁中可存盤的資料量就會變少，樹相應就會變高，磁盤IO次數就會變大，

B+樹：改造B樹

B+樹，作為B樹的升級版，在B樹基礎上，MySQL在B樹的基礎上繼續改造，使用B+樹構建索引，B+樹和B樹最主要的區別在于非葉子節點是否存盤資料的問題

B樹：非葉子節點和葉子節點都會存盤資料，
B+樹：只有葉子節點才會存盤資料，非葉子節點至存盤鍵值，葉子節點之間使用雙向指標連接，最底層的葉子節點形成了一個雙向有序鏈表，

在這里插入圖片描述

B+樹的最底層葉子節點包含了所有的索引項，從圖上可以看到，B+樹在查找資料的時候，由于資料都存放在最底層的葉子節點上，所以每次查找都需要檢索到葉子節點才能查詢到資料，所以在需要查詢資料的情況下每次的磁盤的IO跟樹高有直接的關系，但是從另一方面來說，由于資料都被放到了葉子節點，所以放索引的磁盤塊鎖存放的索引數量是會跟這增加的，所以相對于B樹來說，B+樹的樹高理論上情況下是比B樹要矮的，也存在索引覆寫查詢的情況，在索引中資料滿足了當前查詢陳述句所需要的全部資料，此時只需要找到索引即可立刻回傳，不需要檢索到最底層的葉子節點，

舉個例子：

等值查詢：

假如我們查詢值等于9的資料，查詢路徑磁盤塊1->磁盤塊2->磁盤塊6，

第一次磁盤IO：將磁盤塊1加載到記憶體中，在記憶體中從頭遍歷比較，9<15，走左路，到磁盤尋址磁盤塊2，

第二次磁盤IO：將磁盤塊2加載到記憶體中，在記憶體中從頭遍歷比較，7<9<12，到磁盤中尋址定位到磁盤塊6，

第三次磁盤IO：將磁盤塊6加載到記憶體中，在記憶體中從頭遍歷比較，在第三個索引中找到9，取出data，如果data存盤的行記錄，取出data，查詢結束，如果存盤的是磁盤地址，還需要根據磁盤地址到磁盤中取出資料，查詢終止，（這里需要區分的是在InnoDB中Data存盤的為行資料，而MyIsam中存盤的是磁盤地址，）

程序如圖：

范圍查詢：

假如我們想要查找9和26之間的資料，查找路徑是磁盤塊1->磁盤塊2->磁盤塊6->磁盤塊7，

首先查找值等于9的資料，將值等于9的資料快取到結果集，這一步和前面等值查詢流程一樣，發生了三次磁盤IO，

查找到15之后，底層的葉子節點是一個有序串列，我們從磁盤塊6，鍵值9開始向后遍歷篩選所有符合篩選條件的資料，

第四次磁盤IO：根據磁盤6后繼指標到磁盤中尋址定位到磁盤塊7，將磁盤7加載到記憶體中，在記憶體中從頭遍歷比較，9<25<26，9<26<=26，將data快取到結果集，

主鍵具備唯一性（后面不會有<=26的資料），不需再向后查找，查詢終止，將結果集回傳給用戶，

可以看到B+樹可以保證等值和范圍查詢的快速查找，MySQL的索引就采用了B+樹的資料結構，

Mysql的索引實作

介紹完了索引資料結構，那肯定是要帶入到Mysql里面看看真實的使用場景的，所以這里分析Mysql的兩種存盤引擎的索引實作：MyISAM索引和InnoDB索引

MyIsam索引

以一個簡單的user表為例，user表存在兩個索引，id列為主鍵索引，age列為普通索引

CREATE TABLE `user`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = MyISAM
  AUTO_INCREMENT = 1
  DEFAULT CHARSET = utf8;

在這里插入圖片描述

MyISAM的資料檔案和索引檔案是分開存盤的，MyISAM使用B+樹構建索引樹時，葉子節點中存盤的鍵值為索引列的值，資料為索引所在行的磁盤地址，

主鍵索引

在這里插入圖片描述

表user的索引存盤在索引檔案user.MYI中，資料檔案存盤在資料檔案 user.MYD中，

簡單分析下查詢時的磁盤IO情況：

根據主鍵等值查詢資料：

select * from user where id = 28;

先在主鍵樹中從根節點開始檢索，將根節點加載到記憶體，比較28<75，走左路，（1次磁盤IO）
將左子樹節點加載到記憶體中，比較16<28<47，向下檢索，（1次磁盤IO）
檢索到葉節點，將節點加載到記憶體中遍歷，比較16<28，18<28，28=28，查找到值等于30的索引項，（1次磁盤IO）
從索引項中獲取磁盤地址，然后到資料檔案user.MYD中獲取對應整行記錄，（1次磁盤IO）
將記錄返給客戶端，

磁盤IO次數：3次索引檢索+記錄資料檢索，

在這里插入圖片描述

根據主鍵范圍查詢資料：

select * from user where id between 28 and 47;

先在主鍵樹中從根節點開始檢索，將根節點加載到記憶體，比較28<75，走左路，（1次磁盤IO）
將左子樹節點加載到記憶體中，比較16<28<47，向下檢索，（1次磁盤IO）
檢索到葉節點，將節點加載到記憶體中遍歷比較16<28，18<28，28=28<47，查找到值等于28的索引項，

根據磁盤地址從資料檔案中獲取行記錄快取到結果集中，（1次磁盤IO）

我們的查詢陳述句時范圍查找，需要向后遍歷底層葉子鏈表，直至到達最后一個不滿足篩選條件，
向后遍歷底層葉子鏈表，將下一個節點加載到記憶體中，遍歷比較，28<47=47，根據磁盤地址從資料檔案中獲取行記錄快取到結果集中，（1次磁盤IO）
最后得到兩條符合篩選條件，將查詢結果集返給客戶端，

磁盤IO次數：4次索引檢索+記錄資料檢索，

在這里插入圖片描述

**備注：**以上分析僅供參考，MyISAM在查詢時，會將索引節點快取在MySQL快取中，而資料快取依賴于作業系統自身的快取，所以并不是每次都是走的磁盤，這里只是為了分析索引的使用程序，

輔助索引

在 MyISAM 中,輔助索引和主鍵索引的結構是一樣的，沒有任何區別，葉子節點的資料存盤的都是行記錄的磁盤地址，只是主鍵索引的鍵值是唯一的，而輔助索引的鍵值可以重復，

查詢資料時，由于輔助索引的鍵值不唯一，可能存在多個擁有相同的記錄，所以即使是等值查詢，也需要按照范圍查詢的方式在輔助索引樹中檢索資料，

InnoDB索引

主鍵索引（聚簇索引）

每個InnoDB表都有一個聚簇索引，聚簇索引使用B+樹構建，葉子節點存盤的資料是整行記錄，一般情況下，聚簇索引等同于主鍵索引，當一個表沒有創建主鍵索引時，InnoDB會自動創建一個ROWID欄位來構建聚簇索引，InnoDB創建索引的具體規則如下：

在表上定義主鍵PRIMARY KEY，InnoDB將主鍵索參考作聚簇索引，
如果表沒有定義主鍵，InnoDB會選擇第一個不為NULL的唯一索引列用作聚簇索引，
如果以上兩個都沒有，InnoDB 會使用一個6 位元組長整型的隱式欄位 ROWID欄位構建聚簇索引，該ROWID欄位會在插入新行時自動遞增，

除聚簇索引之外的所有索引都稱為輔助索引，在中InnoDB，輔助索引中的葉子節點存盤的資料是該行的主鍵值都，在檢索時，InnoDB使用此主鍵值在聚簇索引中搜索行記錄，

這里以user_innodb為例，user_innodb的id列為主鍵，age列為普通索引，

CREATE TABLE `user_innodb`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = InnoDB;

在這里插入圖片描述

InnoDB的資料和索引存盤在一個檔案t_user_innodb.ibd中，InnoDB的資料組織方式，是聚簇索引，

主鍵索引的葉子節點會存盤資料行，輔助索引只會存盤主鍵值，

在這里插入圖片描述

等值查詢資料：

select * from user_innodb where id = 28;

先在主鍵樹中從根節點開始檢索，將根節點加載到記憶體，比較28<75，走左路，（1次磁盤IO）
將左子樹節點加載到記憶體中，比較16<28<47，向下檢索，（1次磁盤IO）
檢索到葉節點，將節點加載到記憶體中遍歷，比較16<28，18<28，28=28，查找到值等于28的索引項，直接可以獲取整行資料，將改記錄回傳給客戶端，（1次磁盤IO）

磁盤IO數量：3次，

在這里插入圖片描述

輔助索引

除聚簇索引之外的所有索引都稱為輔助索引，InnoDB的輔助索引只會存盤主鍵值而非磁盤地址，

以表user_innodb的age列為例，age索引的索引結果如下圖，

在這里插入圖片描述

底層葉子節點的按照（age，id）的順序排序，先按照age列從小到大排序，age列相同時按照id列從小到大排序，

使用輔助索引需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后使用主鍵到主索引中檢索獲得記錄，

畫圖分析等值查詢的情況：

select * from t_user_innodb where age=19;

在這里插入圖片描述

根據在輔助索引樹中獲取的主鍵id，到主鍵索引樹檢索資料的程序稱為回表查詢，

磁盤IO數：輔助索引3次+獲取記錄回表3次

組合索引

還是以自己創建的一個表為例：表 abc_innodb，id為主鍵索引，創建了一個聯合索引idx_abc(a,b,c)，

CREATE TABLE `abc_innodb`
(
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `a`  int(11)     DEFAULT NULL,
  `b`  int(11)     DEFAULT NULL,
  `c`  varchar(10) DEFAULT NULL,
  `d`  varchar(10) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_abc` (`a`, `b`, `c`)
) ENGINE = InnoDB;

select * from abc_innodb order by a, b, c, id;

在這里插入圖片描述

組合索引的資料結構：

在這里插入圖片描述

組合索引的查詢程序：

select * from abc_innodb where a = 13 and b = 16 and c = 4;

在這里插入圖片描述

最左匹配原則：

最左前綴匹配原則和聯合索引的索引存盤結構和檢索方式是有關系的，

在組合索引樹中，最底層的葉子節點按照第一列a列從左到右遞增排列，但是b列和c列是無序的，b列只有在a列值相等的情況下小范圍內遞增有序，而c列只能在a，b兩列相等的情況下小范圍內遞增有序，

就像上面的查詢，B+樹會先比較a列來確定下一步應該搜索的方向，往左還是往右，如果a列相同再比較b列，但是如果查詢條件沒有a列，B+樹就不知道第一步應該從哪個節點查起，

可以說創建的idx_abc(a,b,c)索引，相當于創建了(a)、（a,b）（a,b,c）三個索引，、

組合索引的最左前綴匹配原則：使用組合索引查詢時，mysql會一直向右匹配直至遇到范圍查詢(>、<、between、like)就停止匹配，

覆寫索引

覆寫索引并不是說是索引結構，覆寫索引是一種很常用的優化手段，因為在使用輔助索引的時候，我們只可以拿到主鍵值，相當于獲取資料還需要再根據主鍵查詢主鍵索引再獲取到資料，但是試想下這么一種情況，在上面abc_innodb表中的組合索引查詢時，如果我只需要abc欄位的，那是不是意味著我們查詢到組合索引的葉子節點就可以直接回傳了，而不需要回表，這種情況就是覆寫索引，

可以看一下執行計劃：

覆寫索引的情況：

在這里插入圖片描述

未使用到覆寫索引：

在這里插入圖片描述

總結

看到這里，你是不是對于自己的sql陳述句里面的索引的有了更多優化想法呢，比如：

避免回表

在InnoDB的存盤引擎中，使用輔助索引查詢的時候，因為輔助索引葉子節點保存的資料不是當前記錄的資料而是當前記錄的主鍵索引，索引如果需要獲取當前記錄完整資料就必然需要根據主鍵值從主鍵索引繼續查詢，這個程序我們成位回表，想想回表必然是會消耗性能影響性能，那如何避免呢？

使用索引覆寫，舉個例子：現有User表（id(PK),name(key),sex,address,hobby…）

如果在一個場景下，select id,name,sex from user where name ='zhangsan';這個陳述句在業務上頻繁使用到，而user表的其他欄位使用頻率遠低于它，在這種情況下，如果我們在建立 name 欄位的索引的時候，不是使用單一索引，而是使用聯合索引（name，sex）這樣的話再執行這個查詢陳述句是不是根據輔助索引查詢到的結果就可以獲取當前陳述句的完整資料，這樣就可以有效地避免了回表再獲取sex的資料，

這里就是一個典型的使用覆寫索引的優化策略減少回表的情況，

聯合索引的使用

聯合索引，在建立索引的時候，盡量在多個單列索引上判斷下是否可以使用聯合索引，聯合索引的使用不僅可以節省空間，還可以更容易的使用到索引覆寫，試想一下，索引的欄位越多，是不是更容易滿足查詢需要回傳的資料呢，比如聯合索引（a_b_c），是不是等于有了索引：a，a_b，a_b_c三個索引，這樣是不是節省了空間，當然節省的空間并不是三倍于（a，a_b，a_b_c）三個索引，因為索引樹的資料沒變，但是索引data欄位的資料確實真實的節省了，

聯合索引的創建原則，在創建聯合索引的時候因該把頻繁使用的列、區分度高的列放在前面，頻繁使用代表索引利用率高，區分度高代表篩選粒度大，這些都是在索引創建的需要考慮到的優化場景，也可以在常需要作為查詢回傳的欄位上增加到聯合索引中，如果在聯合索引上增加一個欄位而使用到了覆寫索引，那我建議這種情況下使用聯合索引，

聯合索引的使用

考慮當前是否已經存在多個可以合并的單列索引，如果有，那么將當前多個單列索引創建為一個聯合索引，
當前索引存在頻繁使用作為回傳欄位的列，這個時候就可以考慮當前列是否可以加入到當前已經存在索引上，使其查詢陳述句可以使用到覆寫索引，

敖丙

CSDN認證博客專家 CSDN簽約作者演算法工程師 B站網紅UP

微信搜一搜【敖丙】關注這個文縐縐的程式員，關注后回復【資料】有我準備的一線大廠面試資料和簡歷模板，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/192593.html

標籤：其他

上一篇：2020年1024程式員節，成為CSDN博客專家

下一篇：java，從入土到出棺——3.邏輯結構與程式控制

一文搞懂MySQL索引所有知識點（建議收藏）

Mysql索引

索引介紹

索引是什么

索引的優勢和劣勢

索引型別

主鍵索引

普通索引

唯一索引

全文索引

空間索引

前綴索引

其他（按照索引列數量分類）

索引的資料結構

Hash表

二叉查找樹

平衡二叉樹

B樹：改造二叉樹

B+樹：改造B樹

Mysql的索引實作

MyIsam索引

主鍵索引

輔助索引

InnoDB索引

主鍵索引（聚簇索引）

輔助索引

組合索引

覆寫索引

總結

避免回表

聯合索引的使用