【Mysql】InnoDB 中的 B+ 樹索引

接上一篇內容，InnoDB 的作者想到一種更靈活的方式來管理所有目錄項，是什麼？

一、目錄項記錄頁

其實這些用戶目錄項與用戶記錄很像，只是目錄項中的兩個列記錄的是主鍵和頁號而已，那麼就可以復用之前存儲用戶記錄的數據頁來存儲目錄項。

為了區分用戶記錄和目錄項，仍然使用 record_type 這個屬性，當值為 1 時，表示目錄項記錄，再來複習一遍：

0：普通用戶記錄
1：目錄項記錄
2：Infimum 記錄
3：Supremum 記錄

現在把目錄項放到一個新頁中，就變成了這樣：

目錄項記錄 record_type 值為 1，普通用戶記錄的 record_type 值是 0
目錄項記錄只有主鍵值和頁的編號，兩個列

如此一來，目錄頁跟數據頁一樣，都可以為主鍵值生成 Page Directory（頁目錄），從而在根據主鍵值查找記錄時，使用二分法來加快查詢速度。

還是以查找主鍵值為 20 的記錄為例，大致就可以分為 2 步走：

先目錄項頁（頁30）通過二分法苦熬蘇找到對應的目錄項記錄。因為 12<20<209，所以目標記錄在頁 9。
到頁 9中繼續根據二分法快速找到主鍵為 20 的用戶記錄。

二、當目錄項記錄頁也變多後

一個頁大小是16KB，當數據多的時候，一個頁用來存放頁目錄記錄一定不夠用。解決辦法也很簡單，就是整更多的頁。

基於上圖，假設一個目錄項記錄頁最多只能存放 4 條目錄項記錄（實際可以存很多），現在繼續插入一條主鍵值為 320 的普通用戶記錄，這時候就需要多分配一個新頁。

現在因為存儲目錄項記錄的頁是多個，此時再根據主鍵值查找一條用戶記錄，大致需要 3 個步驟（繼續查找主鍵值為 20 的記錄）：

確定存儲目錄項記錄的頁。上圖中有2個，分別是頁 30 和頁 32。因為頁 30 表示的目錄項主鍵值在 [1, 320），頁 32 的主鍵值則不小於 320，所以主鍵 20的記錄應該在頁30。
通過存儲目錄項記錄的頁確定用戶記錄真正所在的頁（見上文第一部分）
在真正存儲用戶記錄的頁找到主鍵 20 的記錄（見上文第一部分）

ok，解決了問題，又來了新的問題。當數據非常多，上面的2個目錄項記錄頁也不夠，又會有很多，那如何根據主鍵值快速定位一個存儲目錄項記錄的頁？

解決辦法：目錄項記錄頁不是多麼？我再給這些頁建個更高級的目錄不就行了？可以想像一個多級目錄，大目錄里嵌套小目錄，小目錄里才是實際的數據。

基於上圖，又會演變成這樣：

生成了一個更高級的目錄項記錄的頁 33
頁中分別 2 條記錄，代表頁 30 和頁 32
如果用戶記錄的主鍵值在 [1, 320) 之間，則到頁 30中繼續查找
如果用戶記錄的主鍵值不小於 320，則到頁 32 中繼續查找

看出套路來了吧？隨着表中記錄的增加，這個目錄的層級就會繼續增加。

三、B+ 樹

按照上面的套路，其實可以簡化這個目錄結構圖：

其實這就是 B+ 樹。

現在無論是存放用戶記錄的數據頁，還是存放目錄項記錄的數據頁，都存放到 B+ 樹這種數據結構中。

所有的數據頁都成為 B+ 樹的節點。
真正存用戶記錄的數據頁都在 B+樹最底層的節點上，稱為葉子節點或者葉節點。
而存放目錄項記錄的節點稱為非葉子節點或者內節點。
B+ 樹最上面的節點稱為根節點。

那如果說樹的層級深了，找起來不也沒那麼快嗎？

在之前的假設中規定了存放用戶記錄的頁最多3條，存放目錄項記錄的最多4條，而實際上一個頁存放的記錄數量是非常大的。

現在繼續假設，所有存放用戶記錄的葉子節點的數據頁可以存放 100 條用戶記錄，所有存放目錄項記錄的非葉子節點的數據頁可以存放 1000 條目錄項記錄，那麼：

如果 B+樹只有 1 層，也就是說只有 1 個用於存放用戶記錄的節點，那麼只能存 100 條用戶記錄。
如果 B+樹有 2 層，則最多存放 1000*100= 100000 條用戶記錄。
如果 B+樹有 3 層，則最多存放 1000*1000*100= 100000000 條用戶記錄。
如果 B+樹有 4 層，則最多存放 1000*1000*1000*100= 100000000000 條用戶記錄。

也就是說，如果有 4 層的話最多存 1000億條記錄，很顯然表裡不會有這麼多數據。所以在一般情況下，我們用到的 B+樹不超過 4 層。

基於此，通過主鍵值去查詢某條記錄，最多只需要進行 4 個頁面內的查找（3個存儲目錄項的頁，1個存儲用戶記錄的頁）。而在每個頁面內有存在頁目錄 Page Directory，所以在頁面內也可以通過二分法快速定位記錄。

本文參考書籍：
小孩子4919 《mysql是怎樣運行的》

Tags: 把蘋果咬哭的不規律日常數據庫