資料結構 —— B樹和B+樹

前面一章總結了一下資料結構以及查找樹和紅黑樹的一些知識點，現在接着上面的内容說一下我們常用的B樹和B+樹。

是以要想更加容易讀懂這篇文章，必須要先點這裡看看我們的上一章

先加個目錄：

目錄

1、B樹

1.1 何謂B樹？

1.2 B樹的結構是什麼？

1.3 B樹有什麼優缺點？

1.4 B樹的應用

2 B+樹

2.1 什麼是B+樹？

2.2 B+樹的優缺點？

2.3 B+樹的應用

1、B樹

靈魂三問：何謂B樹？B樹的結構是什麼？B樹有什麼優缺點？

這裡是一個大佬的漫畫講解，很到位

1.1 何謂B樹？

注意注意注意：B-樹就是B樹，不是B減樹

B樹就是一個有2-3樹（檢視上一章内容）的所有結構和原理的多階查找樹，又叫多路平衡查找樹。定義一棵B樹必須指定它的階。

那麼問題來了，什麼是多階查找樹呢？階是什麼呢？

簡單來說呢，一棵樹中的每個節點可以擁有的最多子節點樹就叫做 -- 階。比如2-3樹就是一個階數為3的B樹。

1.2 B樹的結構是什麼？

上一小節中我們已經說過了，2-3樹就是一個階數為3的B樹，這麼說，B樹的結構就類似于2-3樹喽。為什麼說是類似呢？因為這裡還有階一說。那麼如果階數為4，為5的B樹長什麼樣子呢？

其實就是每個節點最多能連接配接的子節點不一樣而已，其他完全一樣，包括保持平衡的邏輯。

這裡是詳細邏輯結構的 傳送門 。就不仔細說了。

知道了結構我們就可以知道它的一些特性了。Look（假設這裡的B樹的階為 m）：

• 一棵B樹的階是預定義的（因為資料儲存在磁盤中，通過磁盤頁的大小決定階的大小）
• 一棵B樹的葉子節點總在同一層（因為它是平衡的，B樹使用節點上移保證平衡）
• 一棵B樹的所有節點上的資料個數等于其子節點個數減一（檢視2-3樹結構圖）
• 一棵B樹的所有中間節點的子節點個數k為: m/2 <= k <= m（因為資料插入隻會發生在葉子節點，需要做平衡化的時候提取中間資料到上層，是以k>=m/2。具體根據結構了解）
• 一棵B樹中的所有節點中的每個資料的左子樹的所有資料小于等于該資料，右子樹的所有資料大于等于該資料（資料有序便于二分查找）

1.3 B樹有什麼優缺點？

我們使用任何東西肯定是無利不起早，沒有好處我們怎麼會用，怎麼會發明出來呢？說起B樹的好處，往下看：

• 和二叉樹相比較，因為我們的資料都是儲存在磁盤中，我們讀取的時候是需要消耗IO，而樹的讀取，我們一層需要讀取一次IO。是以二叉樹過于消耗我們的IO。而B樹相對就會節省我們的IO。其實就是把“瘦高”的二叉樹變成“矮胖”的B樹。

當然任何東西都有兩面性，B樹也有：

• 和二叉樹比較，我們每次操作一個節點的時候就需要去操作節點中的所有資料，相對于二叉樹性能肯定有所不如。

總的來說，相比于這個缺點，記憶體要比磁盤快的多，是以對于消耗的一點記憶體互動來說，省下來的IO大大提高了樹的性能。

1.4 B樹的應用

• 檔案系統
• 資料庫索引，比如現在流行的非關系型資料MongoDB

2 B+樹

既然說了B樹，那麼B+樹也就不得不提了

同樣，還是上面那位大佬，講的很到位

那麼，B+樹為什麼叫B+樹呢？它與B樹有什麼不同呢？

2.1 什麼是B+樹？

B+樹其實就是B樹的一個更新版。相對于B樹，B+樹做了以下修改，大大提升了索引效率：

• 子節點儲存父節點的值，父節點的值作為子節點的最大值或者最小值；
• 所有葉子節點包含了整棵樹的所有值，并且它們之間使用指針相連，形成了一個有序清單；
• 隻有葉子節點儲存資料，其他節點都隻儲存索引（指針）。

是以B+樹的結構是這個樣子的：

2.2 B+樹的優缺點？

B樹的所有優點B+樹全部都有。而且相對于B樹還有一些新增的優點：

• 不儲存資料在根節點和中間節點，是以可以儲存更多的索引，進而支援樹的階數更大，進而比B樹更加矮胖，可以省下更多的IO。
• 每次查詢都必須從根節點周遊到葉子節點，查詢性能相較于B樹穩定（B樹最優直接查詢根節點，最差查詢到子節點。）
• 範圍查詢直接周遊葉子節點就OK，B樹需要周遊N次（N為滿足條件資料量）

2.3 B+樹的應用

• 資料庫索引：典型的就是Mysql資料庫。

暫時做一個總結，文章接着前面一章。覺得有疑問或者不正确的地方的，歡迎指正，一起學習，一起進步。有需要這些流程圖資料的可以留言。