故事從好多年前說(shuō)起。

想必大家也聽(tīng)說(shuō)過(guò)數(shù)據(jù)庫(kù)單表建議最大2kw條數(shù)據(jù)這個(gè)說(shuō)法。如果超過(guò)了，性能就會(huì)下降得比較厲害。

巧了。

我也聽(tīng)說(shuō)過(guò)。

但我不接受它的建議，硬是單表裝了1億條數(shù)據(jù)。

這時(shí)候，我們組里新來(lái)的實(shí)習(xí)生看到了之后，天真無(wú)邪的問(wèn)我："單表不是建議最大兩千萬(wàn)嗎?為什么這個(gè)表都放了1個(gè)億還不分庫(kù)分表"?

我能說(shuō)我是因?yàn)閼袉?我當(dāng)初設(shè)計(jì)時(shí)哪里想到這表竟然能漲這么快。。。

我不能。

說(shuō)了等于承認(rèn)自己是開(kāi)發(fā)組里的毒瘤，雖然我確實(shí)是，但我不能承認(rèn)。

我如坐針氈，如芒刺背，如鯁在喉。

開(kāi)始了一波騷操作。

"我這么做是有道理的"

"雖然這個(gè)表很大，但你有沒(méi)有發(fā)現(xiàn)它查詢(xún)其實(shí)還是很快"

"這個(gè)2kw是個(gè)建議值，我們要來(lái)看下這個(gè)2kw是怎么來(lái)的"

數(shù)據(jù)庫(kù)單表行數(shù)最大多大?

我們先看下單表行數(shù)理論最大值是多少。

建表的SQL是這么寫(xiě)的，

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就是主鍵。主鍵本身唯一，也就是說(shuō)主鍵的大小可以限制表的上限。

如果主鍵聲明為int大小，也就是32位，那么能支持2^32-1，也就是21個(gè)億左右。

如果是bigint，那就是2^64-1，但這個(gè)數(shù)字太大，一般還沒(méi)到這個(gè)限制之前，磁盤(pán)先受不了。

搞離譜點(diǎn)。

如果我把主鍵聲明為 tinyint，一個(gè)字節(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;

如果我想插入一個(gè)id=256的數(shù)據(jù)，那就會(huì)報(bào)錯(cuò)。

mysql> INSERT INTO `tmp` (`id`, `name`, `age`) VALUES (256, '', 60);
ERROR 1264 (22003): Out of range value for column 'id' at row 1

也就是說(shuō)，tinyint主鍵限制表內(nèi)最多255條數(shù)據(jù)。

那除了主鍵，還有哪些因素會(huì)影響行數(shù)?

索引的結(jié)構(gòu)

索引內(nèi)部是用的B+樹(shù)，這個(gè)也是八股文老股了，大家估計(jì)也背得很熟了。

為了不讓大家有過(guò)于強(qiáng)烈的審丑疲勞，今天我嘗試從另外一個(gè)角度給大家講講這玩意。

頁(yè)的結(jié)構(gòu)

假設(shè)我們有這么一張user數(shù)據(jù)表。

user表

其中id是唯一主鍵。

這看起來(lái)的一行行數(shù)據(jù)，為了方便，我們后面就叫它們r(jià)ecord吧。

這張表看起來(lái)就跟個(gè)excel表格一樣。excel的數(shù)據(jù)在硬盤(pán)上是一個(gè)xx.excel的文件。

而上面user表數(shù)據(jù)，在硬盤(pán)上其實(shí)也是類(lèi)似，放在了user.ibd文件下。含義是user表的innodb data文件，專(zhuān)業(yè)點(diǎn)，又叫表空間。

雖然在數(shù)據(jù)表里，它們看起來(lái)是挨在一起的。但實(shí)際上在user.ibd里他們被分成很多小份的數(shù)據(jù)頁(yè)，每份大小16k。

類(lèi)似于下面這樣。

ibd文件內(nèi)部有大量的頁(yè)

我們把視角聚焦一下，放到頁(yè)上面。

整個(gè)頁(yè)16k，不大，但record這么多，一頁(yè)肯定放不下，所以會(huì)分開(kāi)放到很多頁(yè)里。并且這16k，也不可能全用來(lái)放record對(duì)吧。

因?yàn)閞ecord們被分成好多份，放到好多頁(yè)里了，為了唯一標(biāo)識(shí)具體是哪一頁(yè)，那就需要引入頁(yè)號(hào)(其實(shí)是一個(gè)表空間的地址偏移量)。同時(shí)為了把這些數(shù)據(jù)頁(yè)給關(guān)聯(lián)起來(lái)，于是引入了前后指針，用于指向前后的頁(yè)。這些都被加到了頁(yè)頭里。

頁(yè)是需要讀寫(xiě)的，16k說(shuō)小也不小，寫(xiě)一半電源線(xiàn)被拔了也是有可能發(fā)生的，所以為了保證數(shù)據(jù)頁(yè)的正確性，還引入了校驗(yàn)碼。這個(gè)被加到了頁(yè)尾。

那剩下的空間，才是用來(lái)放我們的record的。而record如果行數(shù)特別多的話(huà)，進(jìn)入到頁(yè)內(nèi)時(shí)挨個(gè)遍歷，效率也不太行，所以為這些數(shù)據(jù)生成了一個(gè)頁(yè)目錄，具體實(shí)現(xiàn)細(xì)節(jié)不重要。只需要知道，它可以通過(guò)二分查找的方式將查找效率從O(n) 變成O(lgn)。

頁(yè)結(jié)構(gòu)

從頁(yè)到索引

如果想查一條record，我們可以把表空間里每一頁(yè)都撈出來(lái)，再把里面的record撈出來(lái)挨個(gè)判斷是不是我們要找的。

行數(shù)量小的時(shí)候，這么操作也沒(méi)啥問(wèn)題。

行數(shù)量大了，性能就慢了，于是為了加速搜索，我們可以在每個(gè)數(shù)據(jù)頁(yè)里選出主鍵id最小的record，而且只需要它們的主鍵id和所在頁(yè)的頁(yè)號(hào)。組成新的record，放入到一個(gè)新生成的一個(gè)數(shù)據(jù)頁(yè)中，這個(gè)新數(shù)據(jù)頁(yè)跟之前的頁(yè)結(jié)構(gòu)沒(méi)啥區(qū)別，而且大小還是16k。

但為了跟之前的數(shù)據(jù)頁(yè)進(jìn)行區(qū)分。數(shù)據(jù)頁(yè)里加入了頁(yè)層級(jí)(page level)的信息，從0開(kāi)始往上算。于是頁(yè)與頁(yè)之間就有了上下層級(jí)的概念，就像下面這樣。

兩層B+樹(shù)結(jié)構(gòu)

突然頁(yè)跟頁(yè)之間看起來(lái)就像是一棵倒過(guò)來(lái)的樹(shù)了。也就是我們常說(shuō)的B+樹(shù)索引。

最下面那一層，page level 為0，也就是所謂的葉子結(jié)點(diǎn)，其余都叫非葉子結(jié)點(diǎn)。

上面展示的是兩層的樹(shù)，如果數(shù)據(jù)變多了，我們還可以再通過(guò)類(lèi)似的方法，再往上構(gòu)建一層。就成了三層的樹(shù)。

三層B+樹(shù)結(jié)構(gòu)

那現(xiàn)在我們就可以通過(guò)這樣一棵B+樹(shù)加速查詢(xún)。舉個(gè)例子。

比方說(shuō)我們想要查找行數(shù)據(jù)5。會(huì)先從頂層頁(yè)的record們?nèi)胧?。record里包含了主鍵id和頁(yè)號(hào)(頁(yè)地址)?？聪聢D黃色的箭頭，向左最小id是1，向右最小id是7。那id=5的數(shù)據(jù)如果存在，那必定在左邊箭頭。于是順著的record的頁(yè)地址就到了6號(hào)數(shù)據(jù)頁(yè)里，再判斷id=5>4，所以肯定在右邊的數(shù)據(jù)頁(yè)里，于是加載105號(hào)數(shù)據(jù)頁(yè)。在數(shù)據(jù)頁(yè)里找到id=5的數(shù)據(jù)行，完成查詢(xún)。

B+樹(shù)查詢(xún)過(guò)程

另外需要注意的是，上面的頁(yè)的頁(yè)號(hào)并不是連續(xù)的，它們?cè)诖疟P(pán)里也不一定是挨在一起的。

這個(gè)過(guò)程中查詢(xún)了三個(gè)頁(yè)，如果這三個(gè)頁(yè)都在磁盤(pán)中(沒(méi)有被提前加載到內(nèi)存中)，那么最多需要經(jīng)歷三次磁盤(pán)IO查詢(xún)，它們才能被加載到內(nèi)存中。

B+樹(shù)承載的記錄數(shù)量

從上面的結(jié)構(gòu)里可以看出B+樹(shù)的最末級(jí)葉子結(jié)點(diǎn)里放了record數(shù)據(jù)。而非葉子結(jié)點(diǎn)里則放了用來(lái)加速查詢(xún)的索引數(shù)據(jù)。

也就是說(shuō)：

同樣一個(gè)16k的頁(yè)，非葉子節(jié)點(diǎn)里每一條數(shù)據(jù)都指向一個(gè)新的頁(yè)，而新的頁(yè)有兩種可能。

• 如果是末級(jí)葉子節(jié)點(diǎn)的話(huà)，那么里面放的就是一行行record數(shù)據(jù)。
• 如果是非葉子節(jié)點(diǎn)，那么就會(huì)循環(huán)繼續(xù)指向新的數(shù)據(jù)頁(yè)。

假設(shè)

• 非葉子結(jié)點(diǎn)內(nèi)指向其他內(nèi)存頁(yè)的指針數(shù)量為x。
• 葉子節(jié)點(diǎn)內(nèi)能容納的record數(shù)量為y。
• B+樹(shù)的層數(shù)為z。

總行數(shù)的計(jì)算方法

那這棵B+樹(shù)放的行數(shù)據(jù)總量等于 (x ^ (z-1)) * y。

x怎么算

我們回去看數(shù)據(jù)頁(yè)的結(jié)構(gòu)。

頁(yè)結(jié)構(gòu)

非葉子節(jié)點(diǎn)里主要放索引查詢(xún)相關(guān)的數(shù)據(jù)，放的是主鍵和指向頁(yè)號(hào)。

主鍵假設(shè)是bigint(8Byte)，而頁(yè)號(hào)在源碼里叫FIL_PAGE_OFFSET(4Byte)，那么非葉子節(jié)點(diǎn)里的一條數(shù)據(jù)是12Byte左右。

整個(gè)數(shù)據(jù)頁(yè)16k， 頁(yè)頭頁(yè)尾那部分?jǐn)?shù)據(jù)全加起來(lái)大概128Byte，加上頁(yè)目錄毛估占1k吧。那剩下的15k除以12Byte，等于1280，也就是可以指向x=1280頁(yè)。

我們常說(shuō)的二叉樹(shù)指的是一個(gè)結(jié)點(diǎn)可以發(fā)散出兩個(gè)新的結(jié)點(diǎn)。m叉樹(shù)一個(gè)節(jié)點(diǎn)能指向m個(gè)新的結(jié)點(diǎn)。這個(gè)指向新節(jié)點(diǎn)的操作就叫扇出(fanout)。

而上面的B+樹(shù)，它能指向1280個(gè)新的節(jié)點(diǎn)，恐怖如斯，可以說(shuō)扇出非常高了。

y的計(jì)算

葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是一樣的，所以也假設(shè)剩下15kb可以發(fā)揮。

葉子節(jié)點(diǎn)里放的是真正的行數(shù)據(jù)。假設(shè)一條行數(shù)據(jù)1kb，所以一頁(yè)里能放y=15行。

行總數(shù)計(jì)算

回到 (x ^ (z-1)) * y 這個(gè)公式。

已知x=1280，y=15。

假設(shè)B+樹(shù)是兩層，那z=2。則是(1280 ^ (2-1)) * 15 ≈ 2w。

假設(shè)B+樹(shù)是三層，那z=3。則是(1280 ^ (3-1)) * 15 ≈ 2.5kw。

這個(gè)2.5kw，就是我們常說(shuō)的單表建議最大行數(shù)2kw的由來(lái)。畢竟再加一層，數(shù)據(jù)就大得有點(diǎn)離譜了。三層數(shù)據(jù)頁(yè)對(duì)應(yīng)最多三次磁盤(pán)IO，也比較合理。

行數(shù)超一億就慢了嗎?

上面假設(shè)單行數(shù)據(jù)用了1kb，所以一個(gè)數(shù)據(jù)頁(yè)能放個(gè)15行數(shù)據(jù)。

如果我單行數(shù)據(jù)用不了這么多，比如只用了250byte。那么單個(gè)數(shù)據(jù)頁(yè)能放60行數(shù)據(jù)。

那同樣是三層B+樹(shù)，單表支持的行數(shù)就是 (1280 ^ (3-1)) * 60 ≈ 1個(gè)億。

你看我一個(gè)億的數(shù)據(jù)，其實(shí)也就三層B+樹(shù)，在這個(gè)B+樹(shù)里要查到某行數(shù)據(jù)，最多也是三次磁盤(pán)IO。所以并不慢。

這就很好的解釋了文章開(kāi)頭，為什么我單表1個(gè)億，但查詢(xún)性能沒(méi)啥大毛病。

B樹(shù)承載的記錄數(shù)量

既然都聊到這里了，我們就順著這個(gè)話(huà)題多聊一些吧。

我們都知道，現(xiàn)在mysql的索引都是B+樹(shù)，而有一種樹(shù)，跟B+樹(shù)很像，叫B樹(shù)，也叫B-樹(shù)。

它跟B+樹(shù)最大的區(qū)別在于，B+樹(shù)只在末級(jí)葉子結(jié)點(diǎn)處放數(shù)據(jù)表行數(shù)據(jù)，而B(niǎo)樹(shù)則會(huì)在葉子和非葉子結(jié)點(diǎn)上都放。

于是，B樹(shù)的結(jié)構(gòu)就類(lèi)似這樣：

B樹(shù)結(jié)構(gòu)

B樹(shù)將行數(shù)據(jù)都存在非葉子節(jié)點(diǎn)上，假設(shè)每個(gè)數(shù)據(jù)頁(yè)還是16kb，掐頭去尾每頁(yè)剩15kb，并且一條數(shù)據(jù)表行數(shù)據(jù)還是占1kb，就算不考慮各種頁(yè)指針的情況下，也只能放個(gè)15條數(shù)據(jù)。數(shù)據(jù)頁(yè)扇出明顯變少了。

計(jì)算可承載的總行數(shù)的公式也變成了一個(gè)等比數(shù)列。

15 + 15^2 +15^3 + ... + 15^z

其中z還是層數(shù)的意思。

為了能放2kw左右的數(shù)據(jù)，需要z>=6。也就是樹(shù)需要有6層，查一次要訪(fǎng)問(wèn)6個(gè)頁(yè)。假設(shè)這6個(gè)頁(yè)并不連續(xù)，為了查詢(xún)其中一條數(shù)據(jù)，最壞情況需要進(jìn)行6次磁盤(pán)IO。

而B(niǎo)+樹(shù)同樣情況下放2kw數(shù)據(jù)左右，查一次最多是3次磁盤(pán)IO。

磁盤(pán)IO越多則越慢，這兩者在性能上差距略大。

為此，B+樹(shù)比B樹(shù)更適合成為mysql的索引。

總結(jié)

B+樹(shù)葉子和非葉子結(jié)點(diǎn)的數(shù)據(jù)頁(yè)都是16k，且數(shù)據(jù)結(jié)構(gòu)一致，區(qū)別在于葉子節(jié)點(diǎn)放的是真實(shí)的行數(shù)據(jù)，而非葉子結(jié)點(diǎn)放的是主鍵和下一個(gè)頁(yè)的地址。

B+樹(shù)一般有兩到三層，由于其高扇出，三層就能支持2kw以上的數(shù)據(jù)，且一次查詢(xún)最多1~3次磁盤(pán)IO，性能也還行。

存儲(chǔ)同樣量級(jí)的數(shù)據(jù)，B樹(shù)比B+樹(shù)層級(jí)更高，因此磁盤(pán)IO也更多，所以B+樹(shù)更適合成為mysql索引。

索引結(jié)構(gòu)不會(huì)影響單表最大行數(shù)，2kw也只是推薦值，超過(guò)了這個(gè)值可能會(huì)導(dǎo)致B+樹(shù)層級(jí)更高，影響查詢(xún)性能。

單表最大值還受主鍵大小和磁盤(pán)大小限制。

參考資料

《MYSQL內(nèi)核：INNODB存儲(chǔ)引擎 卷1》

最后雖然我在單表里塞了1億條數(shù)據(jù)，但這個(gè)操作的前提是，我很清楚這不會(huì)太影響性能。

這波解釋?zhuān)翢o(wú)破綻，無(wú)懈可擊。

到這里，連我自己都被自己說(shuō)服了。想必實(shí)習(xí)生也是。

可惡，這該死的毒瘤竟然有些"知識(shí)淵博"。