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