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

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

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

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

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

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

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

　　問題N： ... 第100個變種

　　前段時間，有一個小伙伴在面美團里的時候，又遇到了此問題。

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

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

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

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

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

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

　　注：本文以 PDF 持續(xù)更新，最新Java 架構筆記、面試題 的PDF文件，請后臺私信【筆記】即可獲??！

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

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

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

　　來一個圖，更清楚：

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

　　面試官一聽，感覺你的計算機底層知識是多么的扎實，好感慢慢。這是來自 老架構師的 衷心提示。

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

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

　　具體如下圖：

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

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

　　具體如下圖：

　　InnoDB 存儲引擎 的最小儲存單元——頁（Page），一個頁的大小是 16K，

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

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

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

　　先做一個假設：

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

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

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

　　因為我們不知道要查找的數(shù)據(jù)存在哪個頁中，也不可能把所有的頁遍歷一遍，那樣太慢了。

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

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

　　如圖所示：

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

　　我們總結(jié)一下：

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

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

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

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

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

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

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

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

　　如下圖：

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

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

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

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

　　這里我們就不深究葉子節(jié)點的存儲結(jié)構了，

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

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

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

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

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

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

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

　　也就是說一個非葉子節(jié)點中能夠存放 1170 個指針，即對應 1170 個葉子節(jié)點，

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

　　當然，這樣分析其實不是很嚴謹，InnoDB 數(shù)據(jù)頁結(jié)構，不全是 主鍵值 + 一個指針，還有其他的一些 元數(shù)據(jù)。

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

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

　　根頁（page10）可以存放 1170 個指針，

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

　　這樣一共可以存放 1170 * 1170 個指針，

　　即對應的有 1170 * 1170 個非葉子節(jié)點，

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

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

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

　　在InnoDB 引擎中，實際的情況如何呢？

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

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

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

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

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

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

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

　　說明：

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

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

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

　　在進行深入分析之前，首先回顧一下基礎知識

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

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

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

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

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

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

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

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

　　（1）表空間結(jié)構分析

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

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

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

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

　?。?）獨占表空間文件

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

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

　?。?）共享表空間文件

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

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

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

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

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

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

　　因為主鍵索引B+樹的根頁，在整個表空間文件中的第3個頁開始，所以可以算出它在文件中的偏移量：

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

　　因此我們想要的page level的值在整個文件中的偏移量為：16384*3+64=49152+64=49216，前2個字節(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é)，通過分析可以看到，實驗環(huán)境的三個表：lineitem表的數(shù)據(jù)行數(shù)為600多萬，B+樹高度為3，customer表數(shù)據(jù)行數(shù)只有15萬，B+樹高度也為3。

　　可以看出盡管數(shù)據(jù)量差異較大，這兩個表樹的高度都是3，換句話說這兩個表通過索引查詢效率并沒有太大差異，因為都只需要做3次IO。

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

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

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

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

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

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

　　同理：

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

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

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

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

　　但是，我們?yōu)槔阌诜治觯诜治龅臅r候，暫時不管吧，先看一般情況。

　　對于一些復雜的查詢，可能需要走二級索引，那么通過二級索引查找記錄最多需要花費多少次IO呢？

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

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

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

　　聚簇索引默認是主鍵，如果表中沒有定義主鍵，InnoDB 會選擇一個唯一的非空索引代替。

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

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

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

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

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

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

　　所以，innodb 單表推薦2kw 記錄，超過了這個值可能會導致B+樹層級更高，影響查詢性能。

　　當然，凡事看場景，上面只是一般的分析。

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

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

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