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

更新時(shí)間：2022年05月31日 09:46:21 作者：把蘋果咬哭的測試筆記

這篇文章主要為大家介紹了Mysql?InnoDB?B+樹索引目錄項(xiàng)記錄頁管理，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

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

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

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

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

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

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

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

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

如此一來，目錄頁跟數(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)記錄頁也變多后

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

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

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

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

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

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

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

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

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

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

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

三、B+ 樹

按照上面的套路，其實(shí)可以簡化這個(gè)目錄結(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í)際上一個(gè)頁存放的記錄數(shù)量是非常大的。

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

如果 B+樹只有 1 層，也就是說只有 1 個(gè)用于存放用戶記錄的節(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 個(gè)頁面內(nèi)的查找(3個(gè)存儲目錄項(xiàng)的頁，1個(gè)存儲用戶記錄的頁)。而在每個(gè)頁面內(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)文章！

您可能感興趣的文章: