如何理解數(shù)據(jù)庫的B+樹

本篇內(nèi)容介紹了“如何理解數(shù)據(jù)庫的B+樹”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

1 數(shù)據(jù)從磁盤讀寫與內(nèi)存讀寫有哪些不同

我們平時接觸的有機械硬盤和固態(tài)硬盤。內(nèi)存屬于半導(dǎo)體器件，對于內(nèi)存，我們知道內(nèi)存地址就可以通過地址拿到數(shù)據(jù)，也就是內(nèi)存的隨機訪問特性。訪問速度快但是貴，所以內(nèi)存空間一般比較小。

對于磁盤，屬于機械器件。每當(dāng)磁盤訪問數(shù)據(jù)的時候，都需要等磁盤盤片旋轉(zhuǎn)到磁頭，才能讀取相應(yīng)的數(shù)據(jù)，即使磁盤的轉(zhuǎn)速很快，但是和內(nèi)存的隨機訪問相比還是渣渣。所見，如果是隨機讀寫，其性能差距是非常大的。那如果是順序訪問大量數(shù)據(jù)的時候，磁盤的性能和內(nèi)存其實差距就不大了，這是為啥?

磁盤的最小讀寫單位是扇區(qū)，現(xiàn)在磁盤扇區(qū)一般是4k個字節(jié)，對于操作系統(tǒng)，一次性會讀取多個扇區(qū)，至此操作系統(tǒng)的最小讀取單位就是塊。每當(dāng)我們從磁盤讀取一個數(shù)據(jù)，操作系統(tǒng)就會一次性讀取整個塊，那么對于大量的順序讀寫來說，磁盤效率會比隨機讀寫高很多。

假設(shè)現(xiàn)在你有個有序數(shù)組，全部以塊的方式存放在磁盤中，現(xiàn)在我們通過二分查找的方式查找元素A。首先我們找到中間元素，并從塊中取出，將其從磁盤放入內(nèi)存中，然后再內(nèi)存中進行二分查找。在進行下一步的時候，如果查找的元素在其他塊中，我們需要繼續(xù)從磁盤讀出到內(nèi)存中。這樣反反復(fù)復(fù)的從磁盤到內(nèi)存，其效率將非常的低。所以我們需要想辦法讓訪問磁盤的次數(shù)盡可能的低。

2 數(shù)據(jù)和索引分離

我們以公安系統(tǒng)為例。系統(tǒng)中的用戶非常多，每個用戶除了姓名，年齡等基本信息外，當(dāng)然還有一個唯一標(biāo)識的ID，我們拿到這個ID，就可以知道對應(yīng)的基本信息。但是每個用戶的基本信息太多不可能全部存放在內(nèi)存中，因此考慮存儲于磁盤中。

用戶數(shù)據(jù)

采用有序數(shù)組的方式，其中分別存儲用戶ID和用戶信息所在磁盤的位置，這樣我只需要存放兩個元素，直接存放于內(nèi)存。如下圖所示

有序數(shù)組

但是在數(shù)據(jù)頻繁變化的場景中，有序數(shù)組的弊端就出現(xiàn)了。大部分情況還是考慮使用二叉檢索樹或者哈希表的方式。但是哈希表又不支持區(qū)間查詢，因此更多的使用二叉檢索樹的方式。如下圖所示

在這里插入圖片描述

如果索引太多，依然不能完全存放于內(nèi)存中，那我們是不是可以考慮將索引也存放于磁盤中?如何高效的在磁盤中組織索引的結(jié)構(gòu)?這就引入了B+樹

2 B+樹

• 讓節(jié)點大小等于塊大小

我們知道操作系統(tǒng)在對磁盤進行訪問的時候，通常是按照塊的方式讀取。如果當(dāng)前你需要讀取的數(shù)據(jù)只有幾個字節(jié)，但是磁盤依然會將整個塊讀出來，這樣子是不是讀寫效率就很低呢。在B+樹中，大佬采用讓一個節(jié)點大小等于一個塊的大小，節(jié)點中存放的不是一個元素，而是一個有序的數(shù)組，這樣充分利用操作系統(tǒng)的套路，使得讀取效率的最大化

• 內(nèi)部節(jié)點與葉子節(jié)點

內(nèi)部節(jié)點和葉子節(jié)點雖然是一樣的結(jié)構(gòu)，但是其存儲的內(nèi)容有所區(qū)別。內(nèi)部節(jié)點存放key以及維持樹形結(jié)構(gòu)的指針，它并不存放key對應(yīng)的數(shù)據(jù)。而葉子節(jié)點存放key和對應(yīng)的數(shù)據(jù)，不存放維持樹形結(jié)構(gòu)的指針，這樣使得節(jié)點空間的利用最大化。

內(nèi)部節(jié)點與葉子節(jié)點

• B+樹使用雙向鏈表的方式，具有良好的范圍查詢能力和靈活的調(diào)整能力

綜上三點，B+樹是一顆完全平衡的m階多叉樹。

m階多叉樹

3 B+樹的檢索方案

剛才吹了一波B+樹多么的牛逼，到底是怎么檢索的?具體的查找過程是這樣的：我們先確認(rèn)要尋找的查詢值，位于數(shù)組中哪兩個相鄰元素中間，然后我們將第一個元素對應(yīng)的指針讀出，獲得下一個  block 的位置。讀出下一個 block 的節(jié)點數(shù)據(jù)后，我們再對它進行同樣處理。這樣，B+  樹會逐層訪問內(nèi)部節(jié)點，直到讀出葉子節(jié)點。對于葉子節(jié)點中的數(shù)組，直接使用二分查找算法，我們就可以判斷查找的元素是否存在。如果存在，我們就可以得到該查詢值對應(yīng)的存儲數(shù)據(jù)。如果這個數(shù)據(jù)是詳細(xì)信息的位置指針，那我們還需要再訪問磁盤一次，將詳細(xì)信息讀出

B+樹是一個m階的多叉樹，所以B+樹中的一個節(jié)點可以存放m個元素的數(shù)組，ok，這樣的話，只需要幾層的b+樹就可以索引數(shù)據(jù)量很大的數(shù)了。比如1個2k的節(jié)點可以存放200個元素，那么一個4層的B+樹就能存放200^4，即16億個元素。

如果只有四層，意味著我們最多訪問磁盤4次，假設(shè)目前每個節(jié)點為2k，那么第一層就一個節(jié)點也就2k，第二層節(jié)點最多200個元素，一共就是0.8M。第三層200^2，也就是40000個節(jié)點，一共80M。對于當(dāng)前的計算機而言，我們完全可以將前面三層存放于內(nèi)存中，只需要將第四層存放于磁盤中，這樣我們只需要和磁盤打一次交道就分手，也就是面試想知道的為什么要分為內(nèi)部節(jié)點與葉子節(jié)點。

4 B+樹如何進行動態(tài)的調(diào)整

上面介紹了B+樹的結(jié)構(gòu)和查詢原理，現(xiàn)在我們看看B+樹增加和刪除是怎么個情況

現(xiàn)在我們以三個元素的B+樹 為例，假設(shè)目前我們要插入ID為6=5的元素，第一步先查找對應(yīng)的葉子節(jié)點，如果葉子節(jié)點沒有滿，直接插入即可

插入元素6

如果我們插入的元素是10?按道理我們應(yīng)該插入到9后面，但是節(jié)點已經(jīng)滿了，所以我們需要采取其他的方式。方法是將此葉子節(jié)點進行分裂，即生成一個新的節(jié)點，然后將數(shù)據(jù)在兩個節(jié)點中平分。

節(jié)點分裂

很明顯，葉子節(jié)點的分裂影響到了父節(jié)點，如果父節(jié)點也是滿的，也要進行分裂

節(jié)點分裂

“如何理解數(shù)據(jù)庫的B+樹”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！