?　　在瘋狂創(chuàng)客圈 的社群面試交流中，有很多小伙伴在面大廠， 經(jīng)常遇到下面的問題：

　　問題1：在實(shí)際生產(chǎn)環(huán)境中，InnoDB 中一棵 B+ 樹索引一般有多少層？

　　問題2：在實(shí)際生產(chǎn)環(huán)境中，InnoDB一棵B+樹可以存放多少行數(shù)據(jù)？

　　問題3：MySQL 對(duì)于千萬級(jí)的大表，為啥要優(yōu)化？

　　問題4：mysql 單表最好不要超過2000w？

　　問題5：單表超過2000w 就要考慮數(shù)據(jù)遷移了，這個(gè)是為啥？

　　問題6：你這個(gè)表數(shù)據(jù)都馬上要到2000w 了，難怪查詢速度慢，為什么？

　　問題N： ... 第100個(gè)變種

　　前段時(shí)間，有一個(gè)小伙伴在面美團(tuán)里的時(shí)候，又遇到了此問題。

　　其實(shí)，這些問題，都是在考察大家對(duì) B+樹底層原理的理解

　　尼恩在這里，給大家做一個(gè)系統(tǒng)化、起底式、全方位的梳理。

　　按照下面的套路去答，基本可以拿到120分。

　　大家收藏起來，多度幾遍，一定能讓面試官刮目相看。

　　現(xiàn)在把這個(gè) 題目以及參考答案，收入咱們的 《尼恩Java面試寶典》，

　　供后面的小伙伴參考，提升大家的 3高 架構(gòu)、設(shè)計(jì)、開發(fā)水平。

　　注：本文以 PDF 持續(xù)更新，最新Java 架構(gòu)筆記、面試題 的PDF文件，請(qǐng)后臺(tái)私信【筆記】即可獲取！

　　要回答這些問題，在回答的時(shí)候，首先從 InnoDB 索引數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)組織方式說起。

　　磁盤扇區(qū)、文件系統(tǒng)、InnoDB 存儲(chǔ)引擎都有各自的最小存儲(chǔ)單元。

　　來看看三個(gè)重要的最小單元磁盤上，存儲(chǔ)數(shù)據(jù)最小單元是扇區(qū)，一個(gè)扇區(qū)的大小是 512 字節(jié)，文件系統(tǒng)（例如EXT4）,最小單元是塊 （block），一個(gè)block 塊的大小是 4k，InnoDB 存儲(chǔ)引擎 的最小儲(chǔ)存單元——頁（Page），一個(gè)頁的大小是 16K。

　　來一個(gè)圖，更清楚：

　　以上三個(gè)數(shù)據(jù)，非常重要，一定要背下來， 并且在面試的時(shí)候， 找個(gè)機(jī)會(huì)背出來。

　　面試官一聽，感覺你的計(jì)算機(jī)底層知識(shí)是多么的扎實(shí)，好感慢慢。這是來自 老架構(gòu)師的 衷心提示。

　　由于文件系統(tǒng)（例如EXT4）的最小單元是塊 （block），一個(gè)block 塊的大小是 4k，

　　所以，假設(shè)一個(gè)文件大小只有1個(gè)字節(jié)，那么，這個(gè)文件在磁盤上，還是不得不占4KB的空間。

　　具體如下圖：

　　要知道，Innodb 的所有數(shù)據(jù)文件（后綴為 ibd 的文件），也是存儲(chǔ)在磁盤的，當(dāng)然也是由block組成，

　　所以，Innodb 的所有數(shù)據(jù)文件，全部都是 16384（16k）的整數(shù)倍。

　　具體如下圖：

　　InnoDB 存儲(chǔ)引擎 的最小儲(chǔ)存單元——頁（Page），一個(gè)頁的大小是 16K，

　　在 MySQL 中我們的InnoDB 頁的大小當(dāng)然也可以通過參數(shù)設(shè)置的，具體如下圖：

　　通過上圖，可以看到，在 MySQL 中我們的 InnoDB 頁的大小默認(rèn)是 16k

　　數(shù)據(jù)表中的數(shù)據(jù)都是存儲(chǔ)在頁中的，所以一個(gè)頁中能存儲(chǔ)多少行數(shù)據(jù)呢？

　　先做一個(gè)假設(shè)：

　　假設(shè)一行數(shù)據(jù)的大小是1k，

　　那么一個(gè)16K頁，可以存放16行這樣的數(shù)據(jù)。

　　如果數(shù)據(jù)庫只按這樣的方式存儲(chǔ)，那么如何查找數(shù)據(jù)就成為一個(gè)問題

　　因?yàn)槲覀儾恢酪檎业臄?shù)據(jù)存在哪個(gè)頁中，也不可能把所有的頁遍歷一遍，那樣太慢了。

　　所以人們想了一個(gè)辦法，用B+樹的方式組織這些數(shù)據(jù)。B+ 樹的葉子節(jié)點(diǎn)存儲(chǔ)真正的記錄，對(duì)應(yīng)的文件系統(tǒng) page頁面，可以叫做 數(shù)據(jù)頁B+ 樹的非葉子節(jié)點(diǎn)存放的是鍵值 + 指針，其對(duì)應(yīng)的文件系統(tǒng) page頁面，可以叫做 索引頁

　　這里用指針來描其實(shí)述不是太準(zhǔn)確，準(zhǔn)確來說是頁的偏移量，不過借用指針一詞，更好理解

　　如圖所示：

　　InnoDB中主鍵索引B+樹是如何組織數(shù)據(jù)、查詢數(shù)據(jù)的？

　　我們總結(jié)一下：

　　1、在B+樹中葉子節(jié)點(diǎn)存放數(shù)據(jù)，非葉子節(jié)點(diǎn)存放鍵值+指針。

　　InnoDB存儲(chǔ)引擎的最小存儲(chǔ)單元是頁，頁可以用于存放數(shù)據(jù)也可以用于存放鍵值+指針，

　　2、頁內(nèi)的記錄是有序的，所以可以使用二分查找在頁內(nèi)到下一層的目標(biāo)頁面的指針從根頁開始，首先通過非葉子節(jié)點(diǎn)的二分查找法，確定數(shù)據(jù)在下一層哪個(gè)頁之后，一層一層往下找，一直到非葉子節(jié)點(diǎn)，進(jìn)而在非葉子節(jié)（數(shù)據(jù)頁）中查找到需要的數(shù)據(jù)；

　　那么回到我們開始的問題，通常一棵B+樹可以存放多少行數(shù)據(jù)？

　　首先，需要計(jì)算出非葉子節(jié)點(diǎn)能存放多少指針？

　　頁作為 InnoDB 磁盤管理的最小單位，不僅可以用來存放具體的行數(shù)據(jù)，還可以存放鍵值和指針。

　　回到文題，我們先從簡單的入手，

　　這里我們先假設(shè)B+樹高為2，即存在一個(gè)根節(jié)點(diǎn)和若干個(gè)葉子節(jié)點(diǎn)，那么 B+ 樹只有兩層。

　　如下圖：

　　那么對(duì)于這棵 B+ 樹能夠存放多少行數(shù)據(jù)，其實(shí)問的就是這棵 B+ 樹的非葉子節(jié)點(diǎn)中存放的數(shù)據(jù)量，

　　那么，這棵簡單的 B+ 樹能夠存放多少行數(shù)據(jù)，其實(shí)問的就是這棵 B+ 樹的非葉子節(jié)點(diǎn)中存放的數(shù)據(jù)量，

　　這棵B+樹的存放總記錄數(shù)為, 是一個(gè)簡單的公式：

　　每個(gè)葉子節(jié)點(diǎn)存放的行記錄數(shù)就是每頁存放的記錄數(shù)，由于各個(gè)數(shù)據(jù)表中的字段數(shù)量都不一樣，

　　這里我們就不深究葉子節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)了，

　　簡單按照一行記錄的數(shù)據(jù)大小為 1k 來算的話（實(shí)際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)記錄大小通常就是 1K 左右），

　　一頁（16K）或者說一個(gè)葉子節(jié)點(diǎn)可以存放 16 行這樣的數(shù)據(jù)。

　　那么 ，這顆B+ 樹 的非葉子節(jié)點(diǎn)（ 唯一的）能夠存儲(chǔ)多少數(shù)據(jù)呢？

　　非葉子節(jié)點(diǎn)里面存的是主鍵值 + 指針

　　為了方便分析，這里我們把一個(gè)主鍵值 + 一個(gè)指針稱為一個(gè)單元，我們假設(shè)主鍵的類型是 BigInt，長度為 8 字節(jié)，而指針大小在 InnoDB 中設(shè)置為 6 字節(jié)，

　　這樣一個(gè)單元，一共 14 字節(jié)。

　　這樣的話，一頁或者說一個(gè)非葉子節(jié)點(diǎn)能夠存放 16384 / 14=1170 個(gè)這樣的單元。

　　也就是說一個(gè)非葉子節(jié)點(diǎn)中能夠存放 1170 個(gè)指針，即對(duì)應(yīng) 1170 個(gè)葉子節(jié)點(diǎn)，

　　所以對(duì)于這樣一棵高度為 2 的 B+ 樹，能存放 1170（一個(gè)非葉子節(jié)點(diǎn)中的指針數(shù)） * 16（一個(gè)葉子節(jié)點(diǎn)中的行數(shù)）= 18720 行數(shù)據(jù)。

　　當(dāng)然，這樣分析其實(shí)不是很嚴(yán)謹(jǐn)，InnoDB 數(shù)據(jù)頁結(jié)構(gòu)，不全是 主鍵值 + 一個(gè)指針，還有其他的一些 元數(shù)據(jù)。

　　按照 《MySQL 技術(shù)內(nèi)幕：InnoDB 存儲(chǔ)引擎》中的定義，InnoDB 數(shù)據(jù)頁結(jié)構(gòu)包含如下幾個(gè)部分：

　　分析完高度為 2 的 B+ 樹，同樣的道理，我們來看高度為 3 的：

　　根頁（page10）可以存放 1170 個(gè)指針，

　　然后第二層的每個(gè)頁（page:11,12,13）也都分別可以存放1170個(gè)指針。

　　這樣一共可以存放 1170 * 1170 個(gè)指針，

　　即對(duì)應(yīng)的有 1170 * 1170 個(gè)非葉子節(jié)點(diǎn)，

　　所以，高為3的B+樹一共可以存放 1170 * 1170 * 16 = 21902400 行記錄。

　　回到問題，InnoDB 一棵 B+ 樹可以存放多少行數(shù)據(jù)？

　　這個(gè)問題的簡單回答是：約 2 千萬。

　　在InnoDB 引擎中，實(shí)際的情況如何呢？

　　在InnoDB的表空間文件中，約定page number為3的代表主鍵索引的根頁，而在根頁偏移量為64的地方存放了該B+樹的page level。

　　如果page level為1，樹高為2，page level為2，則樹高為3。

　　即B+樹的高度=page level+1；

　　下面我們將從實(shí)際環(huán)境中嘗試找到這個(gè)page level。

　　實(shí)驗(yàn)環(huán)境中，這三張表的數(shù)據(jù)量如下：

　　從圖中可以看到，一個(gè)表600W，一個(gè)表 15W，一個(gè)表5行數(shù)據(jù)。

　　在實(shí)際操作之前，你可以通過InnoDB元數(shù)據(jù)表確認(rèn)主鍵索引根頁的page number為3，你也可以從《InnoDB存儲(chǔ)引擎》這本書中得到確認(rèn)。

　　說明：

　　information_schema是mysql自帶的一個(gè)信息數(shù)據(jù)庫，其保存著關(guān)于mysql服務(wù)器所維護(hù)的所有其他數(shù)據(jù)庫的信息，如數(shù)據(jù)庫名，數(shù)據(jù)庫的表，表欄的數(shù)據(jù)類型與訪問權(quán)限等。innodb_sys_indexes：innodb表的索引的相關(guān)信息innodb_sys_tables：表格的格式和存儲(chǔ)特性，包括行格式，壓縮頁面大小位級(jí)別的信息

　　執(zhí)行結(jié)果：

　　可以看出數(shù)據(jù)庫dbt3下的customer表、lineitem表主鍵索引根頁的page number均為3，而其他的二級(jí)索引page number為4。

　　在進(jìn)行深入分析之前，首先回顧一下基礎(chǔ)知識(shí)

　　數(shù)據(jù)表的主鍵列使用的就是主鍵索引。一張數(shù)據(jù)表有只能有一個(gè)主鍵，并且主鍵不能為 null，不能重復(fù)。

　　在 MySQL 的 InnoDB 的表中，當(dāng)沒有顯示的指定表的主鍵時(shí)，InnoDB 會(huì)自動(dòng)先檢查表中是否有唯一索引的字段，如果有，則選擇該字段為默認(rèn)的主鍵，否則 InnoDB 將會(huì)自動(dòng)創(chuàng)建一個(gè) 6Byte 的自增主鍵。

　　二級(jí)索引又稱為輔助索引，是因?yàn)槎?jí)索引的葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是主鍵。也就是說，通過二級(jí)索引，可以定位主鍵的位置。常用的二級(jí)索引包括：唯一索引(Unique Key) ：唯一索引也是一種約束。唯一索引的屬性列不能出現(xiàn)重復(fù)的數(shù)據(jù)，但是允許數(shù)據(jù)為 NULL，一張表允許創(chuàng)建多個(gè)唯一索引。 建立唯一索引的目的大部分時(shí)候都是為了該屬性列的數(shù)據(jù)的唯一性，而不是為了查詢效率。普通索引(Index) ：普通索引的唯一作用就是為了快速查詢數(shù)據(jù)，一張表允許創(chuàng)建多個(gè)普通索引，并允許數(shù)據(jù)重復(fù)和 NULL。前綴索引(Prefix) ：前綴索引只適用于字符串類型的數(shù)據(jù)。前綴索引是對(duì)文本的前幾個(gè)字符創(chuàng)建索引，相比普通索引建立的數(shù)據(jù)更小， 因?yàn)橹蝗∏皫讉€(gè)字符。

　　從物理意義上來講，InnoDB表由共享表空間文件（ibdata1）、獨(dú)占表空間文件（ibd）、表結(jié)構(gòu)文件（.frm）、以及日志文件（redo文件等）組成。

　　在MYSQL中建立任何一張數(shù)據(jù)表，在其數(shù)據(jù)目錄對(duì)應(yīng)的數(shù)據(jù)庫目錄下都有對(duì)應(yīng)表的.frm文件

　　.frm文件是用來保存每個(gè)數(shù)據(jù)表的元數(shù)據(jù)(meta)信息，包括表結(jié)構(gòu)的定義等，

　　.frm文件跟數(shù)據(jù)庫存儲(chǔ)引擎無關(guān)，也就是任何存儲(chǔ)引擎的數(shù)據(jù)表都必須有.frm文件，

　　命名方式為數(shù)據(jù)表名.frm，如user.frm. ， .frm文件可以用來在數(shù)據(jù)庫崩潰時(shí)恢復(fù)表結(jié)構(gòu)。

　?。?）表空間結(jié)構(gòu)分析

　　以下為InnoDB的表空間結(jié)構(gòu)圖：

　　數(shù)據(jù)段即B+樹的葉子節(jié)點(diǎn)，索引段即為B+樹的非葉子節(jié)點(diǎn)InnoDB存儲(chǔ)引擎的管理是由引擎本身完成的，

　　表空間（Tablespace）是由分散的段(Segment)組成。一個(gè)段(Segment)包含多個(gè)區(qū)（Extent）。

　　區(qū)（Extent）由64個(gè)連續(xù)的頁（Page）組成，每個(gè)頁大小為16K，即每個(gè)區(qū)大小為1MB，創(chuàng)建新表時(shí)，先使用32頁大小的碎片頁存放數(shù)據(jù)，使用完后才是區(qū)的申請(qǐng)（InnoDB最多每次申請(qǐng)4個(gè)區(qū)，保證數(shù)據(jù)的順序性能）頁類型有：數(shù)據(jù)頁、Undo頁、系統(tǒng)頁、事務(wù)數(shù)據(jù)頁、插入緩沖位圖頁、以及插入緩沖空閑列表頁。

　?。?）獨(dú)占表空間文件

　　若將innodb_file_per_table設(shè)置為on，則系統(tǒng)將為每一個(gè)表單獨(dú)的生成一個(gè)table_name.ibd的文件，

　　在此文件中，存儲(chǔ)與該表相關(guān)的數(shù)據(jù)、索引、表的內(nèi)部數(shù)據(jù)字典信息。

　?。?）共享表空間文件

　　在InnoDB存儲(chǔ)引擎中，默認(rèn)表空間文件是ibdata1（主要存儲(chǔ)的是共享表空間數(shù)據(jù)），初始化為10M，且可以擴(kuò)展，如下圖所示：

　　實(shí)際上，InnoDB的表空間文件是可以修改的，使用以下語句就可以修改：

　　使用共享表空間存儲(chǔ)方式時(shí)，Innodb的所有數(shù)據(jù)保存在一個(gè)單獨(dú)的表空間里面，而這個(gè)表空間可以由很多個(gè)文件組成，一個(gè)表可以跨多個(gè)文件存在，所以其大小限制不再是文件大小的限制，而是其自身的限制。

　　從Innodb的官方文檔中可以看到，其表空間的最大限制為64TB，也就是說，Innodb的單表限制基本上也在64TB左右了，當(dāng)然這個(gè)大小是包括這個(gè)表的所有索引等其他相關(guān)數(shù)據(jù)。

　　而在使用單獨(dú)表空間存儲(chǔ)方式時(shí)，每個(gè)表的數(shù)據(jù)以一個(gè)單獨(dú)的文件來存放，這個(gè)時(shí)候的單表限制，又變成文件系統(tǒng)的大小限制了。

　　了解了這些基礎(chǔ)知識(shí)之后，下面我們對(duì)數(shù)據(jù)庫表空間文件做相關(guān)的解析， 主要是針對(duì)獨(dú)占獨(dú)占表空間文件（ibd）

　　因?yàn)橹麈I索引B+樹的根頁，在整個(gè)表空間文件中的第3個(gè)頁開始，所以可以算出它在文件中的偏移量：

　　另外根據(jù)《InnoDB存儲(chǔ)引擎》中描述在根頁的64偏移量位置前2個(gè)字節(jié)，保存了page level的值，

　　因此我們想要的page level的值在整個(gè)文件中的偏移量為：16384*3+64=49152+64=49216，前2個(gè)字節(jié)中。

　　接下來我們用hexdump工具，查看表空間文件指定偏移量上的數(shù)據(jù)：

　　linetem表的page level為2，B+樹高度為page level+1=3；

　　region表的page level為0，B+樹高度為page level+1=1；

　　customer表的page level為2，B+樹高度為page level+1=3；

　　總結(jié)，通過分析可以看到，實(shí)驗(yàn)環(huán)境的三個(gè)表：lineitem表的數(shù)據(jù)行數(shù)為600多萬，B+樹高度為3，customer表數(shù)據(jù)行數(shù)只有15萬，B+樹高度也為3。

　　可以看出盡管數(shù)據(jù)量差異較大，這兩個(gè)表樹的高度都是3，換句話說這兩個(gè)表通過索引查詢效率并沒有太大差異，因?yàn)槎贾恍枰?次IO。

　　所以在InnoDB中B+樹高度一般為1-3層，它就能滿足千萬級(jí)的數(shù)據(jù)存儲(chǔ)。

　　在查找數(shù)據(jù)時(shí)一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。

　　前面分析了，假設(shè)主鍵ID為bigint類型，長度為8字節(jié)，

　　而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，這樣一共14字節(jié)。

　　那么一個(gè)頁中能存放多少這樣的組合，就代表有多少指針，即 16384 / 14 = 1170。

　　那么可以算出一棵高度為2 的B+樹，能存放 1170 * 16 = 18720 條這樣的數(shù)據(jù)記錄。

　　同理：

　　高度為3的B+樹可以存放的行數(shù) = 1170 * 1170 * 16 = 21902400

　　所以，千萬級(jí)的數(shù)據(jù)存儲(chǔ)只需要約3層B+樹，所以說，根據(jù)主鍵id索引查詢約3次IO便可以找到目標(biāo)結(jié)果。

　　注意：查詢數(shù)據(jù)時(shí)，每加載一頁（page）代表一次IO，

　　當(dāng)然 B+樹的根節(jié)點(diǎn)是常駐內(nèi)存的，這里少了一次IO。

　　但是，我們?yōu)槔阌诜治?，在分析的時(shí)候，暫時(shí)不管吧，先看一般情況。

　　對(duì)于一些復(fù)雜的查詢，可能需要走二級(jí)索引，那么通過二級(jí)索引查找記錄最多需要花費(fèi)多少次IO呢？

　　首先，從二級(jí)索引B+樹中，根據(jù)name 找到對(duì)應(yīng)的主鍵id

　　然后，再根據(jù)主鍵id 從 聚簇索引查找到對(duì)應(yīng)的記錄。

　　如上圖所示，二級(jí)索引有3層，聚簇索引有3層，那么最多花費(fèi)的IO次數(shù)是：3+3 = 6 （這里，忽略根節(jié)點(diǎn)常駐內(nèi)存這件事）

　　聚簇索引默認(rèn)是主鍵，如果表中沒有定義主鍵，InnoDB 會(huì)選擇一個(gè)唯一的非空索引代替。

　　如果連這樣的索引沒有，InnoDB 會(huì)隱式定義一個(gè)主鍵來作為聚簇索引。

　　這也是為什么InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵！?。nnoDB使用的是聚簇索引，將主鍵組織到一棵B+樹中，而行數(shù)據(jù)就儲(chǔ)存在葉子節(jié)點(diǎn)上

　　為啥磁盤IO的性能低？ 不多說啦，具體請(qǐng)參考 的《Java葵花寶典：Java 高性能超底層原理》 視頻和講義，需要的請(qǐng)后臺(tái)私信【筆記】即可獲??！

　　通過上面的分析可以看出， 如果是 走 非聚集索引查詢， 需要6次IO，

　　走 聚焦索引查詢，需要3次磁盤IO

　　當(dāng)然，以上分析流程，忽略了一些性能的優(yōu)化措施，比如 B+樹根節(jié)點(diǎn) 常駐內(nèi)存，還有可能命中 查詢緩存等等。

　　所以，innodb 單表推薦2kw 記錄，超過了這個(gè)值可能會(huì)導(dǎo)致B+樹層級(jí)更高，影響查詢性能。

　　當(dāng)然，凡事看場景，上面只是一般的分析。

　　索引結(jié)構(gòu)不會(huì)影響單表最大行數(shù)，2kw也只是推薦值，最終的單表記錄數(shù)最大值，受到硬件條件，和各種優(yōu)化措施的影響。

　　只要按照上面的 流程去作答， 你的答案不是 100分，而是 120分

　　面試官一定是 心滿意足， 五體投地。。。">