故事從好多年前說起。
想必大家也聽說過數(shù)據(jù)庫單表建議最大兩千萬條數(shù)據(jù)這個說法。如果超過了，性能就會下降得比較厲害。
巧了。我也聽說過。
但我不接受他的建議，硬是單表裝了 1 億條數(shù)據(jù)。
這時候，我們組里新來的實習生看到了之后，天真無邪地問我："單表不是建議最大兩千萬嗎？為什么這個表都放了 1 個億還不分庫分表"？
我能說我是因為懶嗎？我當初設計時哪里想到這表竟然能漲這么快……
我不能。
說了等于承認自己是開發(fā)組里的毒瘤，雖然我確實是，但我不能承認。
我如坐針氈，如芒刺背，如鯁在喉。
開始了一波騷操作。
"我這么做是有道理的。"
"雖然這個表很大，但你有沒有發(fā)現(xiàn)它查詢其實還是很快。"
"這個兩千萬是個建議值，我們要來看下這個兩千萬是怎么來的。"
數(shù)據(jù)庫單表行數(shù)最大多大？
我們先看下單表行數(shù)理論最大值是多少。
建表的 SQL 是這么寫的，
CREATE TABLE `user` ( `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '主鍵', `name` varchar(100) NOT NULL DEFAULT '' COMMENT '名字', `age` int(11) NOT NULL DEFAULT '0' COMMENT '年齡', PRIMARY KEY (`id`), KEY `idx_age` (`age`) ) ENGINE=InnoDB AUTO_INCREMENT=100037 DEFAULT CHARSET=utf8;
其中 id 就是主鍵。主鍵本身唯一，也就是說主鍵的大小可以限制表的上限。
如果主鍵聲明為 int 大小，也就是 32 位。那么能支持 2^32-1，也就是 21 個億左右。
如果是 bigint，那就是 2^64-1。但這個數(shù)字太大，一般還沒到這個限制之前，磁盤先受不了。
搞離譜點。
如果我把主鍵聲明為 tinyint 一個字節(jié)， 8位。最大 2^8-1，也就是 255。
CREATE TABLE `user` ( `id` tinyint(2) unsigned NOT NULL AUTO_INCREMENT COMMENT '主鍵', `name` varchar(100) NOT NULL DEFAULT '' COMMENT '名字', `age` int(11) NOT NULL DEFAULT '0' COMMENT '年齡', PRIMARY KEY (`id`), KEY `idx_age` (`age`) ) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8;
如果我想插入一個 id=256 的數(shù)據(jù)，那就會報錯。
MySQL> INSERT INTO `tmp` (`id`, `name`, `age`) VALUES (256, '', 60); ERROR 1264 (22003): Out of range value for column 'id' at row 1
也就是說，tinyint 主鍵限制表內最多 255 條數(shù)據(jù)。
除了主鍵，還有哪些因素會影響行數(shù)？
索引的結構
索引內部是用的 B+ 樹，這個也是八股文老股了，大家估計也背得很熟了。
為了不讓大家有過于強烈的審丑疲勞，今天我嘗試從另外一個角度給大家講講這玩意。
頁的結構
假設我們有這么一張 user 數(shù)據(jù)表。
user 表
其中 id 是唯一主鍵。
這看起來的一行行數(shù)據(jù)，為了方便，我們后面就叫它們 record 吧。
這張表看起來就跟個 Excel 表格一樣。Excel 的數(shù)據(jù)在硬盤上是一個 xx.xlsx 文件。
而上面 user 表數(shù)據(jù)，在硬盤上其實也是類似，放在了 user.ibd 文件下。含義是 user 表的 innodb data 文件，專業(yè)說法又叫表空間。
雖然在數(shù)據(jù)表里，它們看起來是挨在一起的。但實際上在 user.ibd 里他們被分成很多小數(shù)據(jù)頁，每份大小16K。
類似于下面這樣：
ibd 文件內部有大量的頁
我們把視角聚焦到頁上面。
整個頁大小為 16K，不大。但 record 這么多，一頁肯定放不下，所以會分開放到很多頁里。并且這 16K 也不可能全用來放 record，對吧。
因為，這些 record 被分成好多份，放到各個頁里了。為了唯一標識具體是哪一頁，那就需要引入頁號（其實是一個表空間的地址偏移量）。同時為了把這些數(shù)據(jù)頁給關聯(lián)起來，于是引入了前后指針，用于指向前后的頁。這些都被加到了頁頭里。
頁需要支持讀寫，16K 說小也不小，寫一半電源線被拔了也是有可能發(fā)生的。所以，為了保證數(shù)據(jù)頁的正確性，還引入了校驗碼。這個被加到了頁尾。
那剩下的空間才被用來放 record。如果 record 行數(shù)特別多，進入到頁內時會挨個遍歷效率也不太行。所以，為這些數(shù)據(jù)生成了一個頁目錄。具體實現(xiàn)細節(jié)不重要，只需要知道，它可以通過二分查找的方式將查找效率從 O(n) 變成 O(logn)。
頁結構
從頁到索引
如果想查一條 record，可以把表空間里每一頁查出來，再把里面的 record 挨個判斷是不是我們要找的。
行數(shù)小的時候，這么操作也沒啥問題。行數(shù)多了，性能就慢了。
于是為了加快搜索，可以在每個數(shù)據(jù)頁里選出主鍵 id 最小的 record，而且只需要它們的主鍵 id 和所在頁的頁號。將它們組成新的 record，放入到一個新生成的一個數(shù)據(jù)頁中。這個新數(shù)據(jù)頁跟之前的頁結構沒啥區(qū)別，大小還是 16K。
但為了跟之前的數(shù)據(jù)頁進行區(qū)分，數(shù)據(jù)頁里加入了頁層級（Page Level）信息，從 0 開始往上算。于是頁與頁之間就有了上下層級的概念，就像下面這樣。
兩層 B+ 樹結構
頁跟頁之間看起來就像是一棵倒過來的樹，也就是我們常說的 B+ 樹索引。
最下面一層 Page Level 為 0，也就是所謂的葉子結點。其余都叫非葉子結點。
上面展示的是兩層的樹。如果數(shù)據(jù)變多了，還可以再通過類似的方法，往上構建一層，成了三層樹。
三層 B+ 樹結構
現(xiàn)在，可以通過這樣一棵 B+ 樹加速查詢。
舉個例子，比方說我們想要查找數(shù)據(jù)行 5。
先從頂層頁的 record 入手。record 里包含了主鍵 id 和頁號（頁地址）。
下圖中黃色的箭頭：向左最小 id 是 1，向右最小 id 是 7。
-
如果 id=5 的數(shù)據(jù)存在，那必定在左邊箭頭；
-
于是順著的 record 的頁地址就到了 6 號數(shù)據(jù)頁里；
-
再判斷 id=5>4，所以肯定在右邊的數(shù)據(jù)頁里；
-
于是加載 105 號數(shù)據(jù)頁；
-
在數(shù)據(jù)頁里找到 id=5 的數(shù)據(jù)行，完成查詢。
B+ 樹的查詢過程
另外需要注意，上面的頁的頁號并不是連續(xù)的，它們在磁盤里也不一定是挨在一起的。
這個過程中查詢了三個頁，如果這三個頁都在磁盤中（沒有被提前加載到內存中），那么最多需要經(jīng)歷三次磁盤 IO 查詢，它們才能被加載到內存中。
B+ 樹承載的記錄數(shù)量
從上面的結構里可以看出，B+ 樹的最末級葉子結點里放了 record 數(shù)據(jù)。而非葉子結點里則放了用來加速查詢的索引數(shù)據(jù)。
也就是說，同樣一個 16K 的頁，非葉子節(jié)點里每一條數(shù)據(jù)都指向一個新的頁。而新的也有兩種可能。
-
如果是末級葉子節(jié)點的話，那么里面放的就是 record 數(shù)據(jù)；
-
如果是非葉子節(jié)點，那么就會循環(huán)繼續(xù)指向新的數(shù)據(jù)頁。
假設：
-
非葉子結點內指向其他內存頁的指針數(shù)量為 X；
-
葉子節(jié)點內能容納的 record 數(shù)量為 Y；
-
B+ 樹的層數(shù)為 Z。
總行數(shù)的計算方法
那這棵 B+ 樹放的行數(shù)據(jù)總量等于 (X ^ (Z-1)) * Y。
怎么計算 X
我們回去看數(shù)據(jù)頁的結構。
頁結構
非葉子節(jié)點里主要放索引查詢相關的數(shù)據(jù)，放的是主鍵和指向頁號。
主鍵假設是 bigint（8Byte），而頁號在源碼里叫 FIL_PAGE_OFFSET（4 Byte），那么非葉子節(jié)點里的一條數(shù)據(jù)是 12 Byte 左右。
整個數(shù)據(jù)頁 16K， 頁頭頁尾那部分數(shù)據(jù)全加起來大概 128 Byte，加上頁目錄毛估占 1K 吧。那剩下的 15K 除以 12 Byte 等于 1280，也就是可以指向 X=1280 頁。
我們常說的二叉樹指的是一個結點可以發(fā)散出兩個新的結點。m 叉樹一個節(jié)點能指向 m 個新的節(jié)點。這個指向新節(jié)點的操作就叫扇出（Fanout）。
而上面的 B+ 樹能指向 1280 個新的節(jié)點。恐怖如斯，可以說扇出非常高了。
如何計算 Y
葉子節(jié)點和非葉子節(jié)點的數(shù)據(jù)結構是一樣的，所以也假設剩下 15KB 可以利用。
葉子節(jié)點里放的是真正的行數(shù)據(jù)。假設一條行數(shù)據(jù) 1KB，所以一頁里能放 Y=15 行。
行總數(shù)計算
回到 (X ^ (Z-1)) * Y 這個公式，已知 X=1280，Y=15。
-
假設 B+ 樹是兩層，那 Z=2。總行數(shù) (1280 ^ (2-1)) * 15 ≈ 2萬
-
假設 B+ 樹是三層，那 Z=3。總行數(shù) (1280 ^ (3-1)) * 15 ≈ 2.5千萬
這個 2.5千萬，就是我們常說的單表建議最大行數(shù)兩千萬的由來。畢竟再加一層，數(shù)據(jù)就大得有點離譜了。三層數(shù)據(jù)頁對應最多三次磁盤 IO，也比較合理。
行數(shù)超 1 億就慢了嗎？
上面假設單行數(shù)據(jù)用了 1KB，所以一個數(shù)據(jù)頁能放個 15 行數(shù)據(jù)。
如果我單行數(shù)據(jù)用不了這么多，比如只用了 250 Byte。那么單個數(shù)據(jù)頁能放 60 行數(shù)據(jù)。
那同樣是三層 B+ 樹，單表支持的行數(shù)就是 (1280 ^ (3-1)) * 60 ≈ 1億。
你看我 1 億數(shù)據(jù)，其實也就三層 B+ 樹。在這個 B+ 樹里要查到某行數(shù)據(jù)，最多也是三次磁盤 IO，所以并不慢。
這就很好的解釋了文章開頭，為什么我單表 1 億條數(shù)據(jù)，但查詢性能沒啥大毛病。
B 樹承載的記錄數(shù)量
既然都聊到這里了，我們就順著這個話題多聊一些吧。
我們都知道，現(xiàn)在 MySQL 的索引都是 B+ 樹。而有一種樹，跟 B+ 樹很像叫 B 樹，也叫 B- 樹。它跟 B+ 樹最大的區(qū)別在于，B+ 樹只在末級葉子結點處放數(shù)據(jù)表行數(shù)據(jù)，而 B 樹則會在葉子和非葉子結點上都放。
B 樹的結構類似這樣：
B 樹結構
B 樹將行數(shù)據(jù)都存在非葉子節(jié)點上。假設每個數(shù)據(jù)頁還是 16KB，掐頭去尾每頁剩15KB，并且一條數(shù)據(jù)表行數(shù)據(jù)還是占 1KB。就算不考慮各種頁指針的情況下，也只能放個 15 條數(shù)據(jù)，數(shù)據(jù)頁的扇出明顯變小了。
計算可承載的總行數(shù)的公式也變成了一個等比數(shù)列。
15 + 15^2 +15^3 + ... + 15^Z
其中 Z 還是層數(shù)的意思。
為了能放兩千萬左右的數(shù)據(jù)需要 Z>=6，也就是樹需要有 6 層。查一次要訪問 6 個頁。假設這 6 個頁并不連續(xù)，為了查詢其中一條數(shù)據(jù)，最壞情況需要進行 6 次磁盤 IO。
而 B+ 樹同樣情況下放兩千萬數(shù)據(jù)左右，查一次最多是 3 次磁盤 IO。
磁盤 IO 越多則越慢，這兩者在性能上差距略大。因此，B+ 樹比 B 樹更適合稱為 MySQL 索引。
總結
-
B+ 樹葉子和非葉子結點的數(shù)據(jù)頁都是 16KB，并且數(shù)據(jù)結構一致。區(qū)別在于葉子節(jié)點放的是真實的行數(shù)據(jù)，而非葉子節(jié)點放的是主鍵和下一個頁的地址；
-
B+ 樹一般有兩到三層。由于其高扇出，三層就能支持兩千萬以上的數(shù)據(jù)。并且一次查詢最多 1~3 次磁盤 IO，性能也還行；
-
存儲同樣量級的數(shù)據(jù)，B 樹比 B+ 樹層級更高，因此磁盤 IO 也更多。所以，B+ 樹更適合稱為 MySQL 索引。
-
索引結構不會影響單表最大行數(shù)，兩千萬也只是推薦值。超過了這個值可能會導致 B+ 樹層級更高，影響查詢性能；
-
單表最大值還受主鍵大小和磁盤大小限制。
參考資料
《MYSQL內核：INNODB存儲引擎 卷1》
- EOF -
