初識MySQL · 索引

前言：

重溫磁盤

認識索引

為什么這么做，怎么做

重談page

聚簇索引VS非聚簇索引

回表查詢

?索引分類

前言：

前文我們主要是介紹了MySQL的一些基本操作，增刪查改一類的操作都介紹了，并且因為大多數情況下，查詢的頻率遠遠高于其他操作，所以我們在查詢上面，也是花費了一番功夫的。

那么本文，我們來介紹查詢背后的機制——索引，大多數同學第一次接觸到索引的時候，第一感覺肯定是：索引？我們C語言平常學習的索引嗎？類似于數組下標一類的？實則不然，在MySQL的索引大有不同。

我們在平時構建算法的時候，影響效率的不止有算法本身，實際上還有對數據的組織方式，比如同樣是增刪查改，對于順序表和堆來說，二者對于這四個操作的效率肯定大不相同。那么我們在優化算法的時候，就可以著手于對數據的組織方式進行優化。索引的存在就是優化數據的組織方式的。

所以，索引既然是優化的數據的組織方式的，那么，索引不就是數據結構嗎？

重溫磁盤

對于MySQL來說，我們有著和Linux中“萬物皆文件”的一樣的概念，即“一切皆表”，也就是說我們認為MySQL的所有數據都是一張一張的表構成的，不管是我們創建的，還是查詢等操作產生的中間表，我們認為都是表。

即便我們從文件的角度來看，每次當我們創建了表之后，我們在MySQL的目錄也能看到對應的文件生成：

類似于這個，目前我的MySQL版本是8.0的，如果有的同學的MySQL版本是5.7，那么還會看到生成了對應的表結構定義文件.frm，但是不幸的是.frm文件在8.0之后已經被棄用了，原因大致如下：

問題	解釋
一致性差	`.frm` 是單文件，容易與 `.ibd` 不一致
不支持事務	表結構變更不具備事務能力
不支持原子性	DDL 操作不可回滾
無法跨平臺	`.frm` 二進制結構與平臺、版本強耦合
不利于統一管理	數據、索引、結構分散在多個文件中

好了，現在我們有一個認識：MySQL中不管是創建數據庫，還是創建表，都在會實際的文件系統中創建真實的目錄和文件。

那么不就意味著，當我們在MySQL創建表的時候，是要和磁盤等外設打交道的，既然是要和磁盤等外設打交道，那么就要考慮IO的問題了，但是我們同時都知道的，根據馮諾依曼結構體系，處于應用層的MySQL是不能直接和硬盤打交道的，能和硬盤等外設打交道的只有OS，所以問題從MySQL如何和磁盤打交道轉變為了MySQL如果通過OS，間接的和磁盤打交道。

那么我們這個小標題，要解決的問題是OS如何和磁盤打交道的。

基本的磁盤長什么樣我們都知道，由多個盤片摞在一起，并且每個面都有一個磁頭，一個盤片我們可以分出磁道，扇區等單位出來，磁道是一個一個的同心圓，多個磁道構成一個盤面，每個磁道被劃分為一個一個的區域段，這個區域段我們就稱為扇區。

那么有了磁頭Heads，柱面Cylinder（等價于磁道），扇區（Sector），我們就能精準的找到磁盤中的某一個區域，這種磁盤數據定位方式叫做CHS，但是我們要知道，這是早期做法，因為它的數量有嚴格的限制，最多8.4GB左右，所以現在OS早已通過LBA，即Logical Block Addressing 這種邏輯尋址方式進行尋址。不過在早期的時候，磁盤控制器要求只能通過CHS進行訪問，所以早期的時候是有LBA向CHS進行轉換的，不過在當今的時代，基本上已經拋棄了CHS的做法。

但是我們清楚的時候，在第一次介紹文件系統的時候，我們清楚的知道OS和硬盤的數據交互一次性是4KB，也就是說如果我們只是修改一個字節，OS也要在磁盤中給你找到這1字節周圍的4KB數據，然后再修改，這實際上用到了局部性原理，為了提高效率的。

現在我們就清楚了OS和磁盤打交道的基本單位是4KB，那么疑問來了，MySQL通過OS和磁盤打交道的基本單位是多少呢？

答案是：16KB。也就是說MySQL作為應用層服務來說，要交互一次數據，至少都是16KB起步，那么當交互的時候，OS怎么搬來的16KB數據MySQL不管，它只管要就可以了。那么我們如何驗證MySQL交互數據的基本單位是16KB呢？我們可以通過命令show global status like 'innode_page_size'進行查看：

可以看到確實是16KB。

所以我們可以將MySQL和磁盤交互數據的時候應該是這樣的：

其中的buffer pool是MySQL自己申請的緩沖區，相當于TCP中read也有自己的緩沖區一樣。

那么我們從這里得出結論：MySQL通過OS和磁盤交互的基本數據單位是16KB。

認識索引

前文我們花費些許功夫，通過磁盤的CHS，引出了操作系統的LBA，并且結合了OS與磁盤的基本交互是4KB，引出了MySQL和磁盤的交互單位是16KB，但是實際上，事實遠遠沒有這么簡單。那么16KB為什么不簡單我們后面介紹。

對于索引，是通過改變數據的組織方式然后提高MySQL的效率的，所以它的本質，其實就是數據結構，那么我們來理解MySQL的索引是如何工作的。

首先我們建立一張表，這里我們最好加上主鍵約束：

注意我們不是按照id的大小插入數據的，我們是隨機插入的，但是當我們一查看數據的時候，我們發現：

它默認為我們進行了排序。

那么從這個現象，我們引出兩個問題：這個操作是誰做的，為什么要這么做？重談16KB。

為什么這么做，怎么做

先給結論：MySQL自己做的，這么做的目的是為了方便引出目錄。

對于數據庫來說，它的基本數據單位16KB都是要管理起來的，在源碼中，它的基本管理方式是使用鏈表，就像這樣：

那么現在，我們清楚每個16KB里面有數據，還有前后指針，并且在應用層是通過雙向鏈表管理起來的，還發現每個16KB，被稱呼為page。

對于每個page來說，它里面有大量的數據，不同的page鏈接在一起，但是這樣的數據組織方式是雙向鏈表，數據查找的時候，仍然是線性的，可以說在大量數據的時候，這種模式下MySQL會一個一個遍歷的每個page，按照順序遍歷，找到了直接返回即可。

這不就是一個一個的查嘛？那么時間復雜度就是O(N)，這個N在實際的數據中，可能是幾百萬，可能是幾億，那你讓如此脆弱的MySQL完成這么個操作，那它一天啥事也不用干了，光崩潰就可以了。

所以這里，我們引入了目錄：

首先在每個page里面，引入一個目錄：比如一號目錄映射到了1，二號目錄映射到了3，那么我要查2號數據的時候，通過目錄1，找到了1號數據，然后往下走一步，就是2號數據了。這個過程的思想就是通過目錄，一次性干掉大部分數據。通過目錄，能一次性篩選掉其他目錄的所有的指向數據，這個操作實際上就是我們平時讀書的時候，查閱目錄的方式是一樣的。

但是這種操作實際上并不能很好解決問題，它的本質還是線性遍歷的，因為你要使用目錄，但是前置條件是你能遍歷到目錄的那個page，這不還是鏈表的遍歷嗎？

所以在page內已有目錄的基礎之上，我們的解決思路也是簡單的，我們給page也指定目錄，也就是說在數據有目錄的基礎之上，我們對不同的page，也指定上目錄，圖大致是這樣的：

這樣，就能通過第一層目錄，快速定位到對應數據的page的附近，然后遍歷到page再次通過目錄，快速定位到數據的附近，運氣好可以直接命中，這效率提高的就非常多了。

那么現在就可以回答剛才的問題了：MySQL為什么要自己排序？因為目錄指代的順序不能錯亂了，錯亂了目錄無法正確定位。

現在還可以回答一個問題，為什么要使用主鍵約束？不使用可以嗎？

答案是可以，如果我們不使用主鍵，也沒有唯一鍵和Not null的列，InnoDB 會自動生成一個隱藏的6字節的row id作為主鍵，并建立聚簇索引。

所以實際上的page的組織結構就是這樣的，反正遍歷某個目錄的時候，如果太花時間了，再來一個目錄就行，而如果我們仔細一看這個結構，不就是傳說中的B+樹嗎！！所以得出結論，存儲引擎innnodb采取的索引方式是B+樹。那么其他結構為什么不行，比如hash，它不支持范圍查找，因為查找它需要映射，比如紅黑樹，紅黑樹和AVL樹都是近似平衡或者絕對平衡，這就意味著每一層都會有節點，也就是說它很高，而B+樹是矮胖的，層高越低，和系統磁盤交互的次數就很少，所以紅黑樹也pass，至于二叉平衡樹就不用說了。

特性 / 數據結構	B+樹	紅黑樹	AVL樹	Hash
是否支持范圍查詢	? 是，效率高（葉子節點有序且鏈表連接）	? 不直接支持（需中序遍歷）	? 不直接支持	? 不支持
節點扇出（分支數量）	高（每頁存多個key）	低（每節點2個子節點）	低	N/A
樹高度（影響IO次數）	矮（log?N）	較高（log?N）	更高（比紅黑樹高）	無樹結構
適合數據規模	大數據量、磁盤存儲	小數據量、內存結構	小數據量、內存結構	精確查詢、大數據量
插入/刪除性能	中等，代價為平衡和分裂	快速，近似平衡	較慢（頻繁旋轉）	快（無排序要求）
是否順序存儲	? 葉子節點有序、鏈表相連	? 否	? 否	? 否
磁盤友好性	? 高，每個節點可對應一個磁盤頁	? 差，節點少無法利用頁空間	? 差	? 差
典型應用場景	數據庫索引（如 InnoDB）	操作系統調度/平衡集合	編譯器語法樹等	緩存（如 Redis）、哈希索引

重談page

前文我們提及，MySQL的Innodb是通過page這個基本單位來和磁盤進行交互的，那么在如果構建索引的部分，我們發現這個基本單位里面有前后指針，有目錄結構，有各種數據，那么交互的單位真的單純只是一個內存塊的話，是不太能執行這樣的操作，所以對于16KB，我們仍然是：先描述再組織。

即對于每個page都要存入相關信息，然后在buffer pool里面對它們進行一個管理，buffer pool就是MySQL的存儲引擎Innodb的緩沖區，我們也可以在MySQL的配置文件里看到，如果有的時候沒看到也不代表它沒有，MySQL有對應的默認行為的。

那么重歸到Page里面，我們可以非常非常粗略地認為page是這樣的：

struct InnoDBPage {byte file_header[38];       // 文件頭byte page_header[56];       // 頁頭信息Record infimum;             // 最小記錄Record supremum;            // 最大記錄Record user_records[];      // 用戶插入的數據記錄byte free_space[];          // 空閑空間byte page_directory[];      // 槽指針（指向記錄）byte file_trailer[8];       // 文件尾部校驗InnoDBPage* next;InnoDBpage* prev;
};

所以MySQL中的索引，實際上是某個存儲引擎，基于某種特定的組織方式進行的數據排列而已。

聚簇索引VS非聚簇索引

根據上文的描述，我們很明顯能夠發現Innodb的索引的數據本身都是放在最后一層的，目錄都是在其他層，這種數據本身和目錄放在統一結構的索引，我們稱為聚簇索引，對于MyIsam來說，它同樣使用的是B+樹作為索引，但是它和Innodb不同的是它的葉節點存儲的是數據記錄的地址，

也就是說MyIsam的葉結構指向的是數據的地址，那么它的數據本身沒有和目錄放在一起，所以哦我們稱呼這種索引為非聚簇索引。

回表查詢

對于主鍵索引來說，我們發現一個點就是，索引好像只有主鍵才有？那么我們查其他字段怎么辦？能不能給其他列建立一個輔助索引？

當然是可以的，我們可以通過命令create index index_name on table_name(對應列名）來創建對應的輔助索引，就像這樣：

然后我們就可以通過show index from test_3查看對應的索引信息了：

在 InnoDB 中，如果我們通過輔助索引（二級索引）來查詢數據，且查詢的字段不在輔助索引中，就會發生“回表操作”。
假設有三個列：A（主鍵）、B、C，其中我們對 C 建了索引，A 是主鍵。
當我們執行 SELECT B FROM test_table WHERE C = 'xxx' 這個語句時：

MySQL 會先通過 idx_C（C 列上的輔助索引）定位滿足條件的記錄的主鍵 A；
再通過主鍵 A 回到聚簇索引中查找完整的數據行，拿到 B 的值。

因為在 InnoDB 中，輔助索引結構只包含：被索引的列 + 主鍵列，不包含其它字段，所以我們必須“回表”才能拿到未包含的字段（如 B）。

優點	缺點
利用輔助索引快速定位主鍵	回表需要額外查詢，性能下降
輔助索引占用空間小	增加查詢的 I/O 操作
支持多種查詢條件	查詢字段不在索引中時必須回表

我們前文提及了索引的作用就是為了減少系統的IO次數，那么，回表無疑增加了IO次數，所以我們可以通過覆蓋索引解決回表查詢的缺點：

CREATE TABLE test (id INT PRIMARY KEY,name VARCHAR(50),age INT,email VARCHAR(100),INDEX idx_name_age (name, age)
);

SELECT name, age FROM test WHERE name = 'Tom';

即我們讓查詢的數據都在一起，不去主鍵索引里面找就可以了。那么針對于輔助索引來說Innodb是不會所有的葉子節點額外加數據的，因為太浪費空間了。

不過如果使用了覆蓋索引，我們查詢的時候會看到兩個索引，但是實際上是一個：

?索引分類

索引分為主鍵索引，唯一鍵索引，普通索引，全文索引。其中普通索引我們已經通過回表查詢簡單的介紹了，其實普通索引有多種創建方式分別是：

create table user8(id int primary key,name varchar(20),email varchar(30),index(name) --在表的定義最后，指定某列為索引
);

create table user9(
id int primary key,
name varchar(20),
email varchar(30));
alter table user9 add index(name); --創建完表以后指定某列為普通索引

create table user10(
id int primary key,
name varchar(20),  
email varchar(30));-- 創建一個索引名為 idx_name 的索引    
create index idx_name on user10(name);

這種方式都可以成功創建一個輔助索引。

而對于主鍵索引和唯一鍵索引我們可以理解為：創建主鍵索引和唯一鍵索引實際上是創建主鍵和唯一鍵，不管是哪種方式，創建表的時候就指定了主鍵或者創建完之后新增主鍵，Innodb都會創建對應的索引。

不過實際上唯一鍵索引它就是輔助索引，不過多了唯一性約束而已。

類型	是否唯一	是否聚簇	自動建索引	特點
主鍵（PRIMARY）	? 是	? 是	? 是	一張表只能有一個，行按主鍵排序存儲
唯一鍵（UNIQUE）	? 是	? 否	? 是	可有多個，索引中也包含主鍵列作為引用
普通索引（INDEX）	? 否	? 否	手動創建	可有多個，用于優化查詢