淺析InnoDB三層B+數(shù)的存儲計算

事情是這樣的

下面是朋友的面試記錄：

面試官：講一下你實習做了什么。

朋友：我在實習期間做了一個存儲用戶操作記錄的功能，主要是從MQ獲取上游服務發(fā)送過來的用戶操作信息，然后把這些信息存到MySQL里面，提供給數(shù)倉的同事使用。

朋友：由于數(shù)據(jù)量比較大，每天大概有四五千多萬條，所以我還給它做了分表的操作。每天定時生成3張表，然后將數(shù)據(jù)取模分別存到這三張表里，防止表內(nèi)數(shù)據(jù)過多導致查詢速度降低。

這表述，好像沒什么問題是吧，別急，接著看：

面試官：那你為什么要分三張表呢，兩張表不行嗎？四張表不行嗎？

朋友：因為MySQL每張表最好不超過2000萬條數(shù)據(jù)，否則會導致查詢速度降低，影響性能。我們每天的數(shù)據(jù)大概是在五千萬條左右，所以分成三張表比較穩(wěn)妥。

面試官：還有嗎？

朋友： 沒有了…… 你干嘛，哎呦

面試官：那你先回去等通知吧。

講完了，看出什么了嗎，你們覺得這位朋友回答的有什么問題嗎？

前言

很多人說，MySQL每張表最好不要超過2000萬條數(shù)據(jù)，否則就會導致性能下降。阿里的Java開發(fā)手冊上也提出：單表行數(shù)超過 500 萬行或者單表容量超過 2GB，才推薦進行分庫分表。

但實際上，這個2000萬或者500萬都只是一個大概的數(shù)字，并不適用于所有場景，如果盲目的以為表數(shù)據(jù)只要不超過2000萬條就沒問題了，很可能會導致系統(tǒng)的性能大幅下降。

實際情況下，每張表由于自身的字段不同、字段所占用的空間不同等原因，它們在最佳性能下可以存放的數(shù)據(jù)量也就不同。

那么，該如何計算出每張表適合的數(shù)據(jù)量呢？別急，慢慢往下看。

本文適合的讀者

閱讀本文你需要有一定的MySQL基礎，最好對InnoDB和B+樹都有一定的了解，可能需要有一年以上的MySQL學習經(jīng)驗（大概一年？），知道 “InnoDB中B+樹的高度一般保持在三層以內(nèi)會比較好” 這條理論知識。

本文主要是針對 “InnoDB中高度為3的B+樹最多可以存多少數(shù)據(jù)” 這一話題進行講解的。且本文對數(shù)據(jù)的計算比較嚴格（至少比網(wǎng)上95%以上的相關博文都要嚴格），如果你比較在意這些細節(jié)并且目前不太清楚的話，請繼續(xù)往下閱讀。

閱讀本文你大概需要花費10-20分鐘的時間，如果你在閱讀的過程中對數(shù)據(jù)進行驗算的話，可能要花費30分鐘左右。

本文思維導圖

InnoDB三層B+數(shù)的存儲計算-思維導圖

基礎知識快速回顧

眾所周知，MySQL中InnoDB的存儲結(jié)構(gòu)是B+樹，B+樹大家都熟悉吧？特性大概有以下幾點，一起快速回顧一下吧！

注：下面這這些內(nèi)容都是精華，看不懂或者不理解的同學建議先收藏本文，之后有知識基礎了再回來看 。

一張數(shù)據(jù)表一般對應一顆或多顆樹的存儲，樹的數(shù)量與建索引的數(shù)量有關，每個索引都會有一顆單獨的樹。

聚簇索引和非聚簇索引：

主鍵索引也是聚簇索引，非主鍵索引都是非聚簇索引。除格式信息外，兩種索引的非葉子節(jié)點都是只存索引數(shù)據(jù)的，比如索引為id，那非葉子節(jié)點就是存的id數(shù)據(jù)。

葉子節(jié)點的區(qū)別如下：

聚簇索引的葉子節(jié)點一般情況下存的是這條數(shù)據(jù)的所有字段信息。所以我們 select * from table where id = 1 的時候，都是要去葉子節(jié)點拿數(shù)據(jù)的。

非聚簇索引的葉子節(jié)點存的是這條數(shù)據(jù)所對應的主鍵和索引列信息。比如這條非聚簇索引是username，然后表的主鍵是id，那該非聚簇索引的葉子節(jié)點存的就是 username 和 id，而不存其他字段。 相當于是先從非聚簇索引查到主鍵的值，再根據(jù)主鍵索引去查數(shù)據(jù)內(nèi)容，一般情況下要查兩次（除非索引覆蓋），這也稱之為 回表 ，就有點類似于存了個指針，指向了數(shù)據(jù)存放的真實地址。

B+樹的查詢是從上往下一層層查詢的，一般情況下我們認為B+樹的高度保持在3層以內(nèi)是比較好的，也就是上兩層是索引，最后一層存數(shù)據(jù)，這樣查表的時候只需要進行3次磁盤IO就可以了(實際上會少一次，因為根節(jié)點會常駐內(nèi)存)，且能夠存放的數(shù)據(jù)量也比較可觀。

如果數(shù)據(jù)量過大，導致B+數(shù)變成4層了，則每次查詢就需要進行4次磁盤IO了，從而使性能下降。所以我們才會去計算InnoDB的3層B+樹最多可以存多少條數(shù)據(jù)。

MySQL每個節(jié)點大小默認為16KB，也就是每個節(jié)點最多存16KB的數(shù)據(jù)，可以修改，最大64KB，最小4KB。

擴展：那如果某一行的數(shù)據(jù)特別大，超過了節(jié)點的大小怎么辦？

MySQL5.7文檔的解釋是：

- 對于 4KB、8KB、16KB 和 32KB設置 ，最大行長度略小于數(shù)據(jù)庫頁面的一半 。例如：對于默認的 16KB頁大小，最大行長度略小于 8KB ，默認32KB的頁大小，則最大行長度略小于16KB。

- 而對于 64KB 頁面，最大行則長度略小于 16KB。

- 如果行超過最大行長度， 則將可變長度列用外部頁存儲，直到該行符合最大行長度限制。 就是說把varchar、text這種長度可變的存到外部頁中，來減小這一行的數(shù)據(jù)長度。

MySQL查詢速度主要取決于磁盤的讀寫速度，因為MySQL查詢的時候每次只讀取一個節(jié)點到內(nèi)存中，通過這個節(jié)點的數(shù)據(jù)找到下一個要讀取的節(jié)點位置，再讀取下一個節(jié)點的數(shù)據(jù)，直到查詢到需要的數(shù)據(jù)或者發(fā)現(xiàn)數(shù)據(jù)不存在。

肯定有人要問了，每個節(jié)點內(nèi)的數(shù)據(jù)難道不用查詢嗎？這里的耗時怎么不計算？

這是因為讀取完整個節(jié)點的數(shù)據(jù)后，會存到內(nèi)存當中，在內(nèi)存中查詢節(jié)點數(shù)據(jù)的耗時其實是很短的，再配合MySQL的查詢方式，時間復雜度差不多為 O(log2N)O(log_2N)O(log2N) ，相比磁盤IO來說，可以忽略不計。

MySQL InnoDB 節(jié)點的儲存內(nèi)容

在Innodb的B+樹中，我們常說的節(jié)點被稱之為 頁(page)，每個頁當中存儲了用戶數(shù)據(jù)，所有的頁合在一起組成了一顆B+樹（當然實際會復雜很多，但我們只是要計算可以存多少條數(shù)據(jù)，所以姑且可以這么理解）。

頁 是InnoDB存儲引擎管理數(shù)據(jù)庫的最小磁盤單位，我們常說每個節(jié)點16KB，其實就是指每頁的大小為16KB。

這16KB的空間，里面需要存儲 頁格式 信息和 行格式 信息，其中行格式信息當中又包含一些元數(shù)據(jù)和用戶數(shù)據(jù)。所以我們在計算的時候，要把這些數(shù)據(jù)的都計算在內(nèi)。

頁格式

每一頁的基本格式，也就是每一頁都會包含的一些信息，總結(jié)表格如下：

示意圖：

頁格式這塊的內(nèi)容，我在官網(wǎng)翻了好久，硬是沒找到。。。。不知道是沒寫還是我眼瞎，有找到的朋友希望可以在評論區(qū)幫我掛出來。

所以上面頁格式的表格內(nèi)容主要是基于一些博客中學習總結(jié)的。

另外，當新記錄插入到 InnoDB 聚集索引中時，InnoDB 會嘗試留出 1/16 的頁面空閑以供將來插入和更新索引記錄。如果按順序（升序或降序）插入索引記錄，則生成的頁大約可用 15/16 的空間。如果以隨機順序插入記錄，則頁大約可用 1/2 到 15/16 的空間。

除了 User Records和Free Space 以外所占用的內(nèi)存是 38+56+26+8=128字節(jié)，每一頁留給用戶數(shù)據(jù)的空間就還剩（保留了1/16）。

當然，這是最小值，因為我們沒有考慮頁目錄。頁目錄留在后面根據(jù)再去考慮，這個得根據(jù)表字段來計算。

行格式

首先，我覺得有必要提一嘴，MySQL5.6的默認行格式為COMPACT(緊湊)，5.7及以后的默認行格式為DYNAMIC(動態(tài))，不同的行格式存儲的方式也是有區(qū)別的，還有其他的兩種行格式，本文后續(xù)的內(nèi)容主要是基于DYNAMIC(動態(tài))進行講解的。

每行記錄都包含以下這些信息，其中大都是可以從官方文檔當中找到的。我這里寫的不是特別詳細，僅寫了一些能夠我們計算空間的知識，更詳細內(nèi)容可以去網(wǎng)上搜索 “MySQL 行格式”。

示意圖：

另外還有幾點需要注意：

溢出頁（外部頁）的存儲

注意：這一點是DYNAMIC的特性。

當使用 DYNAMIC 創(chuàng)建表時，InnoDB 會將較長的可變長度列（比如 VARCHAR、VARBINARY、BLOB 和 TEXT 類型）的值剝離出來，存儲到一個溢出頁上，只在該列上保留一個 20 字節(jié)的指針指向溢出頁。

而 COMPACT 行格式（MySQL5.6默認格式）則是將前 768 個字節(jié)和 20 字節(jié)的指針存儲在 B+ 樹節(jié)點的記錄中，其余部分存儲在溢出頁上。

列是否存儲在頁外取決于頁大小和行的總大小。當一行太長時，選擇最長的列進行頁外存儲，直到聚集索引記錄適合 B+ 樹頁（文檔里沒說具體是多少）。小于或等于 40 字節(jié)的 TEXT 和 BLOB 直接存儲在行內(nèi)，不會分頁。

優(yōu)點

DYNAMIC 行格式避免了用大量數(shù)據(jù)填充 B+ 樹節(jié)點從而導致長列的問題。

DYNAMIC 行格式的想法是，如果長數(shù)據(jù)值的一部分存儲在頁外，則通常將整個值存儲在頁外是最有效的。

使用 DYNAMIC 格式，較短的列會盡可能保留在 B+ 樹節(jié)點中，從而最大限度地減少給定行所需的溢出頁數(shù)。

字符編碼不同情況下的存儲

char 、varchar、text 等需要設置字符編碼的類型，在計算所占用空間時，需要考慮不同編碼所占用的空間。

varchar、text等類型會有長度字段列表來記錄他們所占用的長度，但char是固定長度的類型，情況比較特殊，假設字段 name 的類型為 char(10) ，則有以下情況：

對于長度固定的字符編碼（比如ASCII碼），字段 name 將以固定長度格式存儲，ASCII碼每個字符占一個字節(jié)，那 name 就是占用 10 個字節(jié)。

對于長度不固定的字符編碼（比如utf8mb4），至少將為 name 保留 10 個字節(jié)。如果可以，InnoDB會通過修剪尾部空格空間的方式來將其存到 10 個字節(jié)中。

如果空格剪完了還存不下，則將尾隨空格修剪為 _列值字節(jié)長度的最小值_（一般是 1 字節(jié)）。

列的最大長度為： 字符編碼的最大字符長度×N字符編碼的最大字符長度 imes N字符編碼的最大字符長度×N，比如 name 字段的編碼為 utf8mb4，那就是 4×10。

大于或等于 768 字節(jié)的 char 列會被看成是可變長度字段（就像varchar一樣），可以跨頁存儲。例如，utf8mb4 字符集的最大字節(jié)長度為 4，則 char(255) 列將可能會超過 768 個字節(jié)，進行跨頁存儲。

說實話對char的這個設計我是不太理解的，盡管看了很久，包括官方文檔和一些博客，希望懂的同學可以在評論區(qū)解惑：

對于長度不固定的字符編碼這塊，char是不是有點像是一個長度可變的類型了？我們常用的 utf8mb4，占用為 1 ~ 4 字節(jié)，那么 char(10) 所占用的空間就是 10 ~ 40 字節(jié)，這個變化還是挺大的啊，但是它并沒有留足夠的空間給它，也沒有使用可變長度字段列表去記錄char字段的空間占用情況，就很特殊？

開始計算

好了，我們已經(jīng)知道每一頁當中具體存儲的東西了，現(xiàn)在我們已經(jīng)具備計算能力了。

由于頁的剩余空間我已經(jīng)在上面頁格式的地方計算過了，每頁會剩余 15232 字節(jié)可用，下面我們直接計算行。

非葉子節(jié)點計算

單個節(jié)點計算

索引頁就是存索引的節(jié)點，也就是非葉子節(jié)點。

每一條索引記錄當中都包含了當前索引的值 、 一個 6字節(jié) 的指針信息 、一個 5 字節(jié)的行標頭，用來指向下一層數(shù)據(jù)頁的指針。

索引記錄當中的指針占用空間我沒在官方文檔里找到，這個 6 字節(jié)是我參考其他博文的，他們說源碼里寫的是6字節(jié)，但具體在哪一段源碼我也不知道。

希望知道的同學可以在評論區(qū)解惑。

假設我們的主鍵id為 bigint 型，也就是8個字節(jié)，那索引頁中每行數(shù)據(jù)占用的空間就等于 8+6+5=19字節(jié)。每頁可以存 15232÷19≈801?條索引數(shù)據(jù)。

那算上頁目錄的話，按每個槽平均6條數(shù)據(jù)計算的話，至少有 801÷6≈134?個槽，需要占用 268 字節(jié)的空間。

把存數(shù)據(jù)的空間分一點給槽的話，我算出來大約可以存 787 條索引數(shù)據(jù)。

如果是主鍵是 int 型的話，那可以存更多，大約有 993 條索引數(shù)據(jù)。

前兩層非葉子節(jié)點計算

在 B+ 樹當中，當一個節(jié)點索引記錄為 N?條時，它就會有 N 個子節(jié)點。由于我們 3 層B+樹的前兩層都是索引記錄，第一層根節(jié)點有 N 條索引記錄，那第二層就會有 N 個節(jié)點，每個節(jié)點數(shù)據(jù)類型與根節(jié)點一致，仍然可以再存 N?條記錄，第三層的節(jié)點個數(shù)就會等于。

則有：

主鍵為 bigint 的表可以存放?個葉子節(jié)點

主鍵為 int 的表可以存放??個葉子節(jié)點

OK計算完畢。

數(shù)據(jù)條數(shù)計算

最少存放記錄數(shù)

前面我們提到，_最大行長度略小于數(shù)據(jù)庫頁面的一半_，之所以是略小于一半，是由于每個頁面還留了點空間給_頁格式_ 的其他內(nèi)容，所以我們可以認為每個頁面最少能放兩條數(shù)據(jù)，每條數(shù)據(jù)略小于8KB。如果某行的數(shù)據(jù)長度超過這個值，那InnoDB肯定會分一些數(shù)據(jù)到 溢出頁 當中去了，所以我們不考慮。

那每條數(shù)據(jù)8KB的話，每個葉子節(jié)點就只能存放 2 條數(shù)據(jù)，這樣的一張表，在主鍵為 bigint 的情況下，只能存放 2×619369=1238738條數(shù)據(jù)，也就是一百二十多萬條，這個數(shù)據(jù)量，沒想到吧。

較多的存放記錄數(shù)

假設我們的表是這樣的：

--?這是一張非常普通的課程安排表，除id外，僅包含了課程id和老師id兩個字段
--?且這幾個字段均為?int?型（當然實際生產(chǎn)中不會這么設計表，這里只是舉例）。

CREATE?TABLE?`course_schedule`?(
??`id`?int?NOT?NULL,
??`teacher_id`?int?NOT?NULL,
??`course_id`?int?NOT?NULL,
??PRIMARY?KEY?(`id`)?USING?BTREE
)?ENGINE=InnoDB?DEFAULT?CHARSET=utf8;

先來分析一下這張表的行數(shù)據(jù)：無null值列表，無可變長字段列表，需要算上事務ID和指針字段，需要算上行記錄頭，那么每行數(shù)據(jù)所占用的空間就是 4+4+4+6+7+5=30?字節(jié)，每個葉子節(jié)點可以存放 15232÷30≈507條數(shù)據(jù)。

算上頁目錄的槽位所占空間，每個葉子節(jié)點可以存放 502 條數(shù)據(jù)，那么三層B+樹可以存放的最大數(shù)據(jù)量就是 502×986049=494,996,598，將近5億條數(shù)據(jù)！沒想到吧。

常規(guī)表的存放記錄數(shù)

大部分情況下我們的表字段都不是上面那樣的，所以我選擇了一場比較常規(guī)的表來進行分析，看看能存放多少數(shù)據(jù)。表情況如下：

CREATE?TABLE?`blog`?(
??`id`?bigint?unsigned?NOT?NULL?AUTO_INCREMENT?COMMENT?'博客id',
??`author_id`?bigint?unsigned?NOT?NULL?COMMENT?'作者id',
??`title`?varchar(50)?CHARACTER?SET?utf8mb4?NOT?NULL?COMMENT?'標題',
??`description`?varchar(250)?CHARACTER?SET?utf8mb4?NOT?NULL?COMMENT?'描述',
??`school_code`?bigint?unsigned?DEFAULT?NULL?COMMENT?'院校代碼',
??`cover_image`?char(32)?DEFAULT?NULL?COMMENT?'封面圖',
??`create_time`?datetime?NOT?NULL?DEFAULT?CURRENT_TIMESTAMP?COMMENT?'創(chuàng)建時間',
??`release_time`?datetime?DEFAULT?NULL?COMMENT?'首次發(fā)表時間',
??`modified_time`?datetime?NOT?NULL?DEFAULT?CURRENT_TIMESTAMP?ON?UPDATE?CURRENT_TIMESTAMP?COMMENT?'修改時間',
??`status`?tinyint?unsigned?NOT?NULL?COMMENT?'發(fā)表狀態(tài)',
??`is_delete`?tinyint?unsigned?NOT?NULL?DEFAULT?0,
??PRIMARY?KEY?(`id`),
??KEY?`author_id`?(`author_id`),
??KEY?`school_code`?(`school_code`)?USING?BTREE
)?ENGINE=InnoDB?AUTO_INCREMENT=1?DEFAULT?CHARSET=utf8?COLLATE=utf8_general_mysql500_ci?ROW_FORMAT=DYNAMIC;這是開源項目“校園博客”（GitHub地址：https://github.com/stick-i/scblogs ?） 中的博客表，用于存放博客的基本數(shù)據(jù)。

分析一下這張表的行記錄：

行記錄頭信息：肯定得有，占用5字節(jié)。

可變長度字段列表：表中 title占用1字節(jié)，description占用2字節(jié)，共3字節(jié)。

null值列表：表中僅school_code、cover_image、release_time3個字段可為null，故僅占用1字節(jié)。

事務ID和指針字段：兩個都得有，占用13字節(jié)。

字段內(nèi)容信息：

id、author_id、school_code 均為bigint型，各占用8字節(jié)，共24字節(jié)。

create_time、release_time、modified_time 均為datetime類型，各占8字節(jié)，共24字節(jié)。

status、is_delete 為tinyint類型，各占用1字節(jié)，共2字節(jié)。

cover_image 為char(32)，字符編碼為表默認值utf8，由于該字段實際存的內(nèi)容僅為英文字母（存url的），結(jié)合前面講的_字符編碼不同情況下的存儲_ ，故僅占用32字節(jié)。

title、description 分別為varchar(50)、varchar(250)，這兩個應該都不會產(chǎn)生溢出頁（不太確定），字符編碼均為utf8mb4，實際生產(chǎn)中70%以上都是存的中文(3字節(jié))，25%為英文(1字節(jié))，還有5%為4字節(jié)的表情，則存滿的情況下將占用 (50+250)×(0.7×3+0.25×1+0.05×4)=765?字節(jié)。

統(tǒng)計上面的所有分析，共占用 869 字節(jié)，則每個葉子節(jié)點可以存放 15232÷869≈17?條，算上頁目錄，仍然能放 17 條。

則三層B+樹可以存放的最大數(shù)據(jù)量就是 17×619369=10,529,273，約一千萬條數(shù)據(jù)，再次沒想到吧。

數(shù)據(jù)計算總結(jié)

根據(jù)上面三種不同情況下的計算，可以看出，InnoDB三層B+樹情況下的數(shù)據(jù)存儲量范圍為 一百二十多萬條 到 將近5億條，這個跨度還是非常大的，同時我們也計算了一張博客信息表，可以存儲 約一千萬條 數(shù)據(jù)。

所以啊，我們在做項目考慮分表的時候還是得多關注一下表的實際情況，而不是盲目的認為兩千萬數(shù)據(jù)就是那個臨界點。

如果面試時談到這塊的問題，我想面試官也并不是想知道這個數(shù)字到底是多少，而是想看你如何分析這個問題，看你得出這個數(shù)字的過程。

編輯：黃飛

?