談談InnoDB中的B+樹索引

索引類似于書的目錄，他是幫助我們從大量資料中快速定位某一潭訓者某個范圍資料的一種資料結構，有序陣列，搜索樹都可以被用作索引，MySQL中有三大索引，分別是B+樹索引、Hash索引、全文索引，B+樹索引是最最重要的索引，Hash索引和全文索參考的并不是太多，InnoDB不支持Hash索引，不過存盤引擎內部去定位資料頁時會使用Hash索引, 這不是本文重點，本文將簡單介紹B+樹索引，

B+樹的基本結構

這里不對B+樹做精確定義，直接給出一個B+樹的示意圖并做一些解釋說明，

B+樹是一顆多路平衡查找樹，所有節點稱為頁，頁就是一個資料塊，里面可以放資料，頁是固定大小的，在InnoDB中是16kb，頁里邊的資料是一些key值，n個key可以劃分為n+1個區間，每個區間有一個指向下級節點的指標，每個頁之間以雙向鏈表的方式連接，一層中的key是有序的，以磁盤塊1這個頁為例，他有兩個key，17,35，劃分了三個區間（-無窮,17) p1,[17, 35) p2, [35, +無窮] p3三個區間，也稱扇出為3. p1指向的下級節點里邊的key都是比17小的；p2指向的下級節點里邊的key大于等于17，小于35；p3指向的下級節點里邊的key都大于等于35，

在B+樹查找資料的流程：

例如要在上邊這棵樹查找28，首先定位到磁盤1，通過二分的方式找到他屬于哪個區間，發現是p2，從而定位到磁盤塊3，在磁盤塊3的key里邊做二分查找，找到p2, 定位到磁盤塊8，然后二分找到28這個key，對于資料庫來說，查找一個key最終一定會定位到葉子節點，因為只有葉子節點才包含行記錄或者主鍵key，

插入節點與洗掉節點：

這里不對其詳細流程做介紹，給大家安利一個工具：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html， 這個工具可以以影片方式演示B+樹插入和洗掉的程序，非常直觀，大家可以去動手試試看，如圖所示：

值得注意的是，插入節點時，可能存在頁分裂的情況，洗掉節點時可能存在頁合并的情況，頁的分裂就是指當一個頁容納不了新的key時，分為多個頁的程序，頁合并是指當洗掉一個節點使得頁中的key的數量少到一定程度時與相鄰的頁合在一起成為新的頁，并非一個頁滿插入就會發生頁分裂，會優先通過類似旋轉的方式進行調整，這樣可以避免浪費空間，

下圖演示一種最簡單的頁分裂情況，假設一頁只能放3個key，插入efg時，葉子頁放了了，所以分裂為了兩個頁，并且增加了一層，

資料庫索引的B+樹的顯著特點是高扇出，也就是說一個頁存放的資料多，這樣的好處是樹的高度小，大概在2到4層，高度越小，查找的IO次數越少，

為什么要用B+樹

1. 為什么不用有序陣列

有序陣列可以通過二分的方法查找，查找時間復雜度為O(logn). 他的缺點是插入和洗掉操作代價太高，例如洗掉0位置，那么1到n-1位置的資料都要往前移動，代價O(n)

2. 為什么不用Hash表

存盤引擎內部是有用到Hash表的，這里說的不用Hash表是我們自己建索引時通常不會去建立Hash索引（InnoDB也是不支持的）

Hash表是一種查找效率很高的結構，例如我們Java中的HashMap，基本可以認為他的插入、查詢、洗掉都是O(1)的，

Hash表的底層是一個陣列，插入資料時對資料的hashCode對陣列長度取模，確定他在陣列中的位置，放到陣列里邊，當然這里可能存在你要放的位置被占用了，這個叫碰撞，或者Hash沖突，此時可以用拉鏈法解決，具體就是在沖突的位置建一個鏈表，如下圖所示，BCD三個資料在1位置發生沖突，因此在這里形成了鏈表，Hash表中的查找也很容易，先按插入的方式找到待查找資料在的位置，然后看這個位置有沒有，有就找到了，

Hash表的一個缺點在于對范圍查詢的支持不友好，比如要查[F，K]之間資料，那么就需要將F到K之間的所有值列舉出來計算hashcode，一個一個去hash表查，而且他是無序的，對于order by不友好，因此除非你的查詢就只有等值查詢，否則不可能使用Hash表做索引，

3. 為什么不用搜索二叉樹

不管是不經調整的搜索二叉樹，還是AVL樹、紅黑樹都是搜索二叉樹，他的特點是，對于任意一個節點，他的左孩子（如果有）小于自己，右孩子（如果有）大于自己，

搜索二叉樹的缺點在于，他的高度會隨著節點數增加而增加，我們知道，資料庫索引是很大的，不可能直接裝進記憶體，根節點可能是直接在記憶體的，其他節點存放在磁盤上，查找的時候每往下找一層就需要讀一次磁盤，讀磁盤的效率是比較低的，因此需要減少讀磁盤的次數，那么也就需要減少樹的高度，搜索二叉樹當資料很多時，高度就會很高，那么磁盤IO次數就會很多，效率低下，

另外，資料庫是以頁的形式存盤的，InnoDB存盤引擎默認一頁16K，一頁可以看成一個節點 ，二叉樹一個結點只能存盤一個一個資料.假如索引欄位為int 也就是一個4位元組的數字要占16k的空間，極大的浪費了空間，

4. B+樹有什么特點

• 高扇出，高扇出使得一個節點可以存放更多的資料，整棵樹會更加矮胖，InnoDB中一棵樹的高度在2-4層，這意味著一次查詢只需要1-3次磁盤IO
• 非葉子節點只存放key值（也就是列值），這使得一頁可以存更多的資料，這是高扇出的保證

聚集索引

聚集索引（Clustered index) 也叫聚簇索引、主鍵索引，他的顯著特點是其葉子節點包含行資料（表中的一行），沒錯，InnoDB存盤引擎表資料存在索引中，表是索引組織表，顯然表資料不可能有多份，但是必須有一份，所以聚集索引在一張表有且僅有一個，

什么樣的列會建立聚集索引？

主鍵列，也就是你指定一個表的主鍵就會創建聚集索引，InnoDB中的表必有主鍵列，如果沒有指定主鍵，那么會選擇一個非空唯一列作為主鍵，，否則隱式創建一個列作為主鍵，

假設有如下一張表，a為主鍵，假設一頁只能放三個資料

我們看一看他的聚集索引大概是張什么樣的

其中r1到r4分別表示編號從1到4的行

使用聚集索引的好處：

1. 查詢快，等值和范圍查詢都快，使用索引必然查詢效率會高，使用聚集索引比非聚集索引查詢更快，因為他能直接在葉子節點找到資料，而不需要回表（后文說明）
2. 基于主鍵（聚集索引）的排序快，資料本身就是根據主鍵排序的

下面我們創建一個表看一下

建表陳述句和初始化資料如下：

-- a為主鍵
create table t (
    a int not null,
    b varchar(600),
    c int not null,
    primary key(a)
) engine=INNODB;

insert into t values 
(1,'a',11),
(2, 'b', 12),
(3, 'c', 13),
(4, 'd', 14);

關于explain不太了解的朋友可以參看文末最后一個參考資料

第一個查詢我們在a列上做等值查詢，第二個在c上做等值查詢，從key列可以看到，第一個查詢用到了聚集索引，第二個由于c沒有索引，所以全表掃描

第三個查詢對a做排序,第四個查詢對c列做排序，發現對主鍵的排序不會用filesort.

非聚集索引

非聚集索引（Secondary Index)也叫輔助索引、二級索引、非主鍵索引，非主鍵列創建的索引就是這種索引，他的顯著特點是葉子節點不包括完整的行資料（如果包括，這是一件多么恐怖的事啊！），而是包含行記錄對應的主鍵key，

還是以上邊的表為例，我們在b列創建一個索引，

注意我們只用了b的前10個字符創建索引，所以你能看到Sub_part這列顯示的為10，

此時，idx_b這個索引對應B+樹類似下邊這種形式

可以看到葉子節點中的1,2,3,4其實是主鍵里邊的值

在非聚集索引的查找程序是：

先在非聚集索引樹找到指定key，同時能得到主鍵key，拿著主鍵key到聚集索引里找到對應的行，

拿著主鍵key到聚集索引找行的程序稱為回表，回表有可能避免，詳見后文的覆寫索引，

使用非聚集索引的好處：

1. 占用的空間相比聚集索引小，因為他的葉子節點并不包含完整的行資料，只包含主鍵key
   2. 查詢快，這和聚集索引是類似的，但是效率可能比聚集索引低，因為存在回表程序

缺點：

回表問題，就是要查兩棵索引樹才能找到資料，當然后面會提到并不是所有用非聚集索引查詢都有回表程序，

下邊來看幾個查詢計劃

第一個 key為idx_b, 表明用到了非聚集索引，extra是mysql5.6后做的一個優化，Index Push Down優化，簡言之就是在使用索引查詢時直接通過where條件過濾掉了不符合條件的資料，

第二個演示了按非聚集索引的列做排序的情況，發現會用到filesort，因為沒法直接根據索引排序了，需要回表，

第三個和第二個類似，但是他只選擇了b這個列，發現沒有用filesort.因為不用回表，這個其實就是用到了覆寫索引，

聯合索引

聯合索引就是索引包含多個列的情況，此時的B+樹每個key包含了幾個部分，而不是單一值，

繼續上邊的例子，我們建立b，c列上的聯合索引，

這個索引樹可能的形式如下：

這個圖畫的不太好，其實第二個列在一頁里邊也可以是無序的

每個key有兩個列值組成，葉子節點也是包含了主鍵key，可見這個聯合索引是非聚集索引，當然主鍵索引也可以包含多個列，自然也可以是聯合索引，

聯合索引的作用：

1. 對左邊的列做查詢排序都可以用到這個索引（最左原則）

-- 這里可以假設沒有idx_b這個索引
select * from t where b='a';
select * from t where b='a' and c=11;

2. 左邊的列做等值查詢，對后邊的列做排序友好，因為后邊的已經是排序的

-- 這里可以假設沒有idx_b這個索引
select * from t where b='a' order by  c;

3. 讓索引包含更多資料，走覆寫索引，一旦放到一個列被索引，那么索引樹必包含這個列的資料

對于字串型別的列，也是滿足最左前綴原則，like '%a' 不能命中索引，like 'a%'就可以，

注意下邊這個陳述句用不到索引

select * from t where c=11;

下面看幾個查詢計劃：

先來看一看索引情況

可以看到我們在b，c兩列建立了idx_b_c的聯合索引

1號查詢，條件包含最左列，b列，命中索引

2號查詢，條件不包含最左列，key列顯示為NULL，未命中索引，type為ALL，是全表掃描

3號查詢，對最左列做等值，然后右列做排序，命中了索引

4號查詢，沒有命中索引，用到了filesort

通過這四個查詢我們能夠了解到聯合索引的最左原則是怎么回事了，結合前面提到的聯合索引的樹結構，這個原則是理所當然的，

覆寫索引

覆寫的意思就是包含的意思，覆寫索引就是說索引里包含了你需要的資料，

聚集索引直接包含了行資料，因此是覆寫索引，但是一般不這么說，非聚集索引索引資料里邊有索引列的列值（這不完全對，后面有說明），覆寫索引不是一種新的索引結構，只是恰好你要查的資料就在索引樹里有，這樣就不用回表查詢了（非聚集索引葉子節點只有主鍵key，和索引列值，如果需要其他列值，就需要在通過聚集索引查一次，也就是要走回表），如果使用了覆寫索引，那么查詢計劃的Extra列為Using index.

看幾個具體的例子：

目前的索引情況如下

一些執行計劃

c的索引包含c列和主鍵列的值，所以第一第二個查詢不需要回表，使用了覆寫索引，

c的索引不包含b列，所以當c列索引查b列時就需要回表了

第四個查詢，b列上有索引，索引里邊有b列的值，要查的也是b列，索引覆寫了要查詢的列，所以也使用了覆寫索引，

需要注意的是，不要忘記了主鍵列在所有索引都可以被覆寫到，

測驗發現一個奇怪的現象，這里分享給大伙兒，一個列的varchar給超過767的長度，然后在上邊建索引，會有一個自動的截取，如圖所示：

大家可以思考一下，如果你的索引key只是列的一部分，比如，有一個欄位為varchar(100), 你的索引只包含前50個字符，這個時候能不能走覆寫索引？

Cardinality

使用show index from 表名時， 可以看到有一個Cardinality列，這個列是衡量我們索引有效性的方式，他的含義是索引列中不重復的行數，Cardinality除以表行數稱為索引的選擇性，選擇性越高越好，選擇性小于30%通常認為這個索引建的不好，

Cardinality是一個采樣估計值，會隨機選擇若干頁計算平均不同記錄的個數，然后乘上頁數量，所以可能你每次查到的值不一樣，即使你的表沒有更新，

這個值并不是每一次表更新都會計算的，他會有自己的一個計算策略，

執行如下陳述句會導致這個值的重新計算, 當然也可以配置為不進行計算：

1. analyze table
2. show table status
3. show index

B+樹索引管理

索引的創建：

1. 建表的時候創建

create table t4 
(
    id int primary key,
    a int not null, key(a)
);

2. 通過修改表創建

alter table t4 add index idx_a (a);

3. 通過create index創建

create index idx_a on t4(a);

索引的洗掉：

1. 修改表洗掉

alter table t4 drop index idx_a;

2. drop index語法

drop index idx_a on t4;

索引的查看

show index from t4;

關于索引的思考

學習B+樹索引，最最根本是需要弄清楚各種索引樹的結構是怎樣的，做到“心中有樹”，當看到一條優化策略時，我們就能知道這個優化策略為什么能夠優化，基于我們對索引結構的理解，甚至還可以提出一些新（對你來講是新的，但是可能人家已經寫了或者在用了）的優化策略，例如，我們知道每一個非聚集索引葉子節點都會包含主鍵，因此我們的主鍵應該在滿足業務的情況下盡量小，這樣可以減少所有索引的空間，當然，事實上，每一個列資料型別都應當盡量小，

索引之路，道阻且長，奧利給！

參考資料

• 《MySQL技術內幕-InnoDB存盤引擎》
• https://www.bikan8.cn/186.html
• https://blog.csdn.net/why15732625998/article/details/80388236

標籤：MySQL

上一篇：解決專案node版本不支持，windows多版本的node切換

下一篇：談談InnoDB中的B+樹索引