前言

應(yīng)"極客時(shí)間"之約，寫了這個(gè)文章... ...

1.提出問題

學(xué)習(xí)技術(shù)，如武功修煉，學(xué)會(huì)招式很重要，但掌握它的內(nèi)在心法更重要，這樣一來，才能成為高手。

比如，像使用MySQL設(shè)計(jì)表結(jié)構(gòu)時(shí)，建主鍵是避免不了的。但大家知道主鍵的長度是會(huì)影響到查詢性能的么？這其中到底是受什么影響的呢？雖然這個(gè)問題在你使用MySQL進(jìn)行業(yè)務(wù)系統(tǒng)設(shè)計(jì)時(shí)，不是那么顯著的問題。但理解了這個(gè)問題的本質(zhì)，尤其是Mysyql Innodb存儲(chǔ)引擎中B+樹的數(shù)據(jù)結(jié)構(gòu)、構(gòu)建這個(gè)數(shù)據(jù)結(jié)構(gòu)的過程、及結(jié)構(gòu)與查詢性能間的關(guān)系，你將會(huì)獲得不同的新的認(rèn)知。了解了這個(gè)過程，那么之后在使用其他存儲(chǔ)系統(tǒng)時(shí)，也會(huì)有相關(guān)的對(duì)比經(jīng)驗(yàn)。

現(xiàn)在，就以“為什么MySQL設(shè)計(jì)主鍵時(shí)key不能過長”這個(gè)問題為切入點(diǎn)，通過分析Innodb 表空間文件和數(shù)據(jù)頁的結(jié)構(gòu)來看一下Mysql Innodb在表的數(shù)據(jù)索引結(jié)構(gòu)和查詢性能上的關(guān)系。

2.解決問題的核心關(guān)鍵點(diǎn)

眾所周知，Innodb引擎是使用B+樹這種數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)庫表中的數(shù)據(jù)的。表的主鍵存儲(chǔ)在B+樹的葉子節(jié)點(diǎn)上，葉子節(jié)點(diǎn)上還存儲(chǔ)著主鍵所關(guān)聯(lián)的行記錄數(shù)據(jù)，也就是我們常說的聚集索引，它存儲(chǔ)著整張表的數(shù)據(jù)。但這只是邏輯上的描述。

（圖1 - 聚集索引樹邏輯表達(dá)）

只從這個(gè)知識(shí)點(diǎn)上，是不能理解為什么主鍵key的長度和查詢性能間的關(guān)系的。為了解決這個(gè)問題，我們需要更深入一層，可以從幾個(gè)關(guān)鍵點(diǎn)來理解：

一個(gè)是聚集索引的底層物理結(jié)構(gòu)，需要理解在這個(gè)物理結(jié)構(gòu)上它是如何存儲(chǔ)數(shù)據(jù)的；

再來說說第二個(gè)關(guān)鍵點(diǎn)，也就是理解查找遍歷數(shù)據(jù)時(shí)，遍歷操作是如何基于B+樹這個(gè)邏輯和物理結(jié)構(gòu)進(jìn)行查找數(shù)據(jù)的；

最后，來看看第三個(gè)關(guān)鍵點(diǎn)，你需要理解在構(gòu)建這顆B+樹和遍歷時(shí)，都有哪些因素會(huì)影響到查詢性能，并需要在各個(gè)影響因素下做一下對(duì)比來深入理解。

為了能夠更加形象地說明，這里舉一個(gè)例子，并創(chuàng)建一個(gè)數(shù)據(jù)庫和一個(gè)數(shù)據(jù)庫表。表test1的結(jié)構(gòu)是這樣的:

(圖2 - 表test1的結(jié)構(gòu))

其中，主鍵索引p_k 和二級(jí)索引s_k都是一個(gè)Int 類型的字段，并通過python腳本導(dǎo)入100000行數(shù)據(jù)記錄：

(圖3 - 導(dǎo)入數(shù)據(jù)腳本)

3.解決問題

導(dǎo)入后，我們可以看到Innodb會(huì)創(chuàng)建表空間文件來存儲(chǔ)數(shù)據(jù)，比如例子中的ibdata1文件（圖4）和dbtest目錄中test1.ibd文件（圖5）。其中，dbtest 是數(shù)據(jù)庫名，ibdata1是系統(tǒng)表空間文件，test1.ibd文件則實(shí)際存儲(chǔ)著表中的數(shù)據(jù)：

(圖4 - 系統(tǒng)表空間文件)

（圖5 - test1的表空間文件）

在開始分析表空間文件之前，我們需要建立這樣幾點(diǎn)認(rèn)知：

一是，Innodb存儲(chǔ)引擎中存儲(chǔ)數(shù)據(jù)的最小單位是頁，也就是page，默認(rèn)情況下，這個(gè)頁所占用的磁盤空間大小為16KB；

第二點(diǎn)認(rèn)知是，Innodb引擎一個(gè)數(shù)據(jù)頁中一個(gè)數(shù)據(jù)行記錄的大小，不能超過8000個(gè)字節(jié)。因此，一個(gè)數(shù)據(jù)頁中在行記錄最大size的情況下，只能最多能存儲(chǔ)2行記錄；如果一個(gè)數(shù)據(jù)頁存不下一行記錄，會(huì)創(chuàng)建新的數(shù)據(jù)頁來存儲(chǔ)；

最后，再來說說第三點(diǎn)認(rèn)知，在Innodb存儲(chǔ)引擎中，會(huì)有好幾種頁類型來存儲(chǔ)不同類別的數(shù)據(jù)。其中Index索引頁是專門用于存儲(chǔ)表的行數(shù)據(jù)的。

我們可以通過一些開源的Innodb 表空間文件分析工具，來查看表空間內(nèi)部的數(shù)據(jù)信息。結(jié)合這張圖來看，你可以看到類型為Index的就是B+Tree 索引，基于我們的例子，在Innodb中，存儲(chǔ)100000行數(shù)據(jù)和創(chuàng)建的二級(jí)索引數(shù)據(jù)，共占據(jù)了301個(gè)索引頁，大約占據(jù)了36%的存儲(chǔ)空間：

（圖6 - 表空間文件中的不同數(shù)據(jù)頁類型）

當(dāng)然，還可以通過其他的命令模式，來查看更細(xì)粒度的信息，看下這張圖（圖7），你可以看到索引數(shù)據(jù)頁被分成了兩個(gè)部分。其中一個(gè)是以索引樹root page 編號(hào)為3 的索引，另一個(gè)是以索引樹root page 編號(hào)為4的索引，編號(hào)為3的索引樹總共有216個(gè)頁，編號(hào)為4的索引樹總共有85個(gè)，這其實(shí)是分別對(duì)應(yīng)我們例子中表test1的主鍵聚集索引p_k和二級(jí)索引s_k兩顆B+樹的根節(jié)點(diǎn)數(shù)據(jù)頁，因?yàn)榫奂饕~子節(jié)點(diǎn)中存儲(chǔ)了整行的數(shù)據(jù)。而二級(jí)索引存儲(chǔ)的是二級(jí)索引字段的值和主鍵字段的值，并沒有存儲(chǔ)例子表中圖2的那個(gè)名為‘c’的字符列，所以主鍵索引樹占據(jù)的數(shù)據(jù)頁要比二級(jí)索引樹占據(jù)的數(shù)據(jù)頁多一些：

（圖7 - 索引數(shù)據(jù)頁基礎(chǔ)信息）

另外，我們?cè)賮聿榭聪戮奂饕龢渲械慕Y(jié)構(gòu)，從這張圖來看（圖8），表test1在存儲(chǔ)100000行數(shù)據(jù)的情況下，聚集索引樹總共分裂成了兩層，第一層是根頁面節(jié)點(diǎn)，第二層為葉子節(jié)點(diǎn)并存儲(chǔ)著行數(shù)據(jù)。編號(hào)為3的根頁面節(jié)點(diǎn)，總共存儲(chǔ)了215個(gè)記錄，其中第一個(gè)記錄所存儲(chǔ)的數(shù)據(jù)為主鍵的值，也就是 p_k=0 及其所指向的葉子節(jié)點(diǎn)頁面編號(hào)指針，比如圖例為Leaf Node #5的葉子節(jié)點(diǎn)?？梢钥吹剑~子節(jié)點(diǎn)的上一層所指向的非葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)記錄，總是其葉子節(jié)點(diǎn)中主鍵的最小值：

（圖8 - 聚集索引樹中每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)）

通過這張圖（圖9），可以更加形象化地看到聚集索引樹的大體物理存儲(chǔ)結(jié)構(gòu)：

（圖9 -形象化表示聚集索引樹結(jié)構(gòu)）

不難看出，非葉子節(jié)點(diǎn)的分叉數(shù)量和子節(jié)點(diǎn)數(shù)據(jù)頁的數(shù)量，以及自身數(shù)據(jù)頁所能存儲(chǔ)的記錄數(shù)有關(guān)。

接下來，讓我們?cè)倏纯匆粋€(gè)數(shù)據(jù)頁的內(nèi)部結(jié)構(gòu)，以便更好地理解查找遍歷數(shù)據(jù)的過程。這里我們Dump編號(hào)為7的數(shù)據(jù)頁的數(shù)據(jù)結(jié)構(gòu)信息，可以在圖10和圖11中看到一些關(guān)鍵信息：

一個(gè)是：數(shù)據(jù)頁中存在一個(gè)叫做Page Directory的頁目錄，它總共占據(jù)了236個(gè)字節(jié)，共有118個(gè)Entry：

（圖10 - 編號(hào)7數(shù)據(jù)頁中的頁目錄大小）

（圖11 - 編號(hào)7數(shù)據(jù)頁中的頁目錄列表）

再來看看第二個(gè)關(guān)鍵信息，除了第一個(gè)槽位和最后一個(gè)槽位，每個(gè)page directory 槽管理了4個(gè)行記錄，而頁面目錄Entry關(guān)聯(lián)存儲(chǔ)著所管理主鍵值最小的那一行記錄的偏移量；

（圖12 - 編號(hào)7數(shù)據(jù)頁中的頁目錄詳細(xì)信息）

最后一個(gè)關(guān)鍵信息就是：在一個(gè)數(shù)據(jù)頁中，各個(gè)數(shù)據(jù)行通過記錄下一個(gè)數(shù)據(jù)行的偏移量offset，從而構(gòu)成了一個(gè)單向鏈表。

（圖13 - 編號(hào)7數(shù)據(jù)頁中的頁目錄詳細(xì)信息）

那么，在一個(gè)SQL語句中給定一個(gè)主鍵值作為查詢條件并返回所在行的數(shù)據(jù)，會(huì)經(jīng)歷一個(gè)怎么樣的查找遍歷數(shù)據(jù)過程呢？我們通過分析工具模擬Innodb在聚集索引樹上進(jìn)行二分查找主鍵，可以看到具體所遍歷的數(shù)據(jù)頁和頁面目錄的過程。比如，我們查找主鍵值為88888的記錄，如下圖（圖14）所示：

（圖14 - 查找遍歷數(shù)據(jù)結(jié)果）

可以看到，遍歷這顆聚集索引樹，總共遍歷了2個(gè)數(shù)據(jù)頁：

首先，在編號(hào)3的根節(jié)點(diǎn)數(shù)據(jù)頁中，通過Page Directory（頁目錄）二分查找，經(jīng)歷了6次折半遍歷和4次順序遍歷;

其次，在編號(hào)350的子節(jié)點(diǎn)數(shù)據(jù)頁中，通過Page Directory（頁目錄）二分查找，總共經(jīng)歷了8次折半遍歷和4次順序遍歷。

（圖15 - 查找遍歷數(shù)據(jù)的概要信息）

由此可見，在聚集索引樹上通過主鍵查找一個(gè)數(shù)據(jù)記錄時(shí)，需要經(jīng)歷從根節(jié)點(diǎn)到非葉子節(jié)點(diǎn)，再到葉子節(jié)點(diǎn)的過程，并且在每個(gè)數(shù)據(jù)頁中通過Page Directory（頁目錄）進(jìn)行二分查找，來進(jìn)一步縮減順序查找的范圍，可以參看如下流程圖（圖16）：

（圖16 - 查找遍歷數(shù)據(jù)的邏輯流圖）

而從性能角度來說，查找遍歷索引數(shù)據(jù)時(shí)，所遍歷的數(shù)據(jù)頁P(yáng)age 數(shù)量越多，耗時(shí)越多，因?yàn)閺拇疟P裝載數(shù)據(jù)頁，都需要耗費(fèi)一次IO，從而可以確信地推斷出來，索引樹中非葉子數(shù)據(jù)頁的數(shù)量和葉子數(shù)據(jù)頁節(jié)點(diǎn)的數(shù)量越多，查找耗時(shí)也會(huì)越多。

前面的例子中，還只是展示了直接通過主鍵索引為條件，去查找遍歷聚集索引樹返回?cái)?shù)據(jù)行的過程。而一般實(shí)際情況下，很多都是先通過二級(jí)索引樹來先找到主鍵索引，然后再通過主鍵索引樹查找數(shù)據(jù)的。二級(jí)索引樹也是一個(gè)B+樹的邏輯結(jié)構(gòu)，非葉子節(jié)點(diǎn)存儲(chǔ)的是二級(jí)索引Key，葉子節(jié)點(diǎn)存儲(chǔ)的是二級(jí)索引Key和主鍵索引值，參看圖17

（圖17 - 二級(jí)索引數(shù)據(jù)頁結(jié)構(gòu)）

好了，到這里，我們已經(jīng)看到通過分析Innodb 的表空間文件和數(shù)據(jù)頁的結(jié)構(gòu)，能夠理解到查找遍歷數(shù)據(jù)是基于數(shù)據(jù)頁的，并且一個(gè)數(shù)據(jù)頁內(nèi)存儲(chǔ)的數(shù)據(jù)行數(shù)是有限制的，從而導(dǎo)致超過數(shù)據(jù)頁限制的數(shù)據(jù)行會(huì)被分裂到新的數(shù)據(jù)頁當(dāng)中。

接下來我們創(chuàng)建另外一張表，通過加大主鍵key的長度，來和第一張表test1做對(duì)比分析。這一次我們將主鍵key從Int類型8字節(jié)長度變成可變字符類型。這里，我們?cè)O(shè)定主鍵Key最大可存儲(chǔ)300個(gè)字符的varchar（300），看看這么長的主鍵Key與Int類型的主鍵存儲(chǔ)相同數(shù)據(jù)量的數(shù)據(jù)時(shí)，在查找性能上會(huì)有什么差別。

表test2的結(jié)構(gòu)是這樣的（圖18），同樣地，我們可以通過腳本導(dǎo)入100000行數(shù)據(jù)。

（圖18 - 表test2結(jié)構(gòu)）

（圖19 - 導(dǎo)入腳本）

（圖20 - 導(dǎo)入腳本）

其中，主鍵的取值為一個(gè)長度為300個(gè)字符并且從尾字母開始依次從‘a(chǎn)’,’b’,’c’,’d’,’e’,’f’,’g’六個(gè)字符中向高位循環(huán)遞增的字符，例如：

（圖21 - 表test2主鍵值）

導(dǎo)過數(shù)據(jù)之后，表test2的空間文件test2.ibd 如下圖所示：

（圖22 - test2的表空間文件）

并且，通過查詢聚集索引的數(shù)據(jù)頁結(jié)構(gòu)詳細(xì)信息，可以看到，同樣一行記錄，主鍵索引取值變長且在二級(jí)索引字段s_k和字符列’c’列取值不變的情況下，聚集索引樹的高度已經(jīng)變成了3層，且每個(gè)數(shù)據(jù)頁中所包含的數(shù)據(jù)行數(shù)大大減少。

（圖23 - 索引數(shù)據(jù)頁信息）

（圖24 - 索引數(shù)據(jù)頁中的頁目錄）

那么，當(dāng)我們?cè)谶@顆聚集索引樹上查找遍歷數(shù)據(jù)時(shí)，性能又會(huì)如何呢？為了對(duì)比，我們?cè)诒韙est2中查找與表test1具有同樣相對(duì)位置的數(shù)據(jù)行，比如，二級(jí)索引s_k = 88888 對(duì)應(yīng)的記錄，模擬查找遍歷的過程和概要信息如圖25，26：

（圖25 - 查找遍歷一個(gè)數(shù)據(jù)行的過程）

（圖26 - 查找遍歷一個(gè)數(shù)據(jù)行的概要信息）

可見，查找遍歷所裝載的數(shù)據(jù)頁變成了3個(gè)頁面，這意味著3次磁盤IO，相比主鍵為Int類型8字節(jié)長度的表test1多了一次IO，且比較主鍵key的次數(shù)也變多了，這些數(shù)字的變化都意味著查詢效率的變低。

4.總結(jié)

到此，我們來小結(jié)一下，主鍵長度變長和查詢遍歷數(shù)據(jù)效率之間的關(guān)系：

首先，存儲(chǔ)表中各個(gè)數(shù)據(jù)行的聚集索引邏輯結(jié)構(gòu)，在物理表現(xiàn)上，是將各個(gè)行按主鍵值順序插入到各個(gè)索引數(shù)據(jù)頁當(dāng)中；

其次，受限于一個(gè)數(shù)據(jù)頁能夠存儲(chǔ)的數(shù)據(jù)行大小的限制，無論是聚集索引還是二級(jí)索引數(shù)據(jù)頁，如果主鍵長度設(shè)定的過長，都將會(huì)導(dǎo)致數(shù)據(jù)頁分裂，尤其是索引樹的非葉子節(jié)點(diǎn)數(shù)據(jù)頁和二級(jí)索引的葉子節(jié)點(diǎn)數(shù)據(jù)頁，使得數(shù)據(jù)頁內(nèi)部能夠存儲(chǔ)的記錄數(shù)量變少；

從而，使得查找遍歷數(shù)據(jù)時(shí)，不得不在相對(duì)更多的數(shù)據(jù)頁中進(jìn)行查找，增加了裝載數(shù)據(jù)頁的耗時(shí)和比較主鍵key的次數(shù)，降低了效率。

5.延伸思考

這里，關(guān)于Mysql主鍵長度和查找性能關(guān)系的話題，就先說到這兒。大家也可以自己開腦洞，在數(shù)據(jù)存儲(chǔ)層面去看看還有哪些因素會(huì)影響查詢性能，比如：

1）如果以亂序的方式將數(shù)據(jù)插入到Mysql Innodb表中時(shí)，對(duì)于性能是否有影響，影響的因素是什么；

2）或者，如果在高并發(fā)且設(shè)置了自增主鍵的情況下，那么鎖競(jìng)爭(zhēng)對(duì)于插入性能的影響？Mysql Innodb 又提供了哪些方案來應(yīng)對(duì)？

另外，還有幾點(diǎn)想談一下：

1）分析和學(xué)習(xí)一項(xiàng)技術(shù)，掌握其范式非常重要。比如，數(shù)據(jù)存儲(chǔ)，那么對(duì)其基礎(chǔ)數(shù)據(jù)存儲(chǔ)模型和結(jié)構(gòu)是要先構(gòu)建認(rèn)知的；其次是需要多收集相關(guān)的信息，通過對(duì)比、發(fā)散、聯(lián)想、舉例實(shí)踐，進(jìn)而加深理解；然后是總結(jié)、輸出；

2）平時(shí)注重不斷溫習(xí)數(shù)據(jù)結(jié)構(gòu)、算法和編程模型（好的、"別人"的代碼是怎么寫的，為什么這樣寫？）等基礎(chǔ)。只有擁有了好的基礎(chǔ)，才能更快、更準(zhǔn)確的理解與接收。