? 在瘋狂創(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:?jiǎn)伪沓^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ǔ)存單元——頁(yè)(Page),一個(gè)頁(yè)的大小是 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ǔ)存單元——頁(yè)(Page),一個(gè)頁(yè)的大小是 16K,
在 MySQL 中我們的InnoDB 頁(yè)的大小當(dāng)然也可以通過參數(shù)設(shè)置的,具體如下圖:
通過上圖,可以看到,在 MySQL 中我們的 InnoDB 頁(yè)的大小默認(rèn)是 16k
數(shù)據(jù)表中的數(shù)據(jù)都是存儲(chǔ)在頁(yè)中的,所以一個(gè)頁(yè)中能存儲(chǔ)多少行數(shù)據(jù)呢?
先做一個(gè)假設(shè):
假設(shè)一行數(shù)據(jù)的大小是1k,
那么一個(gè)16K頁(yè),可以存放16行這樣的數(shù)據(jù)。
如果數(shù)據(jù)庫(kù)只按這樣的方式存儲(chǔ),那么如何查找數(shù)據(jù)就成為一個(gè)問題
因?yàn)槲覀儾恢酪檎业臄?shù)據(jù)存在哪個(gè)頁(yè)中,也不可能把所有的頁(yè)遍歷一遍,那樣太慢了。
所以人們想了一個(gè)辦法,用B+樹的方式組織這些數(shù)據(jù)。B+ 樹的葉子節(jié)點(diǎn)存儲(chǔ)真正的記錄,對(duì)應(yīng)的文件系統(tǒng) page頁(yè)面,可以叫做 數(shù)據(jù)頁(yè)B+ 樹的非葉子節(jié)點(diǎn)存放的是鍵值 + 指針,其對(duì)應(yīng)的文件系統(tǒng) page頁(yè)面,可以叫做 索引頁(yè)
這里用指針來描其實(shí)述不是太準(zhǔn)確,準(zhǔn)確來說是頁(yè)的偏移量,不過借用指針一詞,更好理解
如圖所示:
InnoDB中主鍵索引B+樹是如何組織數(shù)據(jù)、查詢數(shù)據(jù)的?
我們總結(jié)一下:
1、在B+樹中葉子節(jié)點(diǎn)存放數(shù)據(jù),非葉子節(jié)點(diǎn)存放鍵值+指針。
InnoDB存儲(chǔ)引擎的最小存儲(chǔ)單元是頁(yè),頁(yè)可以用于存放數(shù)據(jù)也可以用于存放鍵值+指針,
2、頁(yè)內(nèi)的記錄是有序的,所以可以使用二分查找在頁(yè)內(nèi)到下一層的目標(biāo)頁(yè)面的指針從根頁(yè)開始,首先通過非葉子節(jié)點(diǎn)的二分查找法,確定數(shù)據(jù)在下一層哪個(gè)頁(yè)之后,一層一層往下找,一直到非葉子節(jié)點(diǎn),進(jìn)而在非葉子節(jié)(數(shù)據(jù)頁(yè))中查找到需要的數(shù)據(jù);
那么回到我們開始的問題,通常一棵B+樹可以存放多少行數(shù)據(jù)?
首先,需要計(jì)算出非葉子節(jié)點(diǎn)能存放多少指針?
頁(yè)作為 InnoDB 磁盤管理的最小單位,不僅可以用來存放具體的行數(shù)據(jù),還可以存放鍵值和指針。
回到文題,我們先從簡(jiǎn)單的入手,
這里我們先假設(shè)B+樹高為2,即存在一個(gè)根節(jié)點(diǎn)和若干個(gè)葉子節(jié)點(diǎn),那么 B+ 樹只有兩層。
如下圖:
那么對(duì)于這棵 B+ 樹能夠存放多少行數(shù)據(jù),其實(shí)問的就是這棵 B+ 樹的非葉子節(jié)點(diǎn)中存放的數(shù)據(jù)量,
那么,這棵簡(jiǎn)單的 B+ 樹能夠存放多少行數(shù)據(jù),其實(shí)問的就是這棵 B+ 樹的非葉子節(jié)點(diǎn)中存放的數(shù)據(jù)量,
這棵B+樹的存放總記錄數(shù)為, 是一個(gè)簡(jiǎn)單的公式:
每個(gè)葉子節(jié)點(diǎn)存放的行記錄數(shù)就是每頁(yè)存放的記錄數(shù),由于各個(gè)數(shù)據(jù)表中的字段數(shù)量都不一樣,
這里我們就不深究葉子節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)了,
簡(jiǎn)單按照一行記錄的數(shù)據(jù)大小為 1k 來算的話(實(shí)際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)記錄大小通常就是 1K 左右),
一頁(yè)(16K)或者說一個(gè)葉子節(jié)點(diǎn)可以存放 16 行這樣的數(shù)據(jù)。
那么 ,這顆B+ 樹 的非葉子節(jié)點(diǎn)( 唯一的)能夠存儲(chǔ)多少數(shù)據(jù)呢?
非葉子節(jié)點(diǎn)里面存的是主鍵值 + 指針
為了方便分析,這里我們把一個(gè)主鍵值 + 一個(gè)指針稱為一個(gè)單元,我們假設(shè)主鍵的類型是 BigInt,長(zhǎng)度為 8 字節(jié),而指針大小在 InnoDB 中設(shè)置為 6 字節(jié),
這樣一個(gè)單元,一共 14 字節(jié)。
這樣的話,一頁(yè)或者說一個(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ù)頁(yè)結(jié)構(gòu),不全是 主鍵值 + 一個(gè)指針,還有其他的一些 元數(shù)據(jù)。
按照 《MySQL 技術(shù)內(nèi)幕:InnoDB 存儲(chǔ)引擎》中的定義,InnoDB 數(shù)據(jù)頁(yè)結(jié)構(gòu)包含如下幾個(gè)部分:
分析完高度為 2 的 B+ 樹,同樣的道理,我們來看高度為 3 的:
根頁(yè)(page10)可以存放 1170 個(gè)指針,
然后第二層的每個(gè)頁(yè)(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è)問題的簡(jiǎn)單回答是:約 2 千萬。
在InnoDB 引擎中,實(shí)際的情況如何呢?
在InnoDB的表空間文件中,約定page number為3的代表主鍵索引的根頁(yè),而在根頁(yè)偏移量為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)主鍵索引根頁(yè)的page number為3,你也可以從《InnoDB存儲(chǔ)引擎》這本書中得到確認(rèn)。
說明:
information_schema是mysql自帶的一個(gè)信息數(shù)據(jù)庫(kù),其保存著關(guān)于mysql服務(wù)器所維護(hù)的所有其他數(shù)據(jù)庫(kù)的信息,如數(shù)據(jù)庫(kù)名,數(shù)據(jù)庫(kù)的表,表欄的數(shù)據(jù)類型與訪問權(quán)限等。innodb_sys_indexes:innodb表的索引的相關(guān)信息innodb_sys_tables:表格的格式和存儲(chǔ)特性,包括行格式,壓縮頁(yè)面大小位級(jí)別的信息
執(zhí)行結(jié)果:
可以看出數(shù)據(jù)庫(kù)dbt3下的customer表、lineitem表主鍵索引根頁(yè)的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ù)庫(kù)目錄下都有對(duì)應(yīng)表的.frm文件
.frm文件是用來保存每個(gè)數(shù)據(jù)表的元數(shù)據(jù)(meta)信息,包括表結(jié)構(gòu)的定義等,
.frm文件跟數(shù)據(jù)庫(kù)存儲(chǔ)引擎無關(guān),也就是任何存儲(chǔ)引擎的數(shù)據(jù)表都必須有.frm文件,
命名方式為數(shù)據(jù)表名.frm,如user.frm. , .frm文件可以用來在數(shù)據(jù)庫(kù)崩潰時(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ù)的頁(yè)(Page)組成,每個(gè)頁(yè)大小為16K,即每個(gè)區(qū)大小為1MB,創(chuàng)建新表時(shí),先使用32頁(yè)大小的碎片頁(yè)存放數(shù)據(jù),使用完后才是區(qū)的申請(qǐng)(InnoDB最多每次申請(qǐng)4個(gè)區(qū),保證數(shù)據(jù)的順序性能)頁(yè)類型有:數(shù)據(jù)頁(yè)、Undo頁(yè)、系統(tǒng)頁(yè)、事務(wù)數(shù)據(jù)頁(yè)、插入緩沖位圖頁(yè)、以及插入緩沖空閑列表頁(yè)。
?。?)獨(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的表空間文件是可以修改的,使用以下語(yǔ)句就可以修改:
使用共享表空間存儲(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ù)庫(kù)表空間文件做相關(guān)的解析, 主要是針對(duì)獨(dú)占獨(dú)占表空間文件(ibd)
因?yàn)橹麈I索引B+樹的根頁(yè),在整個(gè)表空間文件中的第3個(gè)頁(yè)開始,所以可以算出它在文件中的偏移量:
另外根據(jù)《InnoDB存儲(chǔ)引擎》中描述在根頁(yè)的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í)一次頁(yè)的查找代表一次IO,所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。
前面分析了,假設(shè)主鍵ID為bigint類型,長(zhǎng)度為8字節(jié),
而指針大小在InnoDB源碼中設(shè)置為6字節(jié),這樣一共14字節(jié)。
那么一個(gè)頁(yè)中能存放多少這樣的組合,就代表有多少指針,即 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í),每加載一頁(yè)(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表必須有主鍵,并且推薦使用整型的自增主鍵?。?!InnoDB使用的是聚簇索引,將主鍵組織到一棵B+樹中,而行數(shù)據(jù)就儲(chǔ)存在葉子節(jié)點(diǎn)上
為啥磁盤IO的性能低? 不多說啦,具體請(qǐng)參考 的《Java葵花寶典:Java 高性能超底層原理》 視頻和講義,需要的請(qǐng)后臺(tái)私信【筆記】即可獲?。?br>
通過上面的分析可以看出, 如果是 走 非聚集索引查詢, 需要6次IO,
走 聚焦索引查詢,需要3次磁盤IO
當(dāng)然,以上分析流程,忽略了一些性能的優(yōu)化措施,比如 B+樹根節(jié)點(diǎn) 常駐內(nèi)存,還有可能命中 查詢緩存等等。
所以,innodb 單表推薦2kw 記錄,超過了這個(gè)值可能會(huì)導(dǎo)致B+樹層級(jí)更高,影響查詢性能。
當(dāng)然,凡事看場(chǎng)景,上面只是一般的分析。
索引結(jié)構(gòu)不會(huì)影響單表最大行數(shù),2kw也只是推薦值,最終的單表記錄數(shù)最大值,受到硬件條件,和各種優(yōu)化措施的影響。
只要按照上面的 流程去作答, 你的答案不是 100分,而是 120分
面試官一定是 心滿意足, 五體投地。。。
來自【網(wǎng)友】的網(wǎng)友評(píng)論
2018-03-05 18:56:31