一、 索引是什么？
1.1. 索引是什么
當(dāng)一張表有 500 萬(wàn)條數(shù)據(jù)，在沒有索引的 name 字段上執(zhí)行一個(gè)查詢：
select * from user_innodb where name =’jim’;
如果 name 字段上面有索引呢？
ALTER TABLE user_innodb DROP INDEX idx_name;
ALTER TABLE user_innodb ADD INDEX idx_name (name);
索引的創(chuàng)建是需要消耗時(shí)間的。
有索引的查詢和沒有索引的查詢相比，效率相差幾十倍。
索引到底是什么呢？為什么可以對(duì)我們的查詢產(chǎn)生這么大的影響？創(chuàng)建索引的時(shí)候做了什么事情？
1.1.1.索引圖解
定義：數(shù)據(jù)庫(kù)索引，是數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）中一個(gè)排序的數(shù)據(jù)結(jié)構(gòu)，以協(xié)助快速查詢、更新數(shù)據(jù)庫(kù)表中數(shù)據(jù)。
數(shù)據(jù)是以文件的形式存放在磁盤上面的，每一行數(shù)據(jù)都有它的磁盤地址。如果沒有索引的話，我們要從 500 萬(wàn)行數(shù)據(jù)里面檢索一條數(shù)據(jù)，只能依次遍歷這張表的全部數(shù)據(jù)（循環(huán)調(diào)用存儲(chǔ)引擎的讀取下一條行數(shù)據(jù)的接口），直到找到這條數(shù)據(jù)。
但是我們有了索引之后，只需要在索引里面去檢索這條數(shù)據(jù)就行了，因?yàn)樗且环N特殊的專門用來(lái)快速檢索的數(shù)據(jù)結(jié)構(gòu)，我們找到數(shù)據(jù)存放的磁盤地址以后，就可以拿到數(shù)據(jù)了。這個(gè)很容易理解，就像我們從一開始 500 頁(yè)的書里面去找特定的一小節(jié)的內(nèi)容，肯定不可能從第一頁(yè)開始翻。
這本書會(huì)有專門的目錄，它可能只有幾頁(yè)的內(nèi)容，它是按頁(yè)碼來(lái)組織的，可以根據(jù)拼音或者偏旁部首來(lái)查找，我們只要確定內(nèi)容對(duì)應(yīng)的頁(yè)碼，就能很快地找到我們想要的 內(nèi)容。
1.1.2.索引類型
那在數(shù)據(jù)表上面，怎么創(chuàng)建一個(gè)索引？建表的時(shí)候指定，或者說(shuō)是 alter table，也可以使用工具。
第一個(gè)是索引的名稱，第二個(gè)是索引的列表，比如我們是要對(duì) id 創(chuàng)建索引還是對(duì) name創(chuàng)建索引。后面前兩個(gè)很重要，一個(gè)叫索引類型。
在 InnoDB 中，索引類型有三種，普通索引、唯一索引（主鍵索引是特殊的唯一索引）、全文索引。
普通（Normal）：也叫非唯一索引，是最普通的索引，沒有任何的限制。
唯一（Unique）：唯一索引要求鍵值不能重復(fù)。另外需要注意的是，主鍵索引是一種特殊的唯一索引，它還多了一個(gè)限制條件，要求鍵值不能為空。主鍵索引用 primay key創(chuàng)建。
全文（Fulltext）：針對(duì)比較大的數(shù)據(jù)，比如我們存放的是消息內(nèi)容，有幾 KB 的數(shù)據(jù)的這種情況，
如果要解決 like 查詢效率低的問題，可以創(chuàng)建全文索引。只有文本類型的字段才可以創(chuàng)建全文索引，比如如 char、varchar、text。
create table m3 (
name varchar(50),
fulltext index(name)
);
select * from fulltext_test where match(content) against(‘馬士兵教育’ IN NATURAL
LANGUAGE MODE);
在 5.6 的版本之后，MyISAM 和 InnoDB 都支持全文索引。但是 MySQL 自帶的全文索引功能使用限制還是比較多，建議用其他的搜索引擎方案。
我們說(shuō)索引是一種數(shù)據(jù)結(jié)構(gòu)，那么它到底應(yīng)該選擇一種什么數(shù)據(jù)結(jié)構(gòu)，才能實(shí)現(xiàn)數(shù)據(jù)的高效檢索呢？
二、 索引存儲(chǔ)模型推演
二分查找
抖音很火的猜數(shù)字游戲，
猜你現(xiàn)在是100以內(nèi)的幾，
最后通過不斷縮小范圍，
鎖定數(shù)字
這個(gè)就是二分查找的一種思想，也叫折半查找，每一次，我們都把候選數(shù)據(jù)縮小了一半。如果數(shù)據(jù)已經(jīng)排過序的話，這種方式效率比較高。
所以第一個(gè)，可以考慮用有序數(shù)組作為索引的數(shù)據(jù)結(jié)構(gòu)。
有序數(shù)組的等值查詢和比較查詢效率非常高，但是更新數(shù)據(jù)的時(shí)候會(huì)出現(xiàn)一個(gè)問題，
可能要挪動(dòng)大量的數(shù)據(jù)（改變 index），所以只適合存儲(chǔ)靜態(tài)的數(shù)據(jù)。
為了支持頻繁的修改，比如插入數(shù)據(jù)，我們需要采用鏈表。鏈表的話，如果是單鏈表，它的查找效率還是不夠高的。
所以，有沒有可以使用二分查找的鏈表呢？
為了解決這個(gè)問題，BST（Binary Search Tree）也就是我們所說(shuō)的二叉查找樹誕生了
2.2. 二叉查找樹（BST Binary Search Tree）
二叉查找樹的特點(diǎn)是什么？
左子樹所有的節(jié)點(diǎn)都小于父節(jié)點(diǎn)，右子樹所有的節(jié)點(diǎn)都大于父節(jié)點(diǎn)。投影到平面以后，就是一個(gè)游戲序列的線性表。
二叉查找樹既能夠?qū)崿F(xiàn)快速查找，又能夠?qū)崿F(xiàn)快速插入。
但是二叉查找樹有一個(gè)問題：
就是它的查找耗時(shí)是和這棵樹的深度相關(guān)的，在最壞的情況下時(shí)間復(fù)雜度會(huì)退化成O(n)。
什么情況是最壞的情況呢？
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
還是剛才的這一批數(shù)字，如果我們插入的數(shù)據(jù)剛好是有序的，5、7、12、14、17、 25。
這個(gè)時(shí)候二叉查找樹變成了什么樣了呢？
它會(huì)變成鏈表（我們把這種樹叫做“斜樹”），這種情況下不能達(dá)到加快檢索速度的目的，和順序查找效率是沒有區(qū)別的。
造成它傾斜的原因是什么呢？
因?yàn)樽笥易訕渖疃炔钐?，這棵樹的左子樹根本沒有節(jié)點(diǎn)——也就是它不夠平衡。
所以，有沒有左右子樹深度相差不是那么大，更加平衡的樹呢？
這個(gè)就是平衡二叉樹，叫做 Balanced binary search trees，或者 AVL 樹（AVL 是發(fā)明這個(gè)數(shù)據(jù)結(jié)果的人的名字縮寫）。
平衡二叉樹（AVL Tree）（左旋、右旋）
平衡二叉樹的定義：左右子樹深度差絕對(duì)值不能超過 1。
比如左子樹的深度就是 2，右子樹的深度只能是 1 或者 3。
這個(gè)時(shí)候我們?cè)侔错樞虿迦?1、2、3、4、5、6，一定是這樣，不會(huì)變成一棵“斜樹”。
那它的平衡是怎么做到的呢？怎么保證左右子樹的深度差不能超過 1 呢？
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
插入 5、7、14。
注意看：當(dāng)我們插入了 5、7 之后，如果按照二叉查找樹的定義，14 肯定是要在 7 的右邊的，這個(gè)時(shí)候根節(jié)點(diǎn) 1 的右節(jié)點(diǎn)深度會(huì)變成 2，但是左節(jié)點(diǎn)的深度是 0，因?yàn)樗鼪]有子節(jié)點(diǎn)，所以就會(huì)違反平衡二叉樹的定義。
那應(yīng)該怎么辦呢？因?yàn)樗怯夜?jié)點(diǎn)下面接一個(gè)右節(jié)點(diǎn)，右-右型，所以這個(gè)時(shí)候我們要把 7提上去，這個(gè)操作叫做左旋。
同樣的，如果我們插入 14、7、5，這個(gè)時(shí)候會(huì)變成左型，就會(huì)發(fā)生右旋操作，把 7提上去。
所以為了保持平衡，AVL 樹在插入和更新數(shù)據(jù)的時(shí)候執(zhí)行了一系列的計(jì)算和調(diào)整的操作。
平衡的問題我們解決了，那么平衡二叉樹作為索引怎么查詢數(shù)據(jù)？
在平衡二叉樹中，一個(gè)節(jié)點(diǎn)，它的大小是一個(gè)固定的單位，作為索引應(yīng)該存儲(chǔ)什么內(nèi)容？
它應(yīng)該存儲(chǔ)這三塊的內(nèi)容：
第一個(gè)是索引的鍵值。比如我們?cè)?id 上面創(chuàng)建了一個(gè)索引，我在用 where id =1 的條件查詢的時(shí)候就會(huì)找到索引里面的東西 id 的這個(gè)鍵值。
第二個(gè)是數(shù)據(jù)的磁盤地址，因?yàn)樗饕淖饔镁褪侨ゲ檎覕?shù)據(jù)的存放的地址。
第三個(gè)，因?yàn)槭嵌鏄?，它必須還要有左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的引用，這樣我們才能找到下一個(gè)節(jié)點(diǎn)。比如大于 26 的時(shí)候，走右邊，到下一個(gè)樹的節(jié)點(diǎn)，繼續(xù)判斷。
如果是這樣存儲(chǔ)數(shù)據(jù)的話，我們來(lái)看一下會(huì)有什么問題。
首先，對(duì)于 InnoDB 來(lái)說(shuō)，索引的數(shù)據(jù)，是放在硬盤上的。查看數(shù)據(jù)和索引的大?。?/p>
select
CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),’MB’) AS data_len,
CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),’MB’) as index_len
from information_schema.TABLES
where table_schema=’yteaher’ and table_name=’user_innodb’;
當(dāng)我們用樹的結(jié)構(gòu)來(lái)存儲(chǔ)索引的時(shí)候，因?yàn)槟玫揭粔K數(shù)據(jù)就要在 Server 層比較是不是需要的數(shù)據(jù)，如果不是的話就要再讀一次磁盤。
訪問一個(gè)節(jié)點(diǎn)就要跟磁盤之間發(fā)生一次 I/O。InnoDB 操作磁盤的最小的單位是一頁(yè)（或者叫一個(gè)磁板塊），大小是 16K(16384 字節(jié))。
那么，一個(gè)樹的節(jié)點(diǎn)就是 16K 的大小。
如果我們一個(gè)節(jié)點(diǎn)只存一個(gè)鍵值+數(shù)據(jù)+引用，例如整形的字段，可能只用了十幾個(gè)或者幾十個(gè)字節(jié)奏，它遠(yuǎn)遠(yuǎn)達(dá)不到 16384 字節(jié)的容量，所以訪問一個(gè)樹節(jié)點(diǎn)，進(jìn)行一次 IO 的時(shí)候，浪費(fèi)了大量的空間。
所以如果每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)太少，從索引中找到我們需要的數(shù)據(jù)，就要訪問更多的節(jié)點(diǎn)，意味著跟磁盤交互次數(shù)就會(huì)過多，消耗的時(shí)間也越多。
比如上面這張圖，我們一張表里面有 6 條數(shù)據(jù)，當(dāng)我們查詢 id=66 的時(shí)候，要查詢兩個(gè)子節(jié)點(diǎn)，就需要跟磁盤交互 3 次，如果我們有幾百萬(wàn)的數(shù)據(jù)呢？這個(gè)時(shí)間更加難以估計(jì)。
所以解決方案是什么呢？
第一個(gè)，就是讓每個(gè)節(jié)點(diǎn)存儲(chǔ)更多的數(shù)據(jù)。
這樣的話，就會(huì)極大地降低樹的深度。我們的樹就從原來(lái)的高瘦高瘦的樣子，變成了矮胖矮胖的樣子。
這個(gè)時(shí)候，我們的樹就不再是二叉了，而是多叉，或者叫做多路。
多路平衡查找樹（B Tree）（分裂、合并）
Balanced Tree
這個(gè)就是我們的多路平衡查找樹，叫做 B Tree（B 代表平衡）。
跟 AVL 樹一樣，B 樹枝節(jié)點(diǎn)和葉子節(jié)點(diǎn)存儲(chǔ)鍵值、數(shù)據(jù)地址、節(jié)點(diǎn)引用。
它有一個(gè)特點(diǎn)：分叉數(shù)（路數(shù)）永遠(yuǎn)比關(guān)鍵字?jǐn)?shù)多 1。比如我們畫的這棵樹，每個(gè)節(jié)點(diǎn)存儲(chǔ)兩個(gè)關(guān)鍵字，那么就會(huì)有三個(gè)指針指向三個(gè)子節(jié)點(diǎn)。
B Tree 的查找規(guī)則是什么樣的呢？
比如我們要在這張表里面查找20。
? 搜索key = 20
? 20>15,排除0X01
? 20<35,排除0X03
? 那么他在15到35之間，
? 命中0X02
? 走磁盤塊3
? 20=20
? 命中
只用了 3 次 IO，這個(gè)是不是比 AVL 樹效率更高呢？
那 B Tree 又是怎么實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)關(guān)鍵字，還保持平衡的呢？跟 AVL 樹有什么區(qū)別？
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
比如 Max Degree（路數(shù)）是 3 的時(shí)候，我們插入數(shù)據(jù) 1、2、3，在插入 3 的時(shí)候，本來(lái)應(yīng)該在第一個(gè)磁盤塊，但是如果一個(gè)節(jié)點(diǎn)有三個(gè)關(guān)鍵字的時(shí)候，意味著有 4 個(gè)指針， 子節(jié)點(diǎn)會(huì)變成 4 路，所以這個(gè)時(shí)候必須進(jìn)行分裂（其實(shí)就是 B+Tree）。把中間的數(shù)據(jù) 2提上去，把 1 和 3 變成 2 的子節(jié)點(diǎn)。
如果刪除節(jié)點(diǎn)，會(huì)有相反的合并的操作。
注意這里是分裂和合并，跟 AVL 樹的左旋和右旋是不一樣的。
我們繼續(xù)插入 4 和 5，B Tree 又會(huì)出現(xiàn)分裂和合并的操作。
從這個(gè)里面也能看到，在更新索引的時(shí)候會(huì)有大量的索引的結(jié)構(gòu)的調(diào)整，所以解釋了為什么不要在頻繁更新的列上建索引，或者為什么不要更新主鍵。
節(jié)點(diǎn)的分裂和合并，其實(shí)就是 InnoDB 頁(yè)（page）的分裂和合并。
B+樹（加強(qiáng)版多路平衡查找樹）
B Tree 的效率已經(jīng)很高了，為什么 MySQL 還要對(duì) B Tree 進(jìn)行改良，最終使用了B+Tree 呢？
總體上來(lái)說(shuō)，這個(gè)時(shí)候 B 樹的改良版本解決的問題比 B Tree 更全面。
我們來(lái)看一下 InnoDB 里面的 B+樹的存儲(chǔ)結(jié)構(gòu)：
MySQL 中的 B+Tree 有兩個(gè)特點(diǎn)：
1、它的關(guān)鍵字的數(shù)量是跟路數(shù)相等的；
2、B+Tree 的根節(jié)點(diǎn)和枝節(jié)點(diǎn)中都不會(huì)存儲(chǔ)數(shù)據(jù)，只有葉子節(jié)點(diǎn)才存儲(chǔ)數(shù)據(jù)。
目前的認(rèn)知：我們這要存放的數(shù)據(jù)是什么？是不是真實(shí)數(shù)據(jù)的地址？
搜索到關(guān)鍵字不會(huì)直接返回，回到最后一層的葉子節(jié)點(diǎn)。比如我們搜索 id=28，雖然在第一層直接命中了，但是數(shù)據(jù)地址在葉子節(jié)點(diǎn)上面，所以我還要繼續(xù)往下搜索，一直到葉子節(jié)點(diǎn)。
3、B+Tree 的每個(gè)葉子節(jié)點(diǎn)增加了一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，它的最后一個(gè)數(shù)據(jù)會(huì)指向下一個(gè)葉子節(jié)點(diǎn)的第一個(gè)數(shù)據(jù)，形成了一個(gè)有序鏈表的結(jié)構(gòu)。
InnoDB 中的 B+Tree 這種特點(diǎn)帶來(lái)的優(yōu)勢(shì)：
1)它是 B Tree 的變種，B Tree 能解決的問題，它都能解決。B Tree 解決的兩大問題是什么？（每節(jié)點(diǎn)存儲(chǔ)更多關(guān)鍵字；路數(shù)更多）
2)掃庫(kù)、掃表能力更強(qiáng)（如果我們要對(duì)表進(jìn)行全表掃描，只需要遍歷葉子節(jié)點(diǎn)就可以了，不需要遍歷整棵 B+Tree 拿到所有的數(shù)據(jù)）
3) B+Tree 磁盤讀寫能力相對(duì)于 B Tree 來(lái)說(shuō)更強(qiáng)（根節(jié)點(diǎn)和枝節(jié)點(diǎn)不保存數(shù)據(jù)區(qū)，所以一個(gè)節(jié)點(diǎn)可以保存更多的關(guān)鍵字，一次磁盤加載的關(guān)鍵字更多）
4)排序能力更強(qiáng)（因?yàn)槿~子節(jié)點(diǎn)上有下一個(gè)數(shù)據(jù)區(qū)的指針，數(shù)據(jù)形成了鏈表）
5)效率更加穩(wěn)定（B+Tree 永遠(yuǎn)是在葉子節(jié)點(diǎn)拿到數(shù)據(jù)，所以 IO 次數(shù)是穩(wěn)定的）
2.6. 索引方式：真的是用的 B+Tree 嗎？
在 Navicat 的工具中，創(chuàng)建索引，索引方式有兩種。
HASH：以 KV 的形式檢索數(shù)據(jù)，也就是說(shuō)，它會(huì)根據(jù)索引字段生成哈希碼和指針，指針指向數(shù)據(jù)。
哈希索引有什么特點(diǎn)呢？
第一個(gè)，它的時(shí)間復(fù)雜度是 O(1)，查詢速度比較快。但是哈希索引里面的數(shù)據(jù)不是按順序存儲(chǔ)的，所以不能用于排序。
第二個(gè)，我們?cè)诓樵償?shù)據(jù)的時(shí)候要根據(jù)鍵值計(jì)算哈希碼，所以它只能支持等值查詢（= IN），不支持范圍查詢（> = <= between and）。
第三個(gè)：如果字段重復(fù)值很多的時(shí)候，會(huì)出現(xiàn)大量的哈希沖突（采用拉鏈法解決），效率會(huì)降低。
需要注意的是，在 InnoDB 中，不能顯示地創(chuàng)建一個(gè)哈希索引（所謂的支持哈希索引指的是Adaptive Hash Index）。
https://dev.mysql.com/doc/refman/5.7/en/create-index.html
memory 存儲(chǔ)引擎可以使用 Hash 索引.
CREATE TABLE `user_memory` (
`id` INT ( 11 ) NOT NULL AUTO_INCREMENT,
`name` VARCHAR ( 255 ) DEFAULT NULL,
`gender` TINYINT ( 1 ) DEFAULT NULL,
`phone` VARCHAR ( 11 ) DEFAULT NULL,
PRIMARY KEY ( `id` ),
KEY `idx_name` ( `name` ) USING HASH
) ENGINE = MEMORY AUTO_INCREMENT = 1 DEFAULT CHARSET = utf8mb4;
如果說(shuō)面試的時(shí)候問到了為什么不用紅黑樹：
紅黑樹的種種約束保證的是什么？最長(zhǎng)路徑不超過最短路徑的二倍。不太適合于數(shù)據(jù)庫(kù)索引。適合內(nèi)存的數(shù)據(jù)機(jī)構(gòu)，例如實(shí)現(xiàn)一致性哈希。
因?yàn)锽 Tree 和B+Tree 的特性，它們廣泛地用在文件系統(tǒng)和數(shù)據(jù)庫(kù)中，例如Windows的 HPFS 文件系統(tǒng)，Oracel、MySQL、SQLServer 數(shù)據(jù)庫(kù)。
三. B+Tree 落地形式
MySQL 數(shù)據(jù)存儲(chǔ)文件
上一節(jié)課我們知道了不同的存儲(chǔ)引擎文件不一樣。
show VARIABLES LIKE ‘datadir’;
每 張 InnoDB 的 表 有 兩 個(gè) 文 件 （ .frm 和 .ibd ） ， MyISAM 的 表 有 三 個(gè) 文 件（.frm、.MYD、.MYI）。
有一個(gè)是相同的文件，.frm。 .frm 是 MySQL 里面表結(jié)構(gòu)定義的文件，不管你建表的時(shí)候選用任何一個(gè)存儲(chǔ)引擎都會(huì)生成，我們就不看了。
我們主要看一下其他兩個(gè)文件是怎么實(shí)現(xiàn)的 MySQL 不同的存儲(chǔ)引擎的索引的。
MyISAM
在 MyISAM 里面，另外有兩個(gè)文件：
一個(gè)是.MYD 文件，D 代表 Data，是 MyISAM 的數(shù)據(jù)文件，存放數(shù)據(jù)記錄，比如我們的user_myisam 表的所有的表數(shù)據(jù)。
一個(gè)是.MYI 文件，I 代表 Index，是 MyISAM 的索引文件，存放索引，比如我們?cè)趇d 字段上面創(chuàng)建了一個(gè)主鍵索引，那么主鍵索引就是在這個(gè)索引文件里面。
也就是說(shuō)，在 MyISAM 里面，索引和數(shù)據(jù)是兩個(gè)獨(dú)立的文件。
那我們?cè)趺锤鶕?jù)索引找到數(shù)據(jù)呢？
MyISAM 的 B+Tree 里面，葉子節(jié)點(diǎn)存儲(chǔ)的是數(shù)據(jù)文件對(duì)應(yīng)的磁盤地址。所以從索引文件.MYI 中找到鍵值后，會(huì)到數(shù)據(jù)文件.MYD 終于獲取相應(yīng)的數(shù)據(jù)記錄。
如果是輔助索引，有什么不一樣
ALTER TABLE user_innodb DROP INDEX index_user_name;
ALTER TABLE user_innodb ADD INDEX index_user_name (name);
在 MyISAM 里面，輔助索引也在這個(gè).MYI 文件里面。
輔助索引跟主鍵索引存儲(chǔ)和檢索數(shù)據(jù)的方式是沒有任何區(qū)別的，一樣是在索引文件里面找到磁盤的址，然后到數(shù)據(jù)文件里面獲取數(shù)據(jù)。
這個(gè)就是 MyISAM 里面的索引以落地的形式。但是在 InnoDB 里面是不一樣的。我們來(lái)看一下。
InnoDB
InnoDB 只有一個(gè)文件（.ibd 文件），那索引放在哪里呢？
在 InnoDB 里面，它是以主鍵為索引來(lái)組織數(shù)據(jù)的存儲(chǔ)的，所以索引文件和數(shù)據(jù)文件是同一個(gè)文件，都在.ibd 文件里面。
在 InnoDB 的主鍵索引的葉子節(jié)點(diǎn)上，它直接存儲(chǔ)了我們的數(shù)據(jù)。
所以，為什么說(shuō)在 InnoDB 中索引即數(shù)據(jù)，數(shù)據(jù)即索引，就是這個(gè)原因。
但是這里會(huì)有一個(gè)問題，一張 InnoDB 的表可能有很多個(gè)多索引，數(shù)據(jù)肯定是只有一份的，那數(shù)據(jù)在哪個(gè)索引的葉子節(jié)點(diǎn)上呢？
這里要給大家介紹一個(gè)叫做聚集索引（聚簇索引）的概念。
就是索引鍵值的邏輯順序跟表數(shù)據(jù)行的物理存儲(chǔ)順序是一致的。（比如字典的目錄是按拼音排序的的，內(nèi)容也是按拼音排序的，按拼音排序的這種目錄就叫聚集索引）。
InnoDB 組織數(shù)據(jù)的方式就是（聚集）索引組織表（clustered index organize table）。如果說(shuō)一張表創(chuàng)建了主鍵索引，那么這個(gè)主鍵索引就是聚集索引，決定數(shù)據(jù)行的物理存儲(chǔ)順序。
問題來(lái)了，那主鍵索引之外的索引，他們存儲(chǔ)什么內(nèi)容，他們的葉子節(jié)點(diǎn)上沒有數(shù)據(jù)怎么檢索完整數(shù)據(jù)？比如在 name 字段上面建的普通索引。
InnoDB 中，主鍵索引和輔助索引是有一個(gè)主次之分的。剛才我們講了，如果有主鍵索引，那么主鍵鍵索引就是聚集索引。其他的索引統(tǒng)一叫做“二級(jí)索引”或者輔助索引。
二級(jí)索引存儲(chǔ)的是輔助索引的關(guān)鍵值，例如在 name 上面建立索引，節(jié)點(diǎn)上存的是 name的值，bobo，jim 等等。
而二級(jí)索引的葉子節(jié)點(diǎn)存的是這條記錄對(duì)應(yīng)的主鍵的值。比如 bobo id=1，jim id=4……
所以，二級(jí)索引檢索數(shù)據(jù)的流程是這樣的：
當(dāng) 我 們 用 name 索 引 查 詢 一 條 記 錄 ， 它 會(huì) 在 二 級(jí) 索 引 的 葉 子 節(jié) 點(diǎn) 找 到name=bobo，拿到主鍵值，也就是 id=，然后再到主鍵索引的葉子節(jié)點(diǎn)拿到數(shù)據(jù)。
從這個(gè)角度來(lái)說(shuō)，因?yàn)橹麈I索引比二級(jí)索引少掃描了一棵 B+Tree，它的速度相對(duì)會(huì)快一些。
但是，如果一張表沒有主鍵怎么辦？那完整的記錄放在哪個(gè)索引的葉子節(jié)點(diǎn)？或者，這張表根本沒有索引呢？數(shù)據(jù)放在哪里？
https://dev.mysql.com/doc/refman/5.7/en/innodb-index-types.html
1、如果我們定義了主鍵(PRIMARY KEY)，那么 InnoDB 會(huì)選擇主鍵作為聚集索引。
2、如果沒有顯式定義主鍵，則 InnoDB 會(huì)選擇第一個(gè)不包含有 NULL 值得唯一索引作為主鍵索引。
3、如果也沒有這樣的唯一索引，那么 InnoDB 會(huì)選擇內(nèi)置 6 字節(jié)長(zhǎng)的 ROWID 作為隱藏的聚集索引，它會(huì)隨著行記錄的寫入而逐漸遞增。
select _rowid name from t2;
四、 索引使用原則
我們?nèi)菀子幸粋€(gè)誤區(qū)，就是在經(jīng)常使用的查詢條件上都建立索引，索引越多越好，那到底是不是這樣樣呢？
列的離散（sàn）度
第一個(gè)叫做列的離散度，我們先來(lái)看一下列的離散度的公式：
count(distinct(column_name)) : count(*)，列的全部不同值和所有數(shù)據(jù)行的比例。數(shù)據(jù)行數(shù)相同的情況下，分子越大，分子的離散度就越高。
簡(jiǎn)單來(lái)說(shuō)，如果列的重復(fù)值越多，離散度就越低，重復(fù)值越少，離散度就越高。
我們不建議大家在離散度低的字段上建立索引。
沒有索引的時(shí)候查一遍：
SELECT * FROM `user_innodb` WHERE gender = 0;
建立索引之后再查一遍：
ALTER TABLE user_innodb DROP INDEX idx_user_gender;
ALTER TABLE user_innodb ADD INDEX idx_user_gender (gender); — 耗時(shí)比較久
SELECT * FROM `user_innodb` WHERE gender = 0;
發(fā)現(xiàn)消耗的時(shí)間更久了。
聯(lián)合索引最左匹配
前面我們說(shuō)的都是針對(duì)單列創(chuàng)建的索引，但有的時(shí)候我們的多條件查詢的時(shí)候，也會(huì)建立聯(lián)合索引，舉例：查詢成績(jī)的時(shí)候必須同時(shí)輸入身份證和考號(hào)。
單列索引可以看成是特殊的聯(lián)合索引。
比如我們?cè)?user 表上面，給 name 和 phone 建立了一個(gè)聯(lián)合索引。
ALTER TABLE user_innodb DROP INDEX comidx_name_phone;
ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);
聯(lián)合索引在 B+Tree 中是復(fù)合的數(shù)據(jù)結(jié)構(gòu)，它是按照從左到右的順序來(lái)建立搜索樹的（name 在左邊，phone 在右邊）。
從這張圖可以看出來(lái)，name 是有序的，phone 是無(wú)序的。當(dāng) name 相等的時(shí)候，phone 才是有序的。
這個(gè)時(shí)候我們使用 where name= ‘jim’ and phone = ‘136xx ‘去查詢數(shù)據(jù)的時(shí)候，B+Tree 會(huì)優(yōu)先比較 name 來(lái)確定下一步應(yīng)該搜索的方向，往左還是往右。如果 name相同的時(shí)候再比較 phone。但是如果查詢條件沒有 name，就不知道第一步應(yīng)該查哪個(gè)節(jié)點(diǎn)，因?yàn)榻⑺阉鳂涞臅r(shí)候 name 是第一個(gè)比較因子，所以用不到索引。
什么時(shí)候用到聯(lián)合索引
所以，我們?cè)诮⒙?lián)合索引的時(shí)候，一定要把最常用的列表放在最左邊。
比如下面的三條語(yǔ)句，大家覺得用到聯(lián)合索引了嗎？
使用兩個(gè)字段，用到聯(lián)合索引：
EXPLAIN SELECT * FROM user_innodb WHERE name= ‘jim’ AND phone = ‘150000000000’;
使用左邊的 name 字段，用到聯(lián)合索引：
EXPLAIN SELECT * FROM user_innodb WHERE name= ‘權(quán)亮’
使用右邊的 phone 字段，無(wú)法使用索引，全表掃描：
EXPLAIN SELECT * FROM user_innodb WHERE phone = ‘15200000000’
如何創(chuàng)建聯(lián)合索引
有一天我們的 DBA 找到我，說(shuō)我們的項(xiàng)目里面有兩個(gè)查詢很慢，按照我們的想法，一個(gè)查詢創(chuàng)建一個(gè)索引，所以我們針對(duì)這兩條 SQL 創(chuàng)建了兩個(gè)索引，這種做法覺得正確嗎？
CREATE INDEX idx_name on user_innodb(name);
CREATE INDEX idx_name_phone on user_innodb(name,phone);
當(dāng)我們創(chuàng)建一個(gè)聯(lián)合索引的時(shí)候，按照最左匹配原則，用左邊的字段 name 去查詢的時(shí)候，也能用
到索引，所以第一個(gè)索引完全沒必要。
相當(dāng)于建立了兩個(gè)聯(lián)合索引(name),(name,phone)。
如果我們創(chuàng)建三個(gè)字段的索引 index(a,b,c)，相當(dāng)于創(chuàng)建三個(gè)索引：
index(a)
index(a,b)
index(a,b,c)
用 where b=? 和 where b=? and c=? 是不能使用索引的。
這里就是 MySQL 里面聯(lián)合索引的最左匹配原則。
覆蓋索引
什么叫回表：
非主鍵索引，我們先通過索引找到主鍵索引的鍵值，再通過主鍵值查出索引里面的字有的數(shù)據(jù)，它比基于主鍵索引的查詢多掃描了一棵索引樹，這個(gè)過程就叫回表。
例如：
select * from user_innodb where name = ‘bobo’;
在輔助索引里面，不管是單列索引還是聯(lián)合索引，如果 select 的數(shù)據(jù)列只用從索引中就能夠取得，不必從數(shù)據(jù)區(qū)中讀取，這時(shí)候使用的索引就叫做覆蓋索引，這樣就避免了回表。
Extra 里面值為“Using index”代表使用了覆蓋索引。
我們先來(lái)創(chuàng)建一個(gè)聯(lián)合索引：
— 創(chuàng)建聯(lián)合索引
ALTER TABLE user_innodb DROP INDEX comixd_name_phone;
ALTER TABLE user_innodb add INDEX `comixd_name_phone` (`name`,`phone`);
這三個(gè)查詢語(yǔ)句都用到了覆蓋索引：
EXPLAIN SELECT name,phone FROM user_innodb WHERE name= ‘jim’ AND phone = ‘
13666666666′;
EXPLAIN SELECT nameFROM user_innodb WHERE name= ‘jim’ AND phone = ‘
13666666666′;
EXPLAIN SELECT phone FROM user_innodb WHERE name= ‘jim’ AND phone = ‘
13666666666′;
select * ，此處用不到覆蓋索引。
如果改成只用 where phone = 查詢呢？大家自己試試。按照我們之前的分析，它是用不到索引的。
實(shí)際上可以用到覆蓋索引！覆蓋的索引跟是否可能使用索引沒有直接關(guān)系。
很明顯，因?yàn)楦采w的索引減少了 IO 次數(shù)多，減少了數(shù)據(jù)的訪問量，可以大大地提升查詢效率。
五. 索引的創(chuàng)建與使用
因?yàn)樗饕龑?duì)于改善查詢性能的作用是巨大的，所以我們的目標(biāo)是盡量使用索引。
在什么字段上索引？
1、在用于 where 判斷 order 排序和 join 的（on）字段上創(chuàng)建索引
2、索引的個(gè)數(shù)不要過多。
——浪費(fèi)空間，更新變慢。
3、區(qū)分度低的字段，例如性別，不要建索引。
——離散度太低，導(dǎo)致掃描行數(shù)過多。
4、頻繁更新的值，不要作為主鍵或者索引。
——頁(yè)分裂
5、隨機(jī)無(wú)序的值，不建議作為主鍵索引，例如身份證、UUID。
——無(wú)序，分裂
6、創(chuàng)建復(fù)合索引，而不是修改單列索引
什么時(shí)候索引失效？
1、索引列上使用函數(shù)（replaceSUBSTRCONCATsum count avg）、表達(dá)式
計(jì)算（+ – * /）：https://www.runoob.com/mysql/mysql-functions.html
explain SELECT * FROM `t2` where id+1 = 4;
2、字符串不加引號(hào)，出現(xiàn)隱式轉(zhuǎn)換
ALTER TABLE user_innodb DROP INDEX comidx_name_phone;
ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);
explain SELECT * FROM `user_innodb` where name = 136;
explain SELECT * FROM `user_innodb` where name = ‘136’;
3、like 條件中前面帶%
where 條件中 like abc%，like %2673%，like %888 都用不到索引嗎？為什么？
explain select *from user_innodb where name like ‘wang%’;
explain select *from user_innodb where name like ‘%wang’;
過濾的開銷太大。這個(gè)時(shí)候可以用全文索引。
4、負(fù)向查詢
NOT LIKE 不能：
explain select *from employees where last_name not like ‘wang’
!= （）和 NOT IN 在某些情況下可以說(shuō)：
explain select *from employees where emp_no not in (1) explain select *from
employees where emp_no 1
注意跟數(shù)據(jù)庫(kù)版本、數(shù)據(jù)量、數(shù)據(jù)選擇度都有關(guān)系。
其實(shí)，用不用索引，最終都是優(yōu)化器說(shuō)了算。
優(yōu)化器是基于什么的優(yōu)化器？
基于 cost 開銷（Cost Base Optimizer），它不是基于規(guī)則（Rule-Based Optimizer），也不是基于語(yǔ)義。怎么樣開銷就怎么來(lái)。
https://docs.oracle.com/cd/B10501_01/server.920/a96533/rbo.htm#38960
https://dev.mysql.com/doc/refman/5.7/en/cost-model.html
使用索引有基本原則，但是沒有具體細(xì)則，沒有什么情況一定用索引，什么情況一定不用索引的規(guī)則則
