這篇文章主要介紹了還不理解B樹和B+樹,那就看看這篇文章吧，文中通過示例代碼介紹的非常詳細，對大家的學習或者作業具有一定的參考學習價值
金九銀十近段時間正值找作業的最佳時間，給粉絲們準備了一些大廠面試題想要獲取相關大廠的面試題的可以點擊這里來獲取資料：點擊這里哦！！！，暗號：CSDN
以下是部分資料截圖（所有資料均已整合成檔案，pdf壓縮打包處理），
正文
01 B樹
在介紹B+樹之前， 先簡單的介紹一下B樹，這兩種資料結構既有相似之處，也有他們的區別，最后，我們也會對比一下這兩種資料結構的區別，
1.1 B樹概念
B樹也稱B-樹,它是一顆多路平衡查找樹，二叉樹我想大家都不陌生，其實，B樹和后面講到的B+樹也是從最簡單的二叉樹變換而來的，并沒有什么神秘的地方，下面我們來看看B樹的定義，
?每個節點最多有m-1個關鍵字（可以存有的鍵值對），
?根節點最少可以只有1個關鍵字，
?非根節點至少有m/2個關鍵字，
?每個節點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小于它，而右子樹中的所有關鍵字都大于它，
?所有葉子節點都位于同一層，或者說根節點到每個葉子節點的長度都相同，
?每個節點都存有索引和資料，也就是對應的key和value，
所以，根節點的關鍵字數量范圍：1 <= k <= m-1，非根節點的關鍵字數量范圍：m/2 <= k <= m-1，
另外，我們需要注意一個概念，描述一顆B樹時需要指定它的階數，階數表示了一個節點最多有多少個孩子節點，一般用字母m表示階數，
我們再舉個例子來說明一下上面的概念，比如這里有一個5階的B樹，根節點數量范圍：1 <= k <= 4，非根節點數量范圍：2 <= k <= 4，
下面，我們通過一個插入的例子，講解一下B樹的插入程序，接著，再講解一下洗掉關鍵字的程序，
1.2 B樹插入
插入的時候，我們需要記住一個規則：判斷當前結點key的個數是否小于等于m-1，如果滿足，直接插入即可，如果不滿足，將節點的中間的key將這個節點分為左右兩部分，中間的節點放到父節點中即可，
例子：在5階B樹中，結點最多有4個key,最少有2個key（注意：下面的節點統一用一個節點表示key和value），
插入18，70，50,40
插入22
插入22時，發現這個節點的關鍵字已經大于4了，所以需要進行分裂，分裂的規則在上面已經講了，分裂之后，如下，
接著插入23，25，39
分裂，得到下面的，
更過的插入的程序就不多介紹了，相信有這個例子你已經知道怎么進行插入操作了，
1.3 B樹的洗掉操作
B樹的洗掉操作相對于插入操作是相對復雜一些的，但是，你知道記住幾種情況，一樣可以很輕松的掌握的，
現在有一個初始狀態是下面這樣的B樹，然后進行洗掉操作，
洗掉15，這種情況是洗掉葉子節點的元素，如果洗掉之后，節點數還是大于m/2，這種情況只要直接洗掉即可.
接著，我們把22洗掉，這種情況的規則：22是非葉子節點，對于非葉子節點的洗掉，我們需要用后繼key（元素）覆寫要洗掉的key，然后在后繼key所在的子支中洗掉該后繼key，對于洗掉22，需要將后繼元素24移到被洗掉的22所在的節點，
此時發現26所在的節點只有一個元素，小于2個（m/2），這個節點不符合要求，這時候的規則（向兄弟節點借元素）：如果洗掉葉子節點，如果洗掉元素后元素個數少于（m/2），并且它的兄弟節點的元素大于（m/2），也就是說兄弟節點的元素比最少值m/2還多，將先將父節點的元素移到該節點，然后將兄弟節點的元素再移動到父節點，這樣就滿足要求了，
我們看看操作程序就更加明白了，
接著洗掉28，洗掉葉子節點，洗掉后不滿足要求，所以，我們需要考慮向兄弟節點借元素，但是，兄弟節點也沒有多的節點（2個），借不了，怎么辦呢？如果遇到這種情況，首先，還是將先將父節點的元素移到該節點，然后，將當前節點及它的兄弟節點中的key合并，形成一個新的節點，
移動之后，跟兄弟節點合并，
洗掉就只有上面的幾種情況，根據不同的情況進行洗掉即可，
上面的這些介紹，相信對于B樹已經有一定的了解了，接下來的一部分，我們接著講解B+樹，我相信加上B+樹的對比，就更加清晰明了了，
02 B+樹
2.1 B+樹概述
B+樹其實和B樹是非常相似的，我們首先看看相同點：
?根節點至少一個元素
?非根節點元素范圍：m/2 <= k <= m-1
不同點：
?B+樹有兩種型別的節點：內部結點（也稱索引結點）和葉子結點，內部節點就是非葉子節點，內部節點不存盤資料，只存盤索引，資料都存盤在葉子節點，
?內部結點中的key都按照從小到大的順序排列，對于內部結點中的一個key，左樹中的所有key都小于它，右子樹中的key都大于等于它，葉子結點中的記錄也按照key的大小排列，
?每個葉子結點都存有相鄰葉子結點的指標，葉子結點本身依關鍵字的大小自小而大順序鏈接，
?父節點存有右孩子的第一個元素的索引，
下面我們看一個B+樹的例子，感受感受它吧！
2.2 插入操作
對于插入操作很簡單，只需要記住一個技巧即可：當節點元素數量大于m-1的時候，按中間元素分裂成左右兩部分，中間元素分裂到父節點當做索引存盤，但是，本身中間元素還是分裂右邊這一部分的，
下面以一顆5階B+樹的插入程序為例，5階B+樹的節點最少2個元素，最多4個元素，
插入5，10，15，20
插入25，此時元素數量大于4個了，分裂
接著插入26，30，繼續分裂
有了這幾個例子，相信插入操作沒什么問題了，下面接著看看洗掉操作，
2.3 洗掉操作
對于洗掉操作是比B樹簡單一些的，因為葉子節點有指標的存在，向兄弟節點借元素時，不需要通過父節點了，而是可以直接通過兄弟節移動即可（前提是兄弟節點的元素大于m/2），然后更新父節點的索引；如果兄弟節點的元素不大于m/2（兄弟節點也沒有多余的元素），則將當前節點和兄弟節點合并，并且洗掉父節點中的key，下面我們看看具體的實體，
初始狀態
洗掉10，洗掉后，不滿足要求，發現左邊兄弟節點有多余的元素，所以去借元素，最后，修改父節點索引
洗掉元素5，發現不滿足要求，并且發現左右兄弟節點都沒有多余的元素，所以，可以選擇和兄弟節點合并，最后修改父節點索引
發現父節點索引也不滿足條件，所以，需要做跟上面一步一樣的操作
這樣，B+樹的洗掉操作也就完成了，是不是看完之后，覺得非常簡單！
03 B樹和B+樹總結
B+樹相對于B樹有一些自己的優勢，可以歸結為下面幾點，
?單一節點存盤的元素更多，使得查詢的IO次數更少，所以也就使得它更適合做為資料庫MySQL的底層資料結構了，
?所有的查詢都要查找到葉子節點，查詢性能是穩定的，而B樹，每個節點都可以查找到資料，所以不穩定，
?所有的葉子節點形成了一個有序鏈表，更加便于查找，
到此這篇關于還不理解B樹和B+樹,那就看看這篇文章吧的文章就介紹到這了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/81276.html
標籤：其他