Mysql索引是什麼“鬼”

前言

索引有很多種，hash索引，B樹索引，B+樹索引，全文索引等。Mysql支援多種存儲引擎，多種存儲引擎對索引的支援也各不相同。本文探究Mysql為什麼使用B+樹來作為索引的資料結構，索引的原理以及Sql中索引的優化。

Mysql官方對索引的定義是：索引（Index）是幫助Mysql高效擷取資料的資料結構。提取句子主幹就是：索引是資料結構。

索引的原理

索引的目的

索引的目的在于提高查詢或檢索效率。例如我們要在字典中查詢“mysql”這個單詞，是不是先要查詢m開頭的單詞表，然後在查詢第二個字母為y的單詞，然後縮小範圍繼續找，知道找到“mysql”這個單詞為止或者查無此詞。這就好像我們沿着一個樹從樹根開始找，沿着主幹，樹幹，到最後的末梢，走了其中的一條路徑。這比一個查詢一個連結清單的結構，從頭找到尾，在大多數情況下，效率要高得多。

Mysql的索引為什麼是B+樹

為什麼不用普通的二叉樹，這裡就不必多說了，因為對于大的資料量，二叉樹的高度太高，索引的效率低下。這裡主要說明為什麼不用B樹（B-樹就是B樹），而是用B+樹。

B樹（B-樹）介紹

我們都知道二叉樹查詢的時間複雜度為Ｏ(logN)，查詢效率已經夠高了，但為什麼還要有B樹和B+樹呢？答案是磁盤IO。我們都知道，IO操作的效率很低，當有存儲的有很大的資料量，查詢的時候，我們不可能把全部資料都加載到記憶體中，隻能逐一加載磁盤頁，每個磁盤頁對應樹的節點，造成大量的磁盤IO操作（最壞情況下，磁盤IO操作次數是樹的高度），平衡二叉樹由于樹的高度太大造成磁盤IO讀寫過于頻繁，進而導緻效率低下，是以多路查找樹-B樹/B+樹應運而生。

下面是一個三階的B樹（實際中節點元素很多）

B樹有以下特點：

• 在一個節點中存放着資料和指針，且互相間隔
• 在同一個節點中，key是增序的

• 如果一個節點最左邊的指針不為空，則它指定的節點左右的key小于最左邊的key。

  中間的指針指向的節點的key位于相鄰兩個key的中間。

• B樹中不同節點存放的key和指針可能數量不一緻，但是每個節點的域和上限是一緻的，是以在實作中B樹往往對每個節點申請同等大小的空間
• 每個非葉子節點由n-1個key和n個指針組成，其中d<=n<=2d

B+樹

B+樹有以下特點：

• 内節點不存儲data，隻存儲key和指針，葉子結點不存儲指針，隻存儲key和data
• 内節點和葉子結點的大小不同，因為存儲的東西不同
• 每個非葉子結點的指針上限為2d而不是2d+1
• 因為節點内部沒有data，是以有更多的空間放key，是以B+樹的出度一般比B樹要大，而對于一定的資料，出度大的話，樹的深度就小，是以B+樹的檢索效率比B樹高

為什麼B+樹比B樹更适合Mysql索引

• B+樹的磁盤讀取代價低：

  因為B+樹的非葉子結點沒有存儲資料，是以如果把所有同一内部節點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。

  一次性讀記憶體中的需要查找的關鍵字也就越多。

  相對來說IO讀寫次數也就降低了。

• B+樹的查詢效率更穩定：

  由于B+樹的分支結點并不是最終指向檔案内容的結點，隻是葉子結點的索引，是以任意關鍵字的查找都必須從根節點走向分支結點，查詢路徑相同。

  但B樹的分支結點儲存有資料，是以查詢路徑可能不同。

• B+樹便于執行掃庫操作：

  由于B+樹的資料都存儲在葉子節點上，分支節點均為索引，友善掃庫，隻需掃一遍葉子即可。

  但是B樹在分支節點上都儲存着資料，要找到具體的順序資料，需要執行一次中序周遊來查找

Mysql的索引實作

我們知道Mysql有兩種常用的存儲引擎，MyISAM和InnoDB，這兩種存儲引擎對索引的實作方式是不同的。

MyISAM索引實作

MyISAM使用B+樹作為索引的結構，葉子結點的data域存放的是資料記錄的位址。

上圖中是以Col1作為主鍵的MyISAM主索引的示意圖。可以看到，組下面一層葉子結點的data域存放的是資料記錄的位址。如果我們在字段Col2上建一個輔助索引，那麼索引的結構如下：

MyISAM索引檢索算法是這樣的，首先按照B+樹的搜尋算法查詢索引，如果指定的key存在，則取出data域的值，然後用data域的位址查詢資料記錄。MyISAM的索引方式也叫“非聚集的”，跟InnoDB的“聚集索引”相區分，因為資料記錄和索引不在一起。

InnoDB索引實作

InnoDB的索引實作方式與MyISAM的索引實作方式的差別有兩個：

第一，InnoDB的資料檔案本身就是索引檔案。在InnoDB中，資料檔案本身就是按B+樹組織的一個索引結構，而且是主索引結構。資料和索引在一起，葉子結點儲存了完整的資料記錄，這種索引叫做聚集索引。因為InnoDB的資料檔案本身要按主鍵聚集，是以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一辨別資料記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隐含字段作為主鍵，這個字段長度為6個位元組，類型為長整形。

第二，InnoDB輔助索引的data域存儲的是相應記錄主鍵的值而不是位址。如圖，下圖是定義在Col3上的一個輔助索引的示意圖。葉子結點存儲了col3的值和對應的主鍵col1的值。

索引優化

牆裂建議使用自增主鍵

在使用InnoDB作為存儲引擎時，如果沒有特殊需要，請永遠是用一個與業務無關的自增字段作為主鍵，而且這個字段長度不宜過大。為什麼？InnoDB使用聚集索引，資料記錄本身存放在主索引（B+樹）的葉子結點上，這就要求同一個葉子結點（大小為一個記憶體頁或磁盤頁）的資料記錄按主鍵順序存放，每當一條新的記錄插入時，mysql會根據其主鍵将其插入适當的節點和位置，如果頁面達到裝載因子（InnoDB預設為15/16），則開辟一個新的頁（節點）。如果使用自增主鍵，那麼每次插入新的記錄，記錄就會順序插入到目前節點的下一個位置。這樣就會形成一個緊湊的索引結構，每次插入不需要移動已有資料，是以效率很高。如下圖：

如果使用非自增主鍵（例如身份證号或學号這種無序字元串），每次插入主鍵近似随機，每次記錄都要插入到現有索引頁的中間的某個位置，這時不得不移動元素來完成插入，增加了開銷。如下圖：

索引的最左字首原則

聯合索引：mysql可以将多個列按照順序作為一個索引，這種索引叫做聯合索引。

索引的最左比對原則是：假如索引列分别為A，B，C，順序也是A，B，C，那麼：

• 查詢的時候，如果查詢【A】，【A，B】，【A，B，C】，可以使用索引查詢。
• 如果查詢的時候，查詢【A，C】，由于中間缺失了B，那麼C這個索引是用不到的，隻能用到A索引。
• 如果查詢的時候，查詢【B】，【B，C】或【C】，由于缺失了最左字首A，那麼是用不到這個聯合索引的，除非有其他索引。
• 如果查詢的時候使用範圍查詢，并且是最左字首，那麼可以用到索引，但是範圍後面的字段無法用到索引。

這個原則可以結合索引的原理來了解：Mysql索引是B+樹這種複合結構，當索引是聯合索引，比如【name,age,sex】時，B+樹是按照從左到右的順序建立索引樹的。當（張三，20，M）這樣的資料來檢索時，B+樹會優先根據name來确定下一步的搜尋方向，如果name相同再比較name和sex，最後得到檢索的資料。但當（20，M）這樣的資料來的時候，mysql就不知道該查哪個節點，因為建立索引的時候，name就是第一個比較因子，必須先根據name去确定下一步去哪裡搜尋。當（張三，M）這樣的資料來時，可以根據name是“張三”，來确定下一步的搜尋，然後再去比對性别是“M”的資料，是以隻能用到聯合索引中name這個索引。

其他原則

1、盡量選擇區分度高的列作為索引，區分度公式：count(distinct col)/count(*)，表示字段不重複的比例，比例越大，我們掃描的記錄數就越少，唯一性的列的區分度為1。這就是為什麼不建議在狀态，性别這樣區分度很小的列上建立索引的原因。

2、索引列在sql語句中不能參與運算，否則會導緻索引失效。例如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很簡單，b+樹中存的都是資料表中的字段值，但進行檢索時，需要把所有元素都應用函數才能比較，顯然成本太大。應該改成create_time = unix_timestamp(’2014-05-29’);

3、聯合索引比單個索引的成本效益更高。例如，建立【A，B，C】這個聯合索引，相當于建立了【A】，【A,B】，【A，B，C】這三個索引。這就要求我們盡量的擴充索引而不是建立索引，具體情況還需具體分析。

4、頻繁進行查詢的字段應該建立索引，與其他表進行關聯的字段可以考慮建立索引，查詢中排序的字段可以考慮建立索引以提高排序的效率（這裡舉個例子，很多時候查詢記錄希望按照建立時間倒序傳回，通常有人會這樣做order by create_time desc，但是如果create_time不是索引，而這個表有自增主鍵id，那麼order by id desc傳回結果一樣，但是效率會提高）。

Mysql優化

導緻sql執行慢的原因

1、硬體問題：如網絡速度慢，記憶體不足，I/O吞吐量小，磁盤空間滿了等。

2、沒有使用索引或者索引失效。

3、資料過多（分庫分表）。

4、伺服器或參數設定不當。

分析解決慢sql方法

1、先觀察，開啟慢查詢日志，設定相應的門檻值（比如超過3秒就是慢sql），再生産環境跑個一天，看看哪些sql比較慢。

2、explain和慢sql分析，比如sql語句寫的不好，沒有使用索引或者索引失效，或者sql語句太過複雜，關聯查詢和嵌套子查詢太多等等。

3、Show Profile是比explain更近一步的執行細節，可以查詢到執行每一個SQL都幹了什麼事，這些事分别花了多少秒。

4、找DBA或者運維對Mysql進行伺服器的參數調優。

配置優化

基本配置

• innodb_buffer_pool_size：

  這是安裝完InnoDB後第一個應該設定的選項。

  緩沖池是資料和索引緩存的地方：

  這個值越大越好，這能保證你在大多數的讀取操作時使用的是記憶體而不是硬碟。

  典型的值是5-6GB(8GB記憶體)，20-25GB(32GB記憶體)，100-120GB(128GB記憶體)。

• innodb_log_file_size：

  這是redo日志的大小。

  redo日志被用于確定寫操作快速而可靠并且在崩潰時恢複。

  一直到MySQL 5.5，redo日志的總尺寸被限定在4GB(預設可以有2個log檔案)。

  這在MySQL5.6裡被提高了。

  如果你知道你的應用程式需要頻繁的寫入資料并且你使用的時MySQL5.6，一開始就可以設定成4G。

• max_connections：

  如果你經常看到'Too many connections'錯誤，是因為max_connections的值太低了因為應用程式沒有正确的關閉資料庫連接配接，你需要比預設的151連接配接數更大的值。

  max_connection值被設高了(例如1000或更高)之後一個主要缺陷是當伺服器運作1000個或更高的活動事務時會變的沒有響應。

InnoDB配置

• innodb_file_per_table：

  這項設定告知InnoDB是否需要将所有表的資料和索引存放在共享表空間裡（innodb_file_per_table = OFF） 或者為每張表的資料單獨放在一個.ibd檔案（innodb_file_per_table = ON）。

  每張表一個檔案允許你在drop、truncate或者rebuild表時回收磁盤空間。

  這對于一些進階特性也是有必要的，比如資料壓縮。

  你不想讓每張表一個檔案的主要場景是：

  有非常多的表（比如10k+）。

• innodb_flush_log_at_trx_commit：

  預設值為1，表示InnoDB完全支援ACID特性。

  當你的主要關注點是資料安全的時候這個值是最合适的，比如在一個主節點上。

  但是對于磁盤（讀寫）速度較慢的系統，它會帶來很巨大的開銷，因為每次将改變flush到redo日志都需要額外的fsyncs。

  将它的值設定為2會導緻不太可靠（reliable）因為送出的事務僅僅每秒才flush一次到redo日志，但對于一些場景是可以接受的，比如對于主節點的備份節點這個值是可以接受。

• innodb_flush_method：

  這項配置決定了資料和日志寫入硬碟的方式。

  一般來說，如果你有硬體RAID控制器，并且其獨立緩存采用write-back機制，并有着電池斷電保護，那麼應該設定配置為O_DIRECT；

  否則，大多數情況下應将其設為fdatasync（預設值）

• innodb_log_buffer_size：

  這項配置決定了為尚未執行的事務配置設定的緩存。

  其預設值（1MB）一般來說已經夠用了，但是如果你的事務中包含有二進制大對象或者大文本字段的話，這點緩存很快就會被填滿并觸發額外的I/O操作。

執行計劃Explain

準備資料

CREATE TABLE `user_info` (                `id`   BIGINT(20)  NOT NULL AUTO_INCREMENT,               `name` VARCHAR(50) NOT NULL DEFAULT '',                `age`  INT(11)              DEFAULT NULL,                PRIMARY KEY (`id`),                KEY `name_index` (`name`)              )ENGINE = InnoDB DEFAULT CHARSET = utf8;                      INSERT INTO user_info (name, age) VALUES ('xys', 20);              INSERT INTO user_info (name, age) VALUES ('a', 21);              INSERT INTO user_info (name, age) VALUES ('b', 23);              INSERT INTO user_info (name, age) VALUES ('c', 50);              INSERT INTO user_info (name, age) VALUES ('d', 15);              INSERT INTO user_info (name, age) VALUES ('e', 20);              INSERT INTO user_info (name, age) VALUES ('f', 21);              INSERT INTO user_info (name, age) VALUES ('g', 23);              INSERT INTO user_info (name, age) VALUES ('h', 50);              INSERT INTO user_info (name, age) VALUES ('i', 15);                   CREATE TABLE `order_info` (                `id`           BIGINT(20)  NOT NULL AUTO_INCREMENT,                `user_id`      BIGINT(20)           DEFAULT NULL,                `product_name` VARCHAR(50) NOT NULL DEFAULT '',                `productor`    VARCHAR(30)          DEFAULT NULL,                PRIMARY KEY (`id`),                KEY `user_product_detail_index` (`user_id`, `product_name`, `productor`)              )ENGINE = InnoDB DEFAULT CHARSET = utf8;                          INSERT INTO order_info (user_id, product_name, productor) VALUES (1, 'p1', 'WHH');              INSERT INTO order_info (user_id, product_name, productor) VALUES (1, 'p2', 'WL');              INSERT INTO order_info (user_id, product_name, productor) VALUES (1, 'p1', 'DX');              INSERT INTO order_info (user_id, product_name, productor) VALUES (2, 'p1', 'WHH');              INSERT INTO order_info (user_id, product_name, productor) VALUES (2, 'p5', 'WL');              INSERT INTO order_info (user_id, product_name, productor) VALUES (3, 'p3', 'MA')；              INSERT INTO order_info (user_id, product_name, productor) VALUES (4, 'p1', 'WHH');              INSERT INTO order_info (user_id, product_name, productor) VALUES (6, 'p1', 'WHH');              INSERT INTO order_info (user_id, product_name, productor) VALUES (9, 'p8', 'TE');           

執行explain看看，索引使用情況在possible_keys、key和key_len這三列。

分析explain

• id

id相同，執行順序由上而下

 id不同，值越大越先執行

• select_type

select_type總共有以下幾種類型：

1、SIMPLE：表示查詢不使用UNION或子查詢

2、PRIMARY：表示此查詢是最外層的查詢

3、SUBQUERY：表示此查詢是第一個查詢

4、UNION：表示此查詢是UNION第二或随後的查詢 5、DEPENDENT UNION：UNION中的第二個或後面的查詢語句，取決于外面的查詢 6、UNION RESULT：UNION的結果 7、DEPENDENT SUBQUERY：子查詢中的第一個SELECT，取決于外面的查詢，即子查詢依賴于外面查詢的結果 8、DERIVED：衍生，表示導出表的SELECT

• table

table表示查詢涉及的表或衍生的表

id=1的table derived2表示是由id=2的u和o衍生出來的

• type

type字段比較重要，它是判斷查詢是否高效的重要依據。

1、system：表中隻有一條資料，這種類型是特殊的const類型

2、const：針對主鍵或唯一索引的等号條件進行掃描，最多隻傳回一條資料，查詢速度極快，因為它僅僅讀取一次即可。

3、eq_ref：此類型通常出現在多表join，表示對于前表的每一個結果，都隻能比對到後表的一行結果，且查詢的比較操作通常是=，查詢效率較高。

4、ref：此類型通常是多表join，針對非唯一索引，或者非主鍵索引，或者使用了最左字首規則的索引。

5、range：表示使用索引範圍查詢，通過索引字段範圍擷取表中部分資料記錄，這個類型通常出現在 =, <>, >, >=, <, <=, IS NULL, <=>, BETWEEN, IN() 操作中。

6、index：表示全索引掃描，和ALL類型類似，隻不過All類型是全表掃描，index是掃描所有的索引，而不掃描資料。index 類型通常出現在：所要查詢的資料直接在索引樹中就可以擷取到,而不需要掃描資料。當是這種情況時，Extra 字段 會顯示 Using index。

7、ALL：表示全表掃描，性能最差。當資料量大的時候，對資料庫會是巨大的災難。

• possible_keys

它表示mysql在查詢時，可能使用到的索引。注意：有些索引即使在possible_keys中出現，也不表示真正的會用到，mysql 在查詢時具體使用了哪些索引，由 key 字段決定。

• key

這是mysql在查詢時真正用到的索引

• key_len

表示mysql使用索引的位元組數，這個字段可以判斷組合索引是否完全被使用

• ref

這個字段表示索引的哪一列被使用了，如果可能的話，會是一個常量。

• rows

這也是判斷sql性能好壞的一個重要字段。mysql 查詢優化器根據統計資訊，估算 sql要查找到結果集需要掃描讀取的資料行數。原則上來說,rows越小查詢效率越高。

• extra

explain 中的很多額外的資訊會在 extra 字段顯示，常見的有以下幾種：

1、using filesort ：表示 mysql 需額外的排序操作，不能通過索引順序達到排序效果。一般有 using filesort都建議優化去掉，因為這樣的查詢 cpu 資源消耗大。

2、using index：覆寫索引掃描，表示查詢在索引樹中就可查找所需資料，不用掃描表資料檔案，往往說明性能不錯。

3、using temporary：查詢有使用臨時表, 一般出現于排序， 分組和多表 join 的情況， 查詢效率不高，建議優化。

4、using where ：表明使用了where過濾。

總結

常見的索引原則：

• 選擇唯一性索引：

  唯一性索引的值是惟一的，可以更快速的通過該索引确定某條記錄。

• 為經常需要排序、分組和聯合操作的字段建立索引。
• 為常作為查詢條件的字段建立索引。

• 限制索引的數目：

  索引不是越多越好，太多的索引會使插入和更新變慢，因為需要維護索引樹。

• 盡量使用資料量少的索引，如果索引的值很長，那麼查詢的速度會受到影響。
• 最左字首比對原則，是非常重要的原則。
• 盡量選擇區分度高的列作為索引，區分度的公式是表示字段不重複的比例。

• 索引列不能參與計算，保持列“幹淨”：

  帶函數的查詢不參與索引。