[[403596]]

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

大家好，我是Tom哥~

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

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

[[403597]]

(答案在文章中!!)

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

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

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

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

存儲單元

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

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

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

3、InnoDB存儲引擎，有自己的最小單元，稱之為頁，一個頁的大小是16K

扇區(qū)、塊、頁這三者的存儲關(guān)系?

InnoDB引擎

如果mysql部署在本地，通過命令行方式連接mysql，默認的端口 3306 ，然后輸入密碼即可進入

mysql -u root -p 

查看InnoDB的頁大小

show variables like 'innodb_page_size'; 

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

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

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

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

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

B+ 樹是如何檢索記錄?

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

如何計算B+樹的高度?

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

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'; 

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

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

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

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

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

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

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

那么指針數(shù)如何計算?

假設(shè)主鍵ID為bigint類型，長度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為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+樹，查詢數(shù)據(jù)時，每加載一頁(page)代表一次IO。所以說，根據(jù)主鍵id索引查詢約3次IO便可以找到目標結(jié)果。

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

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

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

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

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

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

舉例說明：

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

2、若對Name列進行條件搜索，則需要兩個步驟：

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

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

實戰(zhàn)演示

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

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

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

show table status like 'sp_job_log'\G 

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

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

desc sp_job_log; 

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

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

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

如果樹的高度為3，可以存放的記錄行數(shù) = 1170 * 1170 * 105 = 143,734,500

最后加餐

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

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