Mysql?InnoDB?B+樹索引目錄項(xiàng)記錄頁管理
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 時，表示目錄項(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ù)主鍵值查找記錄時，使用二分法來加快查詢速度。
還是以查找主鍵值為 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è)一個目錄項(xiàng)記錄頁最多只能存放 4 條目錄項(xiàng)記錄(實(shí)際可以存很多)，現(xiàn)在繼續(xù)插入一條主鍵值為 320 的普通用戶記錄，這時候就需要多分配一個新頁。
現(xiàn)在因?yàn)榇鎯δ夸涰?xiàng)記錄的頁是多個，此時再根據(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)文章！
相關(guān)文章
這篇文章主要為大家介紹了MySQL監(jiān)控Innodb信息工作流程,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-02-02
這篇文章主要介紹了InnoDB解決幻讀的方法詳解的相關(guān)資料,需要的朋友可以參考下2023-04-04
這篇文章主要給大家介紹了關(guān)于MySQL全局鎖和表鎖的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用MySQL具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06
MySQL中g(shù)roup_concat函數(shù)用法小結(jié)
MySQL中g(shù)roup_concat函數(shù)用于將groupby產(chǎn)生的同一個分組中的值連接成一個字符串,支持去重、排序和自定義分隔符,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-11-11
MYSQL中獲取得最后一條記錄的語句，需要的朋友可以參考下。2010-03-03
MySQL中show命令方法得到表列及整個庫的詳細(xì)信息(精品珍藏)
MySQL中show 句法得到表列及整個庫的詳細(xì)信息，方便查看數(shù)據(jù)庫的詳細(xì)信息。2010-11-11
這篇文章主要介紹了MySQL存儲過程參數(shù)的用法及說明，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
這篇文章主要為大家介紹了Mysql數(shù)據(jù)庫分組排名實(shí)現(xiàn)的示例詳解教程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2021-10-10
這篇文章給大家介紹Mysql 8.0.18 hash join測試的相關(guān)知識，本文通過實(shí)例代碼講解，非常不錯，具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2019-10-10
MySQL中的死鎖問題是一個復(fù)雜而微妙的議題,尤其是在高并發(fā)的業(yè)務(wù)環(huán)境中,死鎖可能導(dǎo)致服務(wù)的不穩(wěn)定甚至數(shù)據(jù)的不一致,下面這篇文章主要介紹了該如何處理mysql的死鎖問題的相關(guān)資料,需要的朋友可以參考下2024-10-10