大家好，這裡是IT技術百貨，專注於有價值的IT技術知識分享；
今天跟大家分享數據庫中的關鍵數據結構，B樹與B+樹
什麼是B樹
B樹是一個滿足以下條件的多叉樹，一棵m階B樹滿足如下條件：
- 每一個節點最多有m個子節點
- 除去葉子節點和根結點之外，其他節點至少有m/2個節點
- 包含t個子節點的節點包含有t-1個key
- 根結點如果不是葉子節點，那麼至少要包含2個子結點
- 每個節點的關鍵字從小到大排列，每一個關鍵字對應的左子樹都小於這個關鍵字，右子樹都大於這個關鍵字
- 所有葉子節點都位於同一層
以上限定規則略顯複雜，讀起來可能也比較繞口，簡言之就是限制每個節點的子結點個數，保證有序性以及每一個葉節點深度相同的三個特性；
B樹是一種有序的數據結構，可以在log時間複雜度下完成插入、查找、刪除操作；
插入操作：
自底部插入，如果滿足節點個數的限制，則直接插入；如果不滿足，那麼一定是超出了節點個數限制，則進行調整；
調整的方式是將中間的元素插入到父節點，本身的節點分裂成兩個節點（如果父節點個數也超出了繼續按照這個規則調整）；
舉例：如下圖，插入“39”這個節點，那麼第二層最左邊的節點個數超出了，因此將中間的節點升為父節點，本身分裂為兩個節點，最終變為第二個圖的樣子。
插入1
插入之後
刪除操作
刪除操作略微複雜，但不同情形下都是有成熟的規則的，只要按照規則來就可以；（類似於擰魔方）
- 刪除葉節點，並且刪除之後 節點的key的個數滿足多叉樹要求，那麼直接刪除
case 1
- 刪除葉節點，並且刪除後不滿足要求，則首先看前面的兄弟節點是否有>m/2個節點，如果>m/2個節點，那麼就“借”一個，但這裡並不是直接去借兄弟節點元素，是借父親的元素，然後用兄弟節點元素來填補借的父元素。
刪除元素22
- 如果刪除之後，兄弟節點個數不大於m/2, 那麼將父親節點移到被刪除元素的節點，然後跟兄弟節點合併；
- 刪除非葉子節點，則用此節點的右子樹第一個節點來填補，同時刪除右子樹的第一個節點
B+樹
B+樹是對B樹的升級，主要改動如下：
- 內部節點只存儲索引，不存儲數據；（這裡類比聚簇索引和非聚簇索引就很明確了），對於B樹來說，索引和數據會放在磁盤的同一個扇區中（或者是文件系統的同一個頁中），而B+樹不會；
存儲劃分
page=3的頁中只存在索引，而數據存在其他頁中；
- 每一個葉子節點，都存有相鄰葉節點的指針（雙向鏈表）
採用雙向鏈表的原因是為了方便處理"小於"的條件查詢。
對比
B樹和B+樹都是多路查找樹，目的都是為了解決多次訪問磁盤，IO耗時太長的問題；
如果採用二叉樹，雖然查找的時間複雜度沒變，但是由於每一個節點可能在不同的頁上，因此訪問磁盤的次數增多。
B+樹進一步優化了磁盤訪問次數，將索引和數據分開存儲，因此每一個頁中存儲的索引更多。
B+樹的葉節點增加了指針鏈接，可以查詢效率更高；
但同樣的，B+樹對查詢的優化操作會降低了一定寫入性能。
感謝瀏覽閱讀，如果覺得內容有價值歡迎點贊，轉發；喜歡請關注“IT技術百貨”
分享到:
