面試題：mysql 一棵 B+ 樹(shù)能存多少條數(shù)據(jù)？

（答案在文章中?。。?/span>

要搞清楚這個(gè)問(wèn)題，首先要從InnoDB索引數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)組織方式說(shuō)起。

我們都知道計(jì)算機(jī)有五大組成部分：控制器，運(yùn)算器，存儲(chǔ)器，輸入設(shè)備，輸出設(shè)備。

其中很重要的，也跟今天這個(gè)題目有關(guān)系的是存儲(chǔ)器。

我們知道萬(wàn)事萬(wàn)物都有自己的單元體系，若干個(gè)小單體組成一個(gè)個(gè)大的個(gè)體。就像拼樂(lè)高一樣，可以自由組合。所以說(shuō)，如果能熟悉最小單元，就意味著我們抓住了事物的本事，再?gòu)?fù)雜的問(wèn)題也會(huì)迎刃而解。

存儲(chǔ)器范圍比較大，但是數(shù)據(jù)具體怎么存儲(chǔ)，有自己的最小存儲(chǔ)單元。

1、數(shù)據(jù)持久化存儲(chǔ)磁盤里，磁盤的最小單元是扇區(qū)，一個(gè)扇區(qū)的大小是 512個(gè)字節(jié)

2、文件系統(tǒng)的最小單元是塊，一個(gè)塊的大小是 4K

3、InnoDB存儲(chǔ)引擎，有自己的最小單元，稱之為頁(yè)，一個(gè)頁(yè)的大小是16K

扇區(qū)、塊、頁(yè)這三者的存儲(chǔ)關(guān)系？

如果mysql部署在本地，通過(guò)命令行方式連接mysql，默認(rèn)的端口 3306 ，然后輸入密碼即可進(jìn)入

mysql?-u?root?-p

查看InnoDB的頁(yè)大小

show?variables?like?'innodb_page_size';

mysql數(shù)據(jù)庫(kù)中，table表中的記錄都是存儲(chǔ)在頁(yè)中，那么一頁(yè)可以存多少行數(shù)據(jù)？假如一行數(shù)據(jù)的大小約為1K字節(jié)，那么按 16K / 1K = 16，可以計(jì)算出一頁(yè)大約能存放16條數(shù)據(jù)。

mysql 的最小存儲(chǔ)單元叫做“頁(yè)”，這么多的頁(yè)是如何構(gòu)建一個(gè)龐大的數(shù)據(jù)組織，我們又如何知道數(shù)據(jù)存儲(chǔ)在哪一個(gè)頁(yè)中？

如果逐條遍歷，性能肯定很差。為了提升查找速度，我們引入了B+樹(shù)，先來(lái)看下B+樹(shù)的存儲(chǔ)結(jié)構(gòu)

頁(yè)除了可以存放數(shù)據(jù)（葉子節(jié)點(diǎn)），還可以存放健值和指針（非葉子節(jié)點(diǎn)），當(dāng)然他們是有序的。這樣的數(shù)據(jù)組織形式，我們稱為索引組織表。

如：上圖中 page number=3的頁(yè)，該頁(yè)存放鍵值和指向數(shù)據(jù)頁(yè)的指針，這樣的頁(yè)由N個(gè)鍵值+指針組成

B+ 樹(shù)是如何檢索記錄？

• 首先找到根頁(yè)，你怎么知道一張表的根頁(yè)在哪呢？
• 其實(shí)每張表的根頁(yè)位置在表空間文件中是固定的，即page number=3的頁(yè)
• 找到根頁(yè)后通過(guò)二分查找法，定位到id=5的數(shù)據(jù)應(yīng)該在指針P5指向的頁(yè)中
• 然后再去page number=5的頁(yè)中查找，同樣通過(guò)二分查詢法即可找到id=5的記錄

在InnoDB 的表空間文件中，約定page number = 3表示主鍵索引的根頁(yè)

SELECT
b.name,?a.name,?index_id,?type,?a.space,?a.PAGE_NO
FROM
information_schema.INNODB_SYS_INDEXES?a,
information_schema.INNODB_SYS_TABLES?b
WHERE
a.table_id?=?b.table_id?AND?a.space?<>?0
and?b.name?like?'%sp_job_log';

從圖中可以看出，每個(gè)表的主鍵索引的根頁(yè)的page number都是3，而其他的二級(jí)索引page number為4

在根頁(yè)偏移量為64的地方存放了該B+樹(shù)的page level。主鍵索引B+樹(shù)的根頁(yè)在整個(gè)表空間文件中的第3個(gè)頁(yè)開(kāi)始，所以算出它在文件中的偏移量：16384*3 + 64 = 49152 + 64 =49216，前2個(gè)字節(jié)中。

首先，找到MySql數(shù)據(jù)庫(kù)物理文件存放位置：

show?global?variables?like?"%datadir%"?;

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

hexdump?-s?49216?-n?10??sp_job_log.ibd

page_level 值是 1，那么 B+樹(shù)高度為 page level + 1 = 2

特別說(shuō)明：

• 查詢數(shù)據(jù)庫(kù)時(shí)，不論讀一行，還是讀多行，都是將這些行所在的整頁(yè)數(shù)據(jù)加載，然后在內(nèi)存中匹配過(guò)濾出最終結(jié)果。

• 表的檢索速度跟樹(shù)的深度有直接關(guān)系，畢竟一次頁(yè)加載就是一次IO，而磁盤IO又是比較費(fèi)時(shí)間。對(duì)于一張千萬(wàn)級(jí)條數(shù)B+樹(shù)高度為3的表與幾十萬(wàn)級(jí)B+樹(shù)高度也為3的表，其實(shí)查詢效率相差不大。

假設(shè)B+樹(shù)的深度為2

這棵B+樹(shù)的存儲(chǔ)總記錄數(shù) = 根節(jié)點(diǎn)指針數(shù) * 單個(gè)葉子節(jié)點(diǎn)記錄條數(shù)

那么指針數(shù)如何計(jì)算？

假設(shè)主鍵ID為bigint類型，長(zhǎng)度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，這樣一共14字節(jié)。

那么一個(gè)頁(yè)中能存放多少這樣的組合，就代表有多少指針，即 16384 / 14 = 1170。那么可以算出一棵高度為2 的B+樹(shù)，能存放 1170 * 16 = 18720 條這樣的數(shù)據(jù)記錄。

同理：

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

千萬(wàn)級(jí)的數(shù)據(jù)存儲(chǔ)只需要約3層B+樹(shù)，查詢數(shù)據(jù)時(shí)，每加載一頁(yè)（page）代表一次IO。所以說(shuō)，根據(jù)主鍵id索引查詢約3次IO便可以找到目標(biāo)結(jié)果。

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

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

然后，再根據(jù)主鍵id 從 聚簇索引查找到對(duì)應(yīng)的記錄。如上圖所示，二級(jí)索引有3層，聚簇索引有3層，那么最多花費(fèi)的IO次數(shù)是：3+3 = 6

聚簇索引默認(rèn)是主鍵，如果表中沒(méi)有定義主鍵，InnoDB 會(huì)選擇一個(gè)唯一的非空索引代替。如果沒(méi)有這樣的索引，InnoDB 會(huì)隱式定義一個(gè)主鍵來(lái)作為聚簇索引。

這也是為什么InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵！?。?/p>

InnoDB使用的是聚簇索引，將主鍵組織到一棵B+樹(shù)中，而行數(shù)據(jù)就儲(chǔ)存在葉子節(jié)點(diǎn)上

舉例說(shuō)明：

1、若使用"where id = 14"這樣的條件查找記錄，則按照B+樹(shù)的檢索算法即可查找到對(duì)應(yīng)的葉節(jié)點(diǎn)，之后獲得行數(shù)據(jù)。

2、若對(duì)Name列進(jìn)行條件搜索，則需要兩個(gè)步驟：

• 第一步在輔助索引B+樹(shù)中檢索Name，到達(dá)其葉子節(jié)點(diǎn)獲取對(duì)應(yīng)的主鍵值。
• 第二步使用主鍵值在主索引B+樹(shù)中再執(zhí)行一次B+樹(shù)檢索操作，最終到達(dá)葉子節(jié)點(diǎn)即可獲取整行數(shù)據(jù)。（重點(diǎn)在于通過(guò)其他鍵需要建立輔助索引）
  
  
  
  

實(shí)際項(xiàng)目中，每個(gè)表的結(jié)構(gòu)設(shè)計(jì)都不一樣，占用的存儲(chǔ)空間大小也各不相等。如何計(jì)算不同的B+樹(shù)深度下，一個(gè)表可以存儲(chǔ)的記錄條數(shù)？

我們以業(yè)務(wù)日志表 sp_job_log 為例，講解詳細(xì)的計(jì)算過(guò)程：

1、查看表的狀態(tài)信息

show?table?status?like?'sp_job_log'\G

圖中看到sp_job_log表的行平均大小為153個(gè)字節(jié)

2、查看表結(jié)構(gòu)

desc?sp_job_log;

3、計(jì)算B+樹(shù)的行數(shù)

• 單個(gè)葉子節(jié)點(diǎn)（頁(yè)）中的記錄數(shù) = 16K / 153 = 105
• 非葉子節(jié)點(diǎn)能存放多少指針， 16384 / 14 = 1170
• 如果樹(shù)的高度為3，可以存放的記錄行數(shù) = ?1170 * 1170 * 105 = 143,734,500

普通索引和唯一索引在查詢效率上有什么不同？

唯一索引就是在普通索引上增加了約束性，也就是關(guān)鍵字唯一，找到了關(guān)鍵字就停止檢索。而普通索引，可能會(huì)存在用戶記錄中的關(guān)鍵字相同的情況，根據(jù)頁(yè)結(jié)構(gòu)的原理，當(dāng)我們讀取一條記錄的時(shí)候，不是單獨(dú)將這條記錄從磁盤中讀出去，而是將這個(gè)記錄所在的頁(yè)全部加載到內(nèi)存中進(jìn)行讀取。InnoDB 存儲(chǔ)引擎的頁(yè)大小為 16KB，在一個(gè)頁(yè)中可能存儲(chǔ)著上千個(gè)記錄，因此在普通索引的字段上進(jìn)行查找也就是在內(nèi)存中多幾次判斷下一條記錄的操作，對(duì)于 CPU 來(lái)說(shuō)，這些操作所消耗的時(shí)間是可以忽略不計(jì)的。所以對(duì)一個(gè)索引字段進(jìn)行檢索，采用普通索引還是唯一索引在檢索效率上基本上沒(méi)有差別。

-- End --