面試官問你B樹和B+樹,就把這篇文章丢給他

170
原文鍊接:面試官問你B樹和B+樹,就把這篇文章丢給他

1 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+樹的對比,就更加清晰明了了。

2 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+樹的删除操作也就完成了,是不是看完之後,覺得非常簡單!

3 B樹和B+樹總結

B+樹相對于B樹有一些自己的優勢,可以歸結為下面幾點。

  • 單一節點存儲的元素更多,使得查詢的IO次數更少,所以也就使得它更适合做為數據庫MySQL的底層數據結構了。
  • 所有的查詢都要查找到葉子節點,查詢性能是穩定的,而B樹,每個節點都可以查找到數據,所以不穩定。
  • 所有的葉子節點形成了一個有序鍊表,更加便于查找。
文章有不當之處,歡迎指正,如果喜歡微信閱讀,你也可以關注我的微信公衆号好好學java,獲取優質學習資源。

如果覺得我的文章對你有用,請随意贊賞

你可能感興趣的

11 條評論
落葉丶零落 · 9月18日

面試官:說一下B樹和B+樹
我:https://segmentfault.com/a/11...
面試官:滾.

+9 回複

0
大_K · 9月18日
0

哈哈哈哈

Aber · 9月18日
0

我就知道有這個

yokaimeow · 9月24日
zhiqiang21 · 9月19日

用什麼畫的圖啊

回複

0

@zhiqiang21 Processon

歐陽思海 作者 · 9月20日
Salamander · 9月20日

圖文形象

回複

月がきれい · 9月20日

m 是什麼?

回複

0

看到了m是階數

月がきれい · 9月20日
Twilight · 9月27日

假如m=6,B+樹節點最多5個
先插入 5 10 15 20 25,在插入30時分裂,這時哪個作為父節點呢?

回複

載入中...