Mysql InnoDB B+樹索引目錄項(xiàng)記錄管理

接上一篇內(nèi)容，InnoDB 的作者想到一種更靈活的方式來管理所有目錄項(xiàng)，是什么？

一、目錄項(xiàng)記錄頁

其實(shí)這些用戶目錄項(xiàng)與用戶記錄很像，只是目錄項(xiàng)中的兩個列記錄的是主鍵和頁號而已，那么就可以復(fù)用之前存儲用戶記錄的數(shù)據(jù)頁來存儲目錄項(xiàng)。

為了區(qū)分用戶記錄和目錄項(xiàng)，仍然使用 record_type 這個屬性，當(dāng)值為 1 時(shí)，表示目錄項(xiàng)記錄，再來復(fù)習(xí)一遍：

• 0：普通用戶記錄
• 1：目錄項(xiàng)記錄
• 2：Infimum 記錄
• 3：Supremum 記錄

現(xiàn)在把目錄項(xiàng)放到一個新頁中，就變成了這樣：

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

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

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

• 先目錄項(xiàng)頁(頁30)通過二分法快速找到對應(yīng)的目錄項(xiàng)記錄。因?yàn)?12<20<209，所以目標(biāo)記錄在頁 9。
• 到頁 9中繼續(xù)根據(jù)二分法快速找到主鍵為 20 的用戶記錄。

二、當(dāng)目錄項(xiàng)記錄頁也變多后

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

基于上圖，假設(shè)一個目錄項(xiàng)記錄頁最多只能存放 4 條目錄項(xiàng)記錄(實(shí)際可以存很多)，現(xiàn)在繼續(xù)插入一條主鍵值為 320 的普通用戶記錄，這時(shí)候就需要多分配一個新頁。

現(xiàn)在因?yàn)榇鎯δ夸涰?xiàng)記錄的頁是多個，此時(shí)再根據(jù)主鍵值查找一條用戶記錄，大致需要 3 個步驟(繼續(xù)查找主鍵值為 20 的記錄)：

確定存儲目錄項(xiàng)記錄的頁。上圖中有2個，分別是頁 30 和頁 32。因?yàn)轫?30 表示的目錄項(xiàng)主鍵值在 [1, 320)，頁 32 的主鍵值則不小于 320，所以主鍵 20的記錄應(yīng)該在 頁30。

通過存儲目錄項(xiàng)記錄的頁確定用戶記錄真正所在的頁(見上文第一部分)

在真正存儲用戶記錄的頁找到主鍵 20 的記錄(見上文第一部分)

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

解決辦法：目錄項(xiàng)記錄頁不是多么？我再給這些頁建個更高級的目錄不就行了？可以想象一個多級目錄，大目錄里嵌套小目錄，小目錄里才是實(shí)際的數(shù)據(jù)。

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

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

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

三、B+ 樹

按照上面的套路，其實(shí)可以簡化這個目錄結(jié)構(gòu)圖：

其實(shí)這就是 B+ 樹。

現(xiàn)在無論是存放用戶記錄的數(shù)據(jù)頁，還是存放目錄項(xiàng)記錄的數(shù)據(jù)頁，都存放到 B+ 樹這種數(shù)據(jù)結(jié)構(gòu)中。

• 所有的數(shù)據(jù)頁都成為 B+ 樹的節(jié)點(diǎn)。
• 真正存用戶記錄的數(shù)據(jù)頁都在 B+樹最底層的節(jié)點(diǎn)上，稱為葉子節(jié)點(diǎn)或者葉節(jié)點(diǎn)。
• 而存放目錄項(xiàng)記錄的節(jié)點(diǎn)稱為非葉子節(jié)點(diǎn)或者內(nèi)節(jié)點(diǎn)。
• B+ 樹最上面的節(jié)點(diǎn)稱為根節(jié)點(diǎn)。

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

在之前的假設(shè)中規(guī)定了存放用戶記錄的頁最多3條，存放目錄項(xiàng)記錄的最多4條，而實(shí)際上一個頁存放的記錄數(shù)量是非常大的。

現(xiàn)在繼續(xù)假設(shè)，所有存放用戶記錄 的葉子節(jié)點(diǎn)的數(shù)據(jù)頁可以存放 100 條用戶記錄，所有存放目錄項(xiàng)記錄的非葉子節(jié)點(diǎn)的數(shù)據(jù)頁可以存放 1000 條目錄項(xiàng)記錄，那么：

• 如果 B+樹只有 1 層，也就是說只有 1 個用于存放用戶記錄的節(jié)點(diǎn)，那么只能存 100 條用戶記錄。
• 如果 B+樹有 2 層，則最多存放 1000*100= 100000 條用戶記錄。
• 如果 B+樹有 3 層，則最多存放 1000*1000*100= 100000000 條用戶記錄。
• 如果 B+樹有 4 層，則最多存放 1000*1000*1000*100= 100000000000 條用戶記錄。

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

基于此，通過主鍵值去查詢某條記錄，最多只需要進(jìn)行 4 個頁面內(nèi)的查找(3個存儲目錄項(xiàng)的頁，1個存儲用戶記錄的頁)。而在每個頁面內(nèi)有存在頁目錄 Page Directory，所以在頁面內(nèi)也可以通過二分法快速定位記錄。

本文參考書籍： 《mysql是怎樣運(yùn)行的》

以上就是Mysql InnoDB B+樹索引目錄項(xiàng)記錄頁管理的詳細(xì)內(nèi)容，更多關(guān)于Mysql InnoDB B+樹索引目錄記錄的資料請關(guān)注腳本之家其它相關(guān)文章！