目錄概述從二叉樹到B+樹聚集索引非聚集索引聯(lián)合索引和覆蓋索引B+樹索引VS哈希索引普通索引和唯一索引InnoDB VS MyISAM用explain分析索引使用總結(jié)概述

以下是需要創(chuàng)建索引的常見場景，為了對比，創(chuàng)建測試表（a帶索引、d無索引）：

mysql> create table test( --創(chuàng)建測試表 -> id int(10) not null AUTO_INCREMENT, -> a int(10) default null, -> b int(10) default null, -> c int(10) default null, -> d int(10) default null, -> primary key(id), --主鍵索引 -> key idx_a(a), --輔助索引 -> key idx_b_c(b,c) --聯(lián)合索引 -> )engine=InnoDB charset=utf8mb4;Query OK, 0 rows affected, 5 warnings (0.09 sec)mysql> drop procedure if exists insert_test_data;Query OK, 0 rows affected, 1 warning (0.00 sec)mysql> delimiter | --創(chuàng)建存儲過程，插入十萬個數(shù)據(jù)mysql> create procedure insert_test_data() -> begin -> declare i int; -> set i=1; -> while(i<=100000) do -> insert into test(a,b,c,d)values(i,i,i,i); -> set i=i+1; -> end while; -> end |Query OK, 0 rows affected (0.11 sec)mysql> delimiter ;mysql> call insert_test_data(); --執(zhí)行存儲過程Query OK, 1 row affected (11 min 44.13 sec)

數(shù)據(jù)檢索時在條件字段添加索引

聚合函數(shù)對聚合字段添加索引

對排序字段添加索引

為了防止回表添加索引

關(guān)聯(lián)查詢在關(guān)聯(lián)字段添加索引

可以看出使用索引后，對查詢速度優(yōu)化提升是巨大的，本文將從底層到實踐搞懂MySQL索引。

從二叉樹到B+樹

二叉樹：

二叉樹（Binary Tree）是指至多只有兩個子節(jié)點的樹形數(shù)據(jù)結(jié)構(gòu)，沒有父節(jié)點的節(jié)點為根節(jié)點，沒有子節(jié)點的節(jié)點稱為葉子節(jié)點。

二叉搜索樹就是任何節(jié)點的左子節(jié)點小于當(dāng)前節(jié)點鍵值，右子節(jié)點大于當(dāng)前節(jié)點鍵值。

如下圖的二叉搜索樹，我們最多只需要 ⌈ l o g ( n ) ⌉ ⌈log(n)⌉ ⌈log(n)⌉即三次即可匹配到數(shù)據(jù)，而線性查找的話最壞情況需要 n n n次才可匹配到。

但是二叉樹可能會退化成鏈表的情況，如下圖所示，這樣就相當(dāng)于全部掃描了，導(dǎo)致效率不高，為了解決這個問題，需要確保二叉樹一直保持平衡，即平衡二叉樹。

平衡二叉樹：

平衡二叉樹（AVL樹）在滿足二叉樹特性的基礎(chǔ)上，要求每一個節(jié)點的左右子樹高度差不能超過1。它保證了樹構(gòu)造的一個平衡，當(dāng)插入或刪除數(shù)據(jù)導(dǎo)致不平衡時，會進行節(jié)點調(diào)整來保持平衡（具體算法略），確保查找效率。

平衡二叉樹的一個節(jié)點對應(yīng)一個鍵值和數(shù)據(jù)，我們每次查找數(shù)據(jù)就需要從磁盤中讀取一個節(jié)點，也就是我們說的磁盤塊，一個節(jié)點對應(yīng)一個磁盤塊。當(dāng)存儲海量數(shù)據(jù)時，樹的節(jié)點會非常多，會進行很多次的磁盤I/O，查找效率仍是極低的。這就需要一個單節(jié)點能存儲多個鍵值和數(shù)據(jù)的一種平衡樹了。

B樹： B樹（Blance Tree）就是可以單節(jié)點存儲多鍵值和數(shù)據(jù)的平衡樹，每一個節(jié)點我們稱之為頁（Page），即一頁數(shù)據(jù)。每個節(jié)點存儲了更多鍵值和數(shù)據(jù)，把鍵值和數(shù)據(jù)都放在一個頁當(dāng)中，并且每個節(jié)點擁有了更多子節(jié)點，子節(jié)點的個數(shù)一般稱為階。B樹在查找數(shù)據(jù)讀取磁盤的次數(shù)也就大大減少，查找效率比AVL高很多。

如下圖的3階B樹中，查找id=42的數(shù)據(jù)。首先在第一頁里判斷42鍵值大于39，根據(jù)指針P3找到第4頁，再進行比較，小于鍵值45，又根據(jù)指針P1找到第9頁，發(fā)現(xiàn)匹配有匹配的鍵值42，即找到相應(yīng)數(shù)據(jù)。

B+樹：

B+樹是對B樹的進一步優(yōu)化。簡單說就是B+樹的非葉子節(jié)點是不存儲數(shù)據(jù)的，僅存放鍵值。之所以這樣做，是因為數(shù)據(jù)庫中頁的大小是固定的（InnoDB默認16KB），如果不存儲數(shù)據(jù)，就可以存儲更多鍵值，節(jié)點個數(shù)就越大，查找數(shù)據(jù)進行磁盤I/O次數(shù)進一步減少。

另外B+樹的階數(shù)是等于它的鍵值數(shù)量的，如果一個節(jié)點存儲1000鍵值的話，那么只需要三層就可存儲10億數(shù)據(jù)，所以一般查找10億數(shù)據(jù)只需兩次磁盤I/O即可（妙啊）。

同時B+樹葉節(jié)點的數(shù)據(jù)是按順序進行排列的，所以B+樹適合范圍查找、排序查找和分組查找等（B各數(shù)據(jù)分散在節(jié)點上，相對就困難），也就是為什么MySQL采用B+樹索引的原因了。

聚集索引

聚集索引或聚簇索引（Clustered Index）是一種對磁盤上實際數(shù)據(jù)重新組織并按指定的一個或多個列的值排序。數(shù)據(jù)行的物理順序與列值（一般是主鍵那列）的邏輯順序相同，一個表中只能有一個聚集索引（因為只能以一種物理順序存放）。

InnoDB就是用的聚集索引，它的表中的數(shù)據(jù)都會有一個主鍵，即使你不創(chuàng)建主鍵，InnoDB會選取一個Unique鍵作為主鍵，如果表中連Unique鍵都沒有定義的話，InnoDB會為表添加一個名為row_id的隱藏列作為主鍵。

也就是說我們通過InnoDB把數(shù)據(jù)存放到B+樹中，而B+樹中的鍵值就是主鍵，那么在B+樹中的葉子節(jié)點存儲的就是表中的所有數(shù)據(jù)（即該主鍵對應(yīng)的整行數(shù)據(jù)），數(shù)據(jù)文件和索引文件是同一個文件，找到了索引便找到了數(shù)據(jù)，所以我們稱之為聚集索引。

聚集索引更新代價高。插入新行或更新主鍵時會強制將每個被更新的行移動到新的位置（因為要按主鍵排序），而移動行可能還會面臨頁分裂問題（即頁已滿），存儲引擎會將該頁分裂成兩個頁面來容納，頁分裂會占用更多磁盤空間。即索引重排，造成資源浪費。

聚集索引適合范圍查詢。聚集索引查詢速度很快，特別適合范圍檢查（between、<、<=、>、>=）或group by、order by的查詢。因為聚集索引找到包含第一個值的行后，后續(xù)索引值的行在物理上毗連在一起而不必進一步搜索，避免大范圍掃描，大大提高查詢速度。

比如查詢id>=19并且id<30的數(shù)據(jù)：通常根節(jié)點常駐在內(nèi)存中（即頁1已在內(nèi)存），首先在頁1找到了鍵值19及其對應(yīng)指針P2，通過P2讀頁3（此時頁3不在內(nèi)存中，需要從磁盤中加載），然后在頁3查找鍵值19的指針P1，又定位到頁8（同樣的從磁盤加載到內(nèi)存），因為數(shù)據(jù)是按鏈表進行順序鏈接的，可以通過二分找到鍵值19對應(yīng)數(shù)據(jù)。

找到鍵值19后，因為是范圍查找，這時可以在葉子節(jié)點里進行鏈表的查詢，依次遍歷并匹配滿足的條件，一直找到鍵值21，到最后一個數(shù)據(jù)仍不能滿足我們的要求，此時會拿著頁8的指針P去讀取頁9的數(shù)據(jù)，頁9不在內(nèi)存中同樣需要磁盤加載讀進內(nèi)存，然后依此類推，直到匹配到鍵值34時不滿足條件則終止，這就是通過聚集索引查找數(shù)據(jù)的一種方法。

非聚集索引

非聚集索引或非聚簇索引(Secondary Index)就是以主鍵以外的列作為鍵值構(gòu)建的B+樹索引，索引中索引的邏輯順序與磁盤上行的物理存儲順序不同，一個表中可以擁有多個非聚集索引。在InnoDB中處了主鍵索引外其他索引都可以稱為輔助索引或二級索引。

MySQL中的MyISAM使用的就是非聚集索引。表數(shù)據(jù)存儲順序與索引數(shù)據(jù)無關(guān)，葉節(jié)點包含索引字段值及指向數(shù)據(jù)頁數(shù)據(jù)行的邏輯指針（其行數(shù)量與數(shù)據(jù)表數(shù)據(jù)量相同），所以想要查找數(shù)據(jù)還需要根據(jù)主鍵再去聚集索引中查找，根據(jù)聚集索引查找數(shù)據(jù)的過程就稱為回表。

比如定義一張數(shù)據(jù)表test，他是由test.frm、tsst.myd和test.myi組成的：

.frm：記錄了表定義語句. myd：記錄了真實表數(shù)據(jù). myi：記錄了索引數(shù)據(jù)

再檢索數(shù)據(jù)時，先到索引樹test.myi中進行查找，取到數(shù)據(jù)所在test.myd的行位置，拿到數(shù)據(jù)。所以MyISAM引擎的索引文件和數(shù)據(jù)文件是獨立分開的，找到索引不等于找到數(shù)據(jù)，即非聚集索引。

一個表可以有不止一個非聚集索引，實際上每個表最多可以建立249個非聚集索引，但是每次給字段建一個新索引，字段中的數(shù)據(jù)就會被復(fù)制出來一份用于生成索引，因此給表添加索引會增加表的體積，占據(jù)大量磁盤空間和內(nèi)存。所以若磁盤空間和內(nèi)存有限，應(yīng)限制非聚集索引數(shù)量。

此外每當(dāng)你改變了一個建立非聚集索引的表中數(shù)據(jù)時，必須同時更新索引，所以非聚集索引會降低插入和更新速度。

比如查找數(shù)據(jù)36，是用兩個數(shù)字表示，前面那個數(shù)字36代表的是索引的鍵值，后面那個64代表的是數(shù)據(jù)的主鍵。所以說我們找到36后，并沒有拿到數(shù)據(jù)，還要根據(jù)它對應(yīng)的主鍵去到聚集索引表中去查找數(shù)據(jù)。

聯(lián)合索引和覆蓋索引

聯(lián)合索引，顧名思義就是指對表上的多個列聯(lián)合起來進行索引。在創(chuàng)建聯(lián)合索引的時候會根據(jù)業(yè)務(wù)需求，把使用最頻繁的列放在最左邊，因為MySQL的索引查詢會遵循最左前綴匹配的原則。

最左前綴匹配原則即最左優(yōu)先在檢索數(shù)據(jù)的時候，從聯(lián)合索引的最左邊開始匹配，所以當(dāng)我們創(chuàng)建一個聯(lián)合索引的時候，如（a,b,c）相當(dāng)于創(chuàng)建了（a）、（a、b）、（a、b、c）三個索引，這就是最左匹配原則。

覆蓋索引（Covering index）只是特定于具體select語錄而言的聯(lián)合索引。也就是說一個聯(lián)合索引對于某個select語句，通過索引可以直接獲取查詢結(jié)果，而不再需要回表查詢啦，就稱該聯(lián)合索引覆蓋了這條select語句。可以完美的解決非聚集索引回表查詢的問題，但前提是注意查詢時索引的最左匹配原則。

B+樹索引VS哈希索引

原理：

B+樹索引可能需要多次運用二分查找來找到對應(yīng)的數(shù)據(jù)塊。 Hash索引時通過Hash函數(shù)，計算出Hash值，在表中找出對應(yīng)的數(shù)據(jù)。

哈希索引適合大量不同數(shù)據(jù)等值精確查詢，但不支持模糊查詢、范圍查詢，無法用索引來進行排序，也不支持聯(lián)合索引的最左匹配原則，而且有大量重復(fù)鍵值的情況下，還會存在哈希碰撞問題。

普通索引和唯一索引

普通索引的字段可以寫入重復(fù)的值，而唯一索引的字段不能寫入重復(fù)的值。先介紹Insert Buffer和Change Buffer：

Insert Buffer 對于非聚集索引的插入，先判斷插入的非聚集索引是在在緩存池中。若在則直接插入，若不在，則先放入Insert Buffer，之后在一一定頻率和情況鏡像Insert Buffer和輔助索引頁子節(jié)點的合并操作。將多次插入合并為一次操作，減少磁盤離散讀取。要求索引是輔助索引且不唯一。 Change Buffer 是Insert Buffer的升級版，除了插入還支持刪改。通過innodb_change_buffer設(shè)置使用場景，默認為all（還有none、inserts、changes等值），通過innodb_change_buffer_max_size設(shè)置最大使用內(nèi)存占比（默認25%，最大值50%），但在RR隔離級別下會出現(xiàn)死鎖。同樣要求索引是輔助索引且不唯一。

唯一索引使用的是Insert Buffer，因為判斷是否違反唯一性約束，如果都已經(jīng)讀入內(nèi)存了，那直接更新內(nèi)存會更快，就沒必要使用Change Buffer。

普通索引查找到滿足條件的第一個記錄后，繼續(xù)查找下一個記錄直到不滿足條件，對唯一索引來說，查到第一個記錄就返回結(jié)果結(jié)束了。但是InnoDB按頁讀取到內(nèi)存，后面滿足條件的可能都在之前的數(shù)據(jù)頁里，所以普通索引多的幾次內(nèi)存掃描消耗可以忽略不計。

小結(jié)：

數(shù)據(jù)修改時，普通索引可用Change Buffer，而唯一索引不行。 數(shù)據(jù)修改時，唯一索引在RR隔離級別下更容易出現(xiàn)死鎖。 查詢數(shù)據(jù)時，普通索引查到一條記錄還需繼續(xù)判斷下一個記錄，而唯一索引查到后直接返回。 當(dāng)業(yè)務(wù)要求某字段唯一時，若代碼能保證寫入唯一值，則用普通索引，否則用唯一索引。InnoDB VS MyISAM MyISAM InnoDB 數(shù)據(jù)存儲 .frm存儲表定義、.myd數(shù)據(jù)文件、.myi索引文件 不開啟獨立表空間則.frm文件，否則idb文件 索引實現(xiàn) 非聚集索引隨機存儲，只緩存索引 聚集索引順序存儲，緩存索引和數(shù)據(jù) 存儲空間 可被壓縮，存儲空間較小，支持靜態(tài)表、動態(tài)表、壓縮表三種格式 需更多內(nèi)存和存儲 備份恢復(fù) 文件形式存儲可跨平臺，可單獨針對某個表操作 拷貝數(shù)據(jù)文件、備份binlog，體量可能非常大 事務(wù) 不支持（也不支持外鍵，更強調(diào)性能） 支持（包括外鍵、安全、回滾等高級功能） auto_increment 自增長列必須是索引，聯(lián)合索引中可不是第一列 自增長列必須是索引，聯(lián)合索引中也必須是第一列 鎖 支持表級鎖 支持行級鎖 全文索引 支持FULLTEXT類型全文索引 不支持FULLTEXT，但可使用Sphinx插件 表主鍵 允許沒有任何索引和主鍵的表存在 會自動生成隱藏主鍵 總行數(shù) 保存有表的總行數(shù) 沒有保存表的總行數(shù)，會使用輔助索引去遍歷 CRUD 相對適合大量查詢 相對適合增改刪

對比之下，基本上可以考慮使用InnoDB來替代MyISAM了，InnoDB也是目前MySQL的默認引擎，但是具體問題具體分析，也可根據(jù)實際情況對比兩者優(yōu)劣，選擇更合適的。

再擴展一下為什么MyISAM查詢比InnoDB快？

InnoDB要緩存數(shù)據(jù)和索引；MyISAM只緩存索引，換進換出的減少。 InnoDB尋址要映射到塊再到行；MyISAM直接記錄文件的OFFSET，定位更快。 InnoDB還要維護MVCC一致，或許你的場景沒有，但也需要檢查和維護。

MVCC(Multi-Version Concurrency Control)多版本并發(fā)控制

InnoDB為每一行記錄添加了兩個額外的隱藏值（創(chuàng)建版本號、刪除版本號）來實現(xiàn)MVCC，一個記錄行數(shù)據(jù)創(chuàng)建時間，一個記錄行數(shù)據(jù)過期/刪除時間。但是InnoDB并不存儲這些事件發(fā)生的實際時間，相反它只存儲這些事件發(fā)生時的系統(tǒng)版本號。隨著事務(wù)的不斷創(chuàng)建而不斷增長，每個事務(wù)在開始時都會記錄它自己的系統(tǒng)版本號，每個查詢必須去檢查每行數(shù)據(jù)的版本號與事務(wù)的版本號是否相同。也就是說每行數(shù)據(jù)的創(chuàng)建版本號不大于事務(wù)版本號，以確保事務(wù)創(chuàng)建前行數(shù)據(jù)是存在的；行數(shù)據(jù)的刪除版本號大于事務(wù)版本號或未定義，以確保事務(wù)開始前行數(shù)據(jù)沒有被刪除。

用explain分析索引使用

explain可以看SQL語句的執(zhí)行效果，可以幫助選擇更好的索引和優(yōu)化查詢語句，語法：explain select... from ... [where...]。

用前面概述那節(jié)的test表做測試：

mysql> explain select * from test where a=88888;+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+| 1 | SIMPLE | test | NULL | ref | idx_a | idx_a | 5 | const | 1 | 100.00 | NULL |+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+1 row in set, 1 warning (0.03 sec)mysql> explain select b,c from test where b=88888;+----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |+----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+| 1 | SIMPLE | test | NULL | ref | idx_b_c | idx_b_c | 5 | const | 1 | 100.00 | Using index |+----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+1 row in set, 1 warning (0.00 sec)mysql> explain select * from test where a=(select a from test where a=88888);+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+| 1 | PRIMARY | test | NULL | ref | idx_a | idx_a | 5 | const | 1 | 100.00 | Using where || 2 | SUBQUERY | test | NULL | ref | idx_a | idx_a | 5 | const | 1 | 100.00 | Using index |+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+2 rows in set, 1 warning (0.00 sec)

重點看這三列即可：select_type、type、extra。

select_type值 說明 SIMPLE 簡單查詢（不使用關(guān)聯(lián)查詢或子查詢） PRIMARY 包含關(guān)聯(lián)查詢或子查詢 UNION 聯(lián)合查詢中第二個及后面的查詢 DEPENDENT UNION 依賴外部的關(guān)聯(lián)查詢中第二個及以后的查詢 UNION RESULT 聯(lián)合查詢結(jié)果 SUBQUERY 子查詢中的第一個查詢 DEPENDENT SUBQUERY 依賴外部查詢的子查詢中的第一個查詢 DERIVED 用到派生表的查詢 MATERIALIZED 被物化的子查詢 UNCACHEABLE SUBQUERY 子查詢結(jié)果不能被緩存，必須重新評估外層查詢的每一行

type（顯示這一行的數(shù)據(jù)是關(guān)于哪張表的）

type的值 說明 system 查詢對象只有一會數(shù)據(jù) ，最好的情況 const 基于注解或唯一索引查詢，最多返回一條結(jié)果 eq_ref 表連接時基于主鍵或非NULL的唯一索引完成掃描 ref 基于普通索引的等值查詢或表間等值連接 fulltest 全文檢索 ref_or_null 表連接類型是ref，但掃描的索引中可能包含NULL值 index_merge 利用多個索引 unique_subquery 子查詢使用唯一索引 index_subquery 子查詢使用普通索引 range 利用索引進行范圍查詢 index 全索引掃描

extra（解決查詢的詳細信息）

extra的值 說明 Using filesort 用的外部排序而不是索引排序 Using temporary 需創(chuàng)建一個臨時表來存儲結(jié)構(gòu)，通常發(fā)生在對沒有索引的列進行g(shù)roup by時 Using index 使用覆蓋索引 Using where 使用where來處理結(jié)果 Impossible where 對where子句判斷結(jié)果總是false而不能選擇任何數(shù)據(jù) Using join buffer 關(guān)聯(lián)查詢中，被驅(qū)動表的關(guān)聯(lián)字段沒有索引 Using index condition 先條件過濾索引再查數(shù)據(jù) Select tables optimized away 使用聚合函數(shù)來訪問存在索引的某個字段 總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注好吧啦網(wǎng)的更多內(nèi)容!