共計 2223 個字符，預計需要花費 6 分鐘才能閱讀完成。

本篇內容介紹了“如何理解數據庫的 B + 樹”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓丸趣 TV 小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

1 數據從磁盤讀寫與內存讀寫有哪些不同

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

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

磁盤的最小讀寫單位是扇區，現在磁盤扇區一般是 4k 個字節，對于操作系統，一次性會讀取多個扇區，至此操作系統的最小讀取單位就是塊。每當我們從磁盤讀取一個數據，操作系統就會一次性讀取整個塊，那么對于大量的順序讀寫來說，磁盤效率會比隨機讀寫高很多。

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

2 數據和索引分離

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

用戶數據

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

有序數組

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

在這里插入圖片描述

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

2 B+ 樹

讓節點大小等于塊大小

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

內部節點與葉子節點

內部節點和葉子節點雖然是一樣的結構，但是其存儲的內容有所區別。內部節點存放 key 以及維持樹形結構的指針，它并不存放 key 對應的數據。而葉子節點存放 key 和對應的數據，不存放維持樹形結構的指針，這樣使得節點空間的利用最大化。

內部節點與葉子節點

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

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

m 階多叉樹

3 B+ 樹的檢索方案

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

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

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

4 B+ 樹如何進行動態的調整

上面介紹了 B + 樹的結構和查詢原理，現在我們看看 B + 樹增加和刪除是怎么個情況

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

插入元素 6

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

節點分裂

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

節點分裂

“如何理解數據庫的 B + 樹”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注丸趣 TV 網站，丸趣 TV 小編將為大家輸出更多高質量的實用文章！