為什么MySQL索引要用B+樹，而不是B樹？

作者：李平 2019-09-24 09:33:53

數據庫 MySQL

一個面試題：InnoDB 一棵 B+ 樹可以存放多少行數據?這個問題的簡單回答是：約 2 千萬。

[[277685]]
圖片來自 Pexels

為什么是這么多呢?因為這是可以算出來的，要搞清楚這個問題，我們先從 InnoDB 索引數據結構、數據組織方式說起。

我們都知道計算機在存儲數據的時候，有最小存儲單元，這就好比我們今天進行現金的流通最小單位是一毛。

在計算機中磁盤存儲數據最小單元是扇區，一個扇區的大小是 512 字節，而文件系統(例如 XFS/EXT4)他的最小單元是塊，一個塊的大小是 4K。

而對于我們的 InnoDB 存儲引擎也有自己的最小儲存單元——頁(Page)，一個頁的大小是 16K。

下面幾張圖可以幫你理解最小存儲單元，文件系統中一個文件大小只有 1 個字節，但不得不占磁盤上 4KB 的空間。

InnoDB 的所有數據文件(后綴為 ibd 的文件)，他的大小始終都是 16384(16K)的整數倍。

磁盤扇區、文件系統、InnoDB 存儲引擎都有各自的最小存儲單元。

在 MySQL 中我們的 InnoDB 頁的大小默認是 16K，當然也可以通過參數設置：

mysql> show variables like 'innodb_page_size'; 
 
+------------------+-------+ 
 
| Variable_name    | Value | 
 
+------------------+-------+ 
 
| innodb_page_size | 16384 | 
 
+------------------+-------+ 
 
1 row in set (0.00 sec)

數據表中的數據都是存儲在頁中的，所以一個頁中能存儲多少行數據呢?假設一行數據的大小是 1K，那么一個頁可以存放 16 行這樣的數據。

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

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

所以人們想了一個辦法，用 B+ 樹的方式組織這些數據，如下圖所示：

我們先將數據記錄按主鍵進行排序，分別存放在不同的頁中(為了便于理解我們這里一個頁中只存放 3 條記錄，實際情況可以存放很多)。

除了存放數據的頁以外，還有存放鍵值+指針的頁，如圖中 page number=3 的頁，該頁存放鍵值和指向數據頁的指針，這樣的頁由 N 個鍵值+指針組成。

當然它也是排好序的。這樣的數據組織形式，我們稱為索引組織表。

現在來看下，要查找一條數據，怎么查?如：

select * from user where id=5;

這里 id 是主鍵，我們通過這棵 B+ 樹來查找，首先找到根頁，你怎么知道 user 表的根頁在哪呢?

其實每張表的根頁位置在表空間文件中是固定的，即 page number=3 的頁(這點我們下文還會進一步證明)。

找到根頁后通過二分查找法，定位到 id=5 的數據應該在指針 P5 指向的頁中，那么進一步去 page number=5 的頁中查找，同樣通過二分查詢法即可找到 id=5 的記錄：

5    zhao2   27

現在我們清楚了 InnoDB 中主鍵索引 B+ 樹是如何組織數據、查詢數據的，我們總結一下：

InnoDB 存儲引擎的最小存儲單元是頁，頁可以用于存放數據也可以用于存放鍵值+指針，在 B+ 樹中葉子節點存放數據，非葉子節點存放鍵值+指針。
索引組織表通過非葉子節點的二分查找法以及指針確定數據在哪個頁中，進而在去數據頁中查找到需要的數據。

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

這里我們先假設 B+ 樹高為 2，即存在一個根節點和若干個葉子節點，那么這棵 B+ 樹的存放總記錄數為：根節點指針數*單個葉子節點記錄行數。

上文我們已經說明單個葉子節點(頁)中的記錄數=16K/1K=16。(這里假設一行記錄的數據大小為 1K，實際上現在很多互聯網業務數據記錄大小通常就是 1K 左右)。

那么現在我們需要計算出非葉子節點能存放多少指針?其實這也很好算，我們假設主鍵 ID 為 bigint 類型，長度為 8 字節，而指針大小在 InnoDB 源碼中設置為 6 字節，這樣一共 14 字節。

我們一個頁中能存放多少這樣的單元，其實就代表有多少指針，即 16384/14=1170。

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

根據同樣的原理我們可以算出一個高度為 3 的 B+ 樹可以存放：1170*1170*16=21902400 條這樣的記錄。

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

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

怎么得到 InnoDB 主鍵索引 B+ 樹的高度?

上面我們通過推斷得出 B+ 樹的高度通常是 1-3，下面我們從另外一個側面證明這個結論。

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

如果 page level 為 1，樹高為 2，page level 為 2，則樹高為 3。即 B+ 樹的高度=page level+1;下面我們將從實際環境中嘗試找到這個 page level。

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

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;