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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通過(guò)存儲(chǔ)目錄項(xiàng)記錄的頁(yè)確定用戶記錄真正所在的頁(yè)(見(jiàn)上文第一部分)

在真正存儲(chǔ)用戶記錄的頁(yè)找到主鍵 20 的記錄(見(jiàn)上文第一部分)

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

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

基于上圖，又會(huì)演變成這樣：

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

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

三、B+ 樹(shù)

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

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

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

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

那如果說(shuō)樹(shù)的層級(jí)深了，找起來(lái)不也沒(méi)那么快嗎？

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

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

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

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

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

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

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