一、前言

之前了解過Mysql中索引的數(shù)據(jù)結(jié)構(gòu)，但是看得非常淺顯，僅僅知道索引底層實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)是 B+ tree，以及B+ tree 簡單的增加節(jié)點和刪除節(jié)點。但是對一些細節(jié)問題依然不太明白，在此借助一篇講解比較詳細的文章來進行學(xué)習(xí)。

原文：從頭帶你捋一遍 MySQL 索引結(jié)構(gòu)，索引沒你想的那么難！

二、頁的引入

2.1 從一個簡單的表開始

create table user(
    id int primary key,
    age int,
    height int,
    weight int,
    name varchar(32)
)engine = innoDb;

INSERT INTO user(id,age,height,weight,name)VALUES(2,1,2,7,'小吉');
INSERT INTO user(id,age,height,weight,name)VALUES(5,2,1,8,'小尼');
INSERT INTO user(id,age,height,weight,name)VALUES(1,4,3,1,'小泰');
INSERT INTO user(id,age,height,weight,name)VALUES(4,1,5,2,'小美');
INSERT INTO user(id,age,height,weight,name)VALUES(3,5,6,7,'小蔡');

執(zhí)行后，我們查一下表中的數(shù)據(jù)：

select * from user;

表中數(shù)據(jù)

可以看到，數(shù)據(jù)已經(jīng)完整地放到了我們創(chuàng)建的user表中。
但是不知道大家發(fā)現(xiàn)了什么沒有，好像發(fā)生了一件非常詭異的事情，我們插入的數(shù)據(jù)好像亂序了。MySQL好像悄悄的給我們按照id排了個序。

為什么會出現(xiàn)MySQL在我們沒有顯式排序的情況下，默默幫我們排了序呢？它是在什么時候進行排序的？

此時先不做解答，我們帶著這這兩個問題繼續(xù)向后看。

2.2 頁的引入

當(dāng)以上表和數(shù)據(jù)創(chuàng)建好后，Mysql中會形成這樣一個頁：

image.png

上圖就是我們目前為止所理解的頁的結(jié)構(gòu)，他包含我們的多條數(shù)據(jù)，其中的數(shù)據(jù)鏈表部分就是 User Record。另外，MySQL的數(shù)據(jù)以頁組成，那么它有指向下一頁的指針和指向上一頁的指針。

那么說到這里，其實可以回答第一個問題了，MySQL實際上就是在我們插入數(shù)據(jù)的時候，就幫我們在頁中排好了序，至于為什么要排序，這里先賣個關(guān)子，接著往下看。

三、 排序?qū)π阅艿奶嵘?/h2>

上文中我們提了一個問題，為什么數(shù)據(jù)庫在插入數(shù)據(jù)時要對其進行排序呢？我們按正常順序插入數(shù)據(jù)不是也挺好的嗎？
這就要涉及到一個數(shù)據(jù)庫查詢流程的問題了，無論如何，我們是絕對不會去平白無故地在插入數(shù)據(jù)時增加一個操作來讓流程復(fù)雜化的，所以插入數(shù)據(jù)時排序一定有其目的，就是優(yōu)化查詢的效率。
而我們不難看出，頁內(nèi)部存放數(shù)據(jù)的模塊，實質(zhì)上就是一個鏈表的結(jié)構(gòu)，鏈表的特點也就是增刪快，查詢慢，所以優(yōu)化查詢的效率是必須的。

3.1 單頁內(nèi)對性能的提升

3.1.1 Mysql保證插入時對 id 有序

還是基于我們第一節(jié)中的那張頁圖來談，我們插入了五條數(shù)據(jù)，id分別是從1-5，那么假設(shè)我要找一個表中不存在的id，假設(shè)id=-1，那么現(xiàn)在的查詢流程就是：

將id=1的這一整頁數(shù)據(jù)取出，進行逐個比對，那么當(dāng)我們找到id=1的這條數(shù)據(jù)時，發(fā)現(xiàn)這個id大于我們所需要找的哪個id，由于數(shù)據(jù)庫在插入數(shù)據(jù)時，已經(jīng)進行過排序了，那么在id=1的數(shù)據(jù)后面，都是id>1的數(shù)據(jù)，所以我們就不需要再繼續(xù)往下尋找了。

如果在插入時沒有進行排序，那毋庸置疑，我們需要再繼續(xù)往下進行尋找，逐條查找直到到結(jié)尾也沒有找到這條數(shù)據(jù)，才能返回不存在這條數(shù)據(jù)。

看似這種程度的排序已經(jīng)提高了查詢的效率，但是這樣依然存在一些問題。我們再回到這張圖：

image.png

我們不難看出，在現(xiàn)階段我們了解的頁模式中，只有一個功能，就是在查詢某條數(shù)據(jù)的時候直接將一整頁的數(shù)據(jù)加載到內(nèi)存中，以減少硬盤IO次數(shù)，從而提高性能。

但是，我們也可以看到，現(xiàn)在的頁模式內(nèi)部，實際上是采用了鏈表的結(jié)構(gòu)，前一條數(shù)據(jù)指向后一條數(shù)據(jù)，本質(zhì)上還是通過數(shù)據(jù)的逐條比較來取出特定的數(shù)據(jù)。

那么假設(shè)，我們這一頁中有一百萬條數(shù)據(jù)，我們要查的數(shù)據(jù)正好在最后一個，那么我們是不是一定要從前往后找到這一條數(shù)據(jù)呢？

如果是這樣，我們需要查找的次數(shù)就達到了一百萬次，即使是在內(nèi)存中查找，這個效率也是不高的。那么，有什么辦法來優(yōu)化這種情況下的查找效率呢？

3.1.2 通過頁中的目錄來提高查詢效率

我們可以打個比方，我們在看書的時候，如果要找到某一節(jié)，而這一節(jié)我們并不知道在哪一頁，我們是不是就要從前往后，一節(jié)一節(jié)地去尋找我們需要的內(nèi)容的頁碼呢？

答案是否定的，因為在書的前面，存在目錄，它會告訴你這一節(jié)在哪一頁，例如，第一節(jié)在第1頁、第二節(jié)在第13頁。在數(shù)據(jù)庫的頁中，實際上也使用了這種目錄的結(jié)構(gòu)，這就是頁目錄。

那么引入頁目錄之后，我們所理解的頁結(jié)構(gòu)，就變成了這樣：

image.png

分析一下這張圖，實際上頁目錄就像是我們在看書的時候書本的目錄一樣，目錄項1就相當(dāng)于第一節(jié)，目錄項2就相當(dāng)于第二節(jié)，而每一條數(shù)據(jù)就相當(dāng)于書本的每一頁

這張圖就可以解釋成，第一節(jié)從第一頁開始，第二節(jié)從第三頁開始，而實際上，每個目錄項會存放自己這個目錄項當(dāng)中最小的id，也就是說，目錄項1中會存放1，而目錄項2會存放3。

那么對比一下數(shù)據(jù)庫在沒有頁目錄時候的查找流程，假設(shè)要查找id=3的數(shù)據(jù)，在沒有頁目錄的情況下，需要查找id=1、id=2、id=3，三次才能找到該數(shù)據(jù)，而如果有頁目錄之后，只需要先查看一下id=3存在于哪個目錄項下，然后直接通過目錄項進行數(shù)據(jù)的查找即可

如果在該目錄項下沒有找到這條數(shù)據(jù)，那么就可以直接確定這條數(shù)據(jù)不存在，這樣就大大提升了數(shù)據(jù)庫的查找效率，但是這種頁目錄的實現(xiàn)，首先就需要基于數(shù)據(jù)是在已經(jīng)進行過排序的的場景下，才可以發(fā)揮其作用。

所以看到這里，大家應(yīng)該明白第二個問題了，為什么數(shù)據(jù)庫在插入時會進行排序，這才是真正發(fā)揮排序的作用的地方。

3.2 多個頁對性能的提升

3.2.1 Mysql對多個頁的組織關(guān)系

在上文中，我們基本上說明白了MySQL數(shù)據(jù)庫中頁的概念，以及它是如何基于頁來減少磁盤IO次數(shù)的，以及排序是如何優(yōu)化查詢的效率的。

那么我們現(xiàn)在再來思考第三個問題：在開頭說頁的概念的時候，我們有說過，MySQL中每一頁的大小只有16KB，不會隨著數(shù)據(jù)的插入而自動擴容，所以這16KB不可能存下我們所有的數(shù)據(jù)，那么必定會有多個頁來存儲數(shù)據(jù)，那么在多頁的情況下，MySQL中又是怎么組織這些頁的呢？

針對這個問題，我們繼續(xù)來畫出我們現(xiàn)在所了解的多頁的結(jié)構(gòu)圖：

image.png

可以看到，在數(shù)據(jù)不斷變多的情況下，MySQL會再去開辟新的頁來存放新的數(shù)據(jù)，而每個頁都有指向下一頁的指針和指向上一頁的指針，將所有頁組織起來（這里修改了一下數(shù)據(jù)，將每一列的數(shù)據(jù)都放到了數(shù)據(jù)區(qū)中，其中第一個空格之前的代表id），第一頁中存放id為1-5的數(shù)據(jù)，第二頁存放id為6-10的數(shù)據(jù)，第三頁存放id為11-15的數(shù)據(jù)

需要注意的是：在開辟新頁的時候，我們插入的數(shù)據(jù)不一定是放在新開辟的頁上，而是要進行所有頁的數(shù)據(jù)比較，來決定這條插入的數(shù)據(jù)放在哪一頁上，而完成數(shù)據(jù)插入之后，最終的多頁結(jié)構(gòu)就會像上圖中畫的那樣。

在多頁模式下，MySQL終于可以完成多數(shù)據(jù)的存儲了，就是采用開辟新頁的方式，將多條數(shù)據(jù)放在不同的頁中，然后同樣采用鏈表的數(shù)據(jù)結(jié)構(gòu)，將每一頁連接起來。

那么可以思考第四個問題：多頁情況下是否對查詢效率有影響呢？

3.2.2 通過目錄頁（索引頁）提高性能

針對這個問題，既然問出來了，那么答案是肯定的，多頁會對查詢效率產(chǎn)生一定的影響，影響主要就體現(xiàn)在，多頁其本質(zhì)也是一個鏈表結(jié)構(gòu)，只要是鏈表結(jié)構(gòu)，查詢效率一定不會高。

假設(shè)數(shù)據(jù)又非常多條，數(shù)據(jù)庫就會開辟非常多的新頁，而這些新頁就會像鏈表一樣連接在一起，當(dāng)我們要在這么多頁中查詢某條數(shù)據(jù)時，它還是會從頭節(jié)點遍歷到存在我們要查找的那條數(shù)據(jù)所存在的頁上，我們好不容易通過頁目錄優(yōu)化了頁中數(shù)據(jù)的查詢效率，現(xiàn)在又出現(xiàn)了以頁為單位的鏈表，這不是前功盡棄了嗎？

我們對比頁內(nèi)數(shù)據(jù)區(qū)，來分析如何優(yōu)化多頁結(jié)構(gòu)。在單頁時，我們采用了頁目錄的目錄項來指向一行數(shù)據(jù)，這條數(shù)據(jù)就是存在于這個目錄項中的最小數(shù)據(jù)，那么就可以通過頁目錄來查找所需數(shù)據(jù)。

所以對于多頁結(jié)構(gòu)也可以采用這種方式，使用一個目錄項來指向某一頁，而這個目錄項存放的就是這一頁中存放的最小數(shù)據(jù)的索引值。和頁目錄不同的地方在于，這種目錄管理的級別是頁，而頁目錄管理的級別是行。

那么分析到這里，我們多頁模式的結(jié)構(gòu)就會是下圖所示的這樣：

image.png

存在一個目錄頁來管理頁目錄，目錄頁中的數(shù)據(jù)存放的就是指向的那一頁中最小的數(shù)據(jù)。

這里要注意的一點是：其實目錄頁的本質(zhì)也是頁，普通頁中存的數(shù)據(jù)是項目數(shù)據(jù)，而目錄頁中存的數(shù)據(jù)是普通頁的地址。

假設(shè)我們要查找id=19的數(shù)據(jù)，那么按照以前的查找方式，我們需要從第一頁開始查找，發(fā)現(xiàn)不存在那么再到第二頁查找，一直找到第四頁才能找到id=19的數(shù)據(jù)

但是如果有了目錄頁，就可以使用id=19與目錄頁中存放的數(shù)據(jù)進行比較，發(fā)現(xiàn)19大于任何一條數(shù)據(jù)，于是進入id=16指向的頁進行查找，直接然后再通過頁內(nèi)的頁目錄行級別的數(shù)據(jù)的查找，很快就可以找到id為19的數(shù)據(jù)了。

隨著數(shù)據(jù)越來越多，這種結(jié)構(gòu)的效率相對于普通的多頁模式，優(yōu)勢也就越來越明顯。

回歸正題，相信有對MySQL比較了解的同學(xué)已經(jīng)發(fā)現(xiàn)了，我們畫的最終的這幅圖，就是MySQL中的一種索引結(jié)構(gòu)——B+樹。

四、B+樹

我們接著往下聊，我們將我們畫的存在目錄頁的多頁模式圖宏觀化，可以形成下面的這張圖：

image.png

對于它的優(yōu)勢：

• 由于葉子節(jié)點上存放了所有的數(shù)據(jù)，并且有指針相連，每個葉子節(jié)點在邏輯上是相連的，所以對于范圍查找比較友好。
• B+樹的所有數(shù)據(jù)都在葉子節(jié)點上，所以B+樹的查詢效率穩(wěn)定，一般都是查詢3次。
• B+樹有利于數(shù)據(jù)庫的掃描。
• B+樹有利于磁盤的IO，因為他的層高基本不會因為數(shù)據(jù)擴大而增高（三層樹結(jié)構(gòu)大概可以存放兩千萬數(shù)據(jù)量。

五、頁的完整結(jié)構(gòu)

Page是Innodb存儲的最基本結(jié)構(gòu)，也是Innodb磁盤管理的最小單位，與數(shù)據(jù)庫相關(guān)的所有內(nèi)容都存儲在Page結(jié)構(gòu)里。Page分為幾種類型：數(shù)據(jù)頁（B-Tree Node），Undo頁（Undo Log Page），系統(tǒng)頁（System Page），事務(wù)數(shù)據(jù)頁（Transaction System Page）等；每個數(shù)據(jù)頁的大小為16kb，每個Page使用一個32位（一位表示的就是0或1）的int值來表示，正好對應(yīng)Innodb最大64TB的存儲容量(16kb * 2^32=64tib)
一個Page的基本結(jié)構(gòu)如下：

頁的基本結(jié)構(gòu)

5.1 頭部數(shù)據(jù)

每個page都有通用的頭和尾，但是中部的內(nèi)容根據(jù)page的類型不同而發(fā)生變化，頭部的數(shù)據(jù)如下：

頁頭結(jié)構(gòu)

page頭部保存了兩個指針，分別指向前一個Page和后一個Page，頭部還有Page的類型信息和用來唯一標(biāo)識Page的編號。根據(jù)這個指針分布可以想象到Page鏈接起來就是一個雙向鏈表

鏈表結(jié)構(gòu)

5.2 主體數(shù)據(jù)

在Page的主體部分，主要關(guān)注數(shù)據(jù)和索引的存儲，他們都位于User Records部分，User Records占據(jù)Page的大部分空間，User Records由一條條的Record組成，每條記錄代表索引樹上的一個節(jié)點（非葉子節(jié)點和葉子節(jié)點）；在一個單鏈表的內(nèi)部，單鏈表的頭尾由兩條記錄來表示，字符串形式的“ Infimum”代表開頭，“Supremum”表示結(jié)尾；System Record 和 User Record是兩個平行的段；
Innodb中存在四種不同的Record，分別是：

• 主鍵索引樹非葉子節(jié)點
• 主鍵索引樹葉子節(jié)點
• 輔助鍵索引樹非葉子節(jié)點
• 輔助鍵索引樹葉子節(jié)點

這四種節(jié)點Record格式上有差異，但是內(nèi)部都存儲著Next指針指向下一個Record

image.png

這里表達的幾個核心點：1. User Record 和 System Record 是段；2. 每一個 User Record 代表索引樹上的一個節(jié)點；3。 從圖中可以看出，頁包含著 User Record 和 System Record，所以頁包含著段？（存疑）

5.2.1 User Record

User Record在Page內(nèi)以單鏈表的形式存在，最初數(shù)據(jù)是按照插入的先后順序排列的，但是隨著新數(shù)據(jù)的插入和舊數(shù)據(jù)的刪除，數(shù)據(jù)物理順序發(fā)生改變，但是他們依然保持著邏輯上的先后順序

image.png

把User Record組織形式和若干Page組織起來，就得到了稍微完整的形式：

image.png

六、總結(jié)

本篇討論了幾個關(guān)鍵點：

• 頁的基本概念和組成成分
• Mysql 是如何在單頁內(nèi)、多頁間，針對不同的數(shù)據(jù)量，對數(shù)據(jù)操作性能的提升
• 頁與索引之間的關(guān)系

如果本文由卻是，或者解釋不清的地方，還望在下方留言。大家一起交流，一起學(xué)習(xí)，一起進步。

引用：
從頭帶你捋一遍 MySQL 索引結(jié)構(gòu)，索引沒你想的那么難！
mysql中InnoDB引擎中頁的概念