一、根頁面萬年不動

在之前的文章里，為了方便理解，都是先畫存儲用戶記錄的葉子節(jié)點(diǎn)，然后再畫出存儲目錄項記錄的內(nèi)節(jié)點(diǎn)。

但實際上 B+ 樹的行成過程是這樣的：

• 每當(dāng)為某個表創(chuàng)建一個 B+ 樹索引，都會為這個索引創(chuàng)建一個根節(jié)點(diǎn)頁面。最開始表里沒數(shù)據(jù)，所以根節(jié)點(diǎn)中既沒有用戶記錄，也沒有目錄項記錄。
• 當(dāng)往表里插入用戶記錄時，先把用戶記錄存儲到這個根節(jié)點(diǎn)上。
• 當(dāng)根節(jié)點(diǎn)頁空間用完，繼續(xù)插入記錄，此時會將根節(jié)點(diǎn)中所有記錄復(fù)制到一個新頁(比如頁 a)，然后對這個新頁進(jìn)行頁分裂，得到另一個新頁(頁 b)。這時候新插入的記錄就根據(jù)鍵值大小分配到頁 a 和 頁 b 中。于是，根節(jié)點(diǎn)頁就升級成了存儲目錄項記錄的頁，就需要把頁a 和 頁b 對應(yīng)的目錄項記錄插入到根節(jié)點(diǎn)中。

另外，當(dāng)一個B+樹索引的根節(jié)點(diǎn)創(chuàng)建后，它的頁號就不會再變。

所以只要我們對某個表建立一個索引，那么它的根節(jié)點(diǎn)的頁號就會被記錄到某個地方，后續(xù)只要 innodb引擎需要用這個索引，就會從那個固定的地方取出根節(jié)點(diǎn)的頁號，從而訪問這個索引。

二、內(nèi)節(jié)點(diǎn)中目錄項記錄的唯一性

在B+樹索引的內(nèi)節(jié)點(diǎn)中，目錄項記錄的內(nèi)容是索引列+頁號。但是對于二級索引來說，不太嚴(yán)謹(jǐn)。

因為二級索引的索引列可能存在相同的值，比如某張表里有這4條記錄，其中c1列是主鍵 ：

現(xiàn)在為c2列建立索引：

如果這時候繼續(xù)插入一條記錄，3個列分別為9、1、'c'，就會遇到問題：

新記錄中 c2的值也是1，那么這個新記錄到底應(yīng)該放在頁 4，還是放到頁 5？

所以，為了能讓新插入的記錄可以找到自己應(yīng)該到哪個頁中，就需要保證B+樹同一層內(nèi)節(jié)點(diǎn)的目錄項記錄是唯一的。

那么，實際上二級索引的內(nèi)節(jié)點(diǎn)的目錄項記錄應(yīng)該由 3 個部分組成：

• 索引列的值
• 主鍵值
• 頁號

所以實際上給c2建立的索引應(yīng)該是這樣：

現(xiàn)在，當(dāng)插入新記錄9、1、'c'時：

• 可以先把新記錄的 c2 列的值和頁 3 中各目錄項記錄的 c2 列的值進(jìn)行比較。
• 如果 c2 列的值相同，就接著比較主鍵值。

所以，對于二級索引來說，給 c2 列建索引，其實就相當(dāng)于用c2、c1建立了一個聯(lián)合索引。先按照二級索引的值進(jìn)行排序，在二級索引列值相同的情況下，再按照主鍵值進(jìn)行排序。

三、一個頁面至少容納 2 條記錄

在之前的文章里提到過，B+ 樹其實只需要很少的層級就可以輕松存儲數(shù)億條記錄，查詢速度還很快。

這是因為 B+ 樹本質(zhì)上就是一個大的多層級目錄。每經(jīng)過一個目錄時都會過濾許多無效的子目錄，直到最后訪問到存儲真正數(shù)據(jù)的目錄。

那么現(xiàn)在不妨設(shè)想一下：還是同樣的數(shù)據(jù)量，如果一個大的目錄只存放一個子目錄，又是什么樣子？

• 目錄層級非常多
• 最后那個存放真正數(shù)據(jù)的目錄中只能存放一條記錄

如果是這樣的話，這種B+ 樹結(jié)構(gòu)就沒什么意義了，不能形成一個有效的索引。

于是，設(shè)計 innoDB的大佬為了避免 B+樹的層級增長得過高，要求所有數(shù)據(jù)頁都至少可以存放2條記錄。

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

以上就是Mysql InnoDB中B+樹索引的注意事項的詳細(xì)內(nèi)容，更多關(guān)于Mysql InnoDB中B+樹索引的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論