快捷導(dǎo)航

一看就懂的MySQL的聚簇索引及聚簇索引是如何長(zhǎng)高的

更新時(shí)間：2021年05月25日 14:32:43 作者：返回主頁(yè)賜我白日夢(mèng)

聚簇索引不是一種單獨(dú)的索引類型，而是一種數(shù)據(jù)存儲(chǔ)方式。innodb的聚簇索引實(shí)際上在同一個(gè)結(jié)構(gòu)中保存了B-tree索引和數(shù)據(jù)行。通過(guò)本文學(xué)習(xí)MySQL的聚簇索引及聚簇索引是如何長(zhǎng)高的，感興趣的朋友一起學(xué)習(xí)下吧

這一篇筆記我們簡(jiǎn)述一下

MySQL的B+Tree索引到底是咋回事？
聚簇索引索引到底是如何長(zhǎng)高的。

一點(diǎn)一點(diǎn)看，其實(shí)蠻好理解的。

如果你看過(guò)了我之前的筆記，你肯定知道了MySQL進(jìn)行CRUD是在內(nèi)存中進(jìn)行的，也就是在Buffer Pool中。然后你也知道了當(dāng)內(nèi)存中沒(méi)有MySQL需要的數(shù)據(jù)時(shí)，MySQL會(huì)從Disk中通過(guò)IO操作將數(shù)據(jù)讀入內(nèi)存中。讀取的單位呢就是：數(shù)據(jù)頁(yè)

一般數(shù)據(jù)頁(yè)長(zhǎng)下面這樣

沒(méi)錯(cuò)，數(shù)據(jù)頁(yè)中存儲(chǔ)著真實(shí)的數(shù)據(jù)，而且數(shù)據(jù)頁(yè)在內(nèi)存中是以雙向聯(lián)表的方式組織起來(lái)的！如下圖

而在B+Tree的設(shè)定中，它要求主鍵索引時(shí)遞增的，也就是說(shuō)如果主鍵索引時(shí)遞增的話，那么就要求右側(cè)的數(shù)據(jù)頁(yè)中的所有數(shù)據(jù)均比左側(cè)數(shù)據(jù)頁(yè)中的數(shù)據(jù)大。但是很明顯上圖并不符合，因此需要通過(guò)頁(yè)分裂來(lái)調(diào)整成下面這樣。

好，現(xiàn)在你回想一下，之前你肯定有聽(tīng)說(shuō)過(guò)：MySQL的B+Tree聚簇索引，只有葉子節(jié)點(diǎn)才存儲(chǔ)真實(shí)的數(shù)據(jù)，而非葉子節(jié)點(diǎn)中存儲(chǔ)的是索引數(shù)據(jù)，而且葉子節(jié)點(diǎn)之間是通過(guò)雙向鏈表連接起來(lái)

沒(méi)錯(cuò)，那所有的B+Tree的葉子節(jié)點(diǎn)就是上圖中的數(shù)據(jù)頁(yè)，并且它們確實(shí)是通過(guò)雙向鏈表關(guān)聯(lián)起來(lái)的！

我們接著往下看，如果只看上圖由數(shù)據(jù)頁(yè)連接起來(lái)的雙向鏈表的話，這時(shí)如果我們檢索id=7的數(shù)據(jù)行，那會(huì)發(fā)生什么？

很明顯我們要從頭開(kāi)始掃描！

那你可能會(huì)問(wèn)：方才不是說(shuō)B+Tree要求主鍵是遞增的嘛？并且有頁(yè)分裂機(jī)制保證右邊的數(shù)據(jù)頁(yè)中的所有數(shù)據(jù)均比它左邊的數(shù)據(jù)頁(yè)的索引值大。那進(jìn)行二分查找不行嘛？

答：是的，確實(shí)可以在單個(gè)數(shù)據(jù)頁(yè)中進(jìn)行二分查找，但是數(shù)據(jù)頁(yè)之間的組織關(guān)系是鏈表呀，所以從頭開(kāi)始遍歷是避免不了的。

那MySQL怎么辦的呢？

如下圖：MySQL針對(duì)諸多的數(shù)據(jù)頁(yè)抽象出了一個(gè)索引目錄

那有了這個(gè)索引目錄我們?cè)僭谥T多的數(shù)據(jù)頁(yè)中檢索時(shí)看起來(lái)就容易多了！直接就擁有了二分檢索的能力！

而且這個(gè)所以目錄其實(shí)也是存在于數(shù)據(jù)頁(yè)中的，不同于葉子節(jié)點(diǎn)的是，它里面知識(shí)存儲(chǔ)了索引信息，而葉子節(jié)點(diǎn)中存儲(chǔ)的是真實(shí)數(shù)據(jù)？

而索引頁(yè)的誕生也就意味著B(niǎo)+Tree的雛形已經(jīng)誕生了！

隨著用戶不斷的select，buffer pool中的數(shù)據(jù)頁(yè)的越來(lái)越多，那么索引頁(yè)中的數(shù)據(jù)也會(huì)水漲船高。當(dāng)現(xiàn)有的索引體量超過(guò)16KB（一個(gè)數(shù)據(jù)頁(yè)的容量）時(shí)就不得不搞一個(gè)新的索引頁(yè)來(lái)存儲(chǔ)新的索引信息。這時(shí)這顆B+Tree就會(huì)慢慢變得越來(lái)越胖。

那你也知道B+Tree是B樹(shù)的變種，而B(niǎo)樹(shù)其實(shí)可以是2-3樹(shù)、2-3-4數(shù)....等等M階樹(shù)的泛稱，當(dāng)每個(gè)節(jié)點(diǎn)中能存儲(chǔ)的元素達(dá)到上限后，樹(shù)就會(huì)長(zhǎng)高（上一篇文章有講過(guò)）。

就像下圖這樣：