[[403596]]

本文轉(zhuǎn)載自微信公眾號(hào)「微觀技術(shù)」，作者TomGE 。轉(zhuǎn)載本文請(qǐng)聯(lián)系微觀技術(shù)公眾號(hào)。

大家好，我是Tom哥~

今日寄語：充滿活力的新人，能讓身邊的人都重回初心，真是不可思議。

mysql 的InnoDB存儲(chǔ)引擎 一棵B+樹可以存放多少行數(shù)據(jù)?

[[403597]]

(答案在文章中!!)

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

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

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

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

存儲(chǔ)單元

存儲(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)系?

InnoDB引擎

如果mysql部署在本地，通過命令行方式連接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+樹，先來看下B+樹的存儲(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+ 樹是如何檢索記錄?

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

如何計(jì)算B+樹的高度?

在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+樹的page level。主鍵索引B+樹的根頁(yè)在整個(gè)表空間文件中的第3個(gè)頁(yè)開始，所以算出它在文件中的偏移量：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+樹高度為 page level + 1 = 2

特別說明：

• 查詢數(shù)據(jù)庫(kù)時(shí)，不論讀一行，還是讀多行，都是將這些行所在的整頁(yè)數(shù)據(jù)加載，然后在內(nèi)存中匹配過濾出最終結(jié)果。
• 表的檢索速度跟樹的深度有直接關(guān)系，畢竟一次頁(yè)加載就是一次IO，而磁盤IO又是比較費(fèi)時(shí)間。對(duì)于一張千萬級(jí)條數(shù)B+樹高度為3的表與幾十萬級(jí)B+樹高度也為3的表，其實(shí)查詢效率相差不大。

一棵樹可以存放多少行數(shù)據(jù)?

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

這棵B+樹的存儲(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+樹，能存放 1170 * 16 = 18720 條這樣的數(shù)據(jù)記錄。

同理：

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

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

對(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

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

這也是為什么InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵!!!

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

舉例說明：

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

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

第一步在輔助索引B+樹中檢索Name，到達(dá)其葉子節(jié)點(diǎn)獲取對(duì)應(yīng)的主鍵值。

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

實(shí)戰(zhàn)演示

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

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

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ù)

單個(gè)葉子節(jié)點(diǎn)(頁(yè))中的記錄數(shù) = 16K / 153 = 105

非葉子節(jié)點(diǎn)能存放多少指針， 16384 / 14 = 1170

如果樹的高度為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 來說，這些操作所消耗的時(shí)間是可以忽略不計(jì)的。所以對(duì)一個(gè)索引字段進(jìn)行檢索，采用普通索引還是唯一索引在檢索效率上基本上沒有差別。