每日要聞

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

1 B樹在介紹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
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 插入22
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

插入22時,發現這個節點的關鍵字已經大於4了,所以需要進行分裂,分裂的規則在上面已經講了,分裂之後,如下。

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 接著插入23,25,39
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

分裂,得到下面的。

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

更過的插入的過程就不多介紹了,相信有這個例子你已經知道怎麼進行插入操作了。

1.3 B樹的刪除操作

B樹的刪除操作相對於插入操作是相對複雜一些的,但是,你知道記住幾種情況,一樣可以很輕鬆的掌握的。

  • 現在有一個初始狀態是下面這樣的B樹,然後進行刪除操作。
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 刪除15,這種情況是刪除葉子節點的元素,如果刪除之後,節點數還是大於m/2,這種情況只要直接刪除即可。
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 接著,我們把22刪除,這種情況的規則:22是非葉子節點,對於非葉子節點的刪除,我們需要用後繼key(元素)覆蓋要刪除的key,然後在後繼key所在的子支中刪除該後繼key。對於刪除22,需要將後繼元素24移到被刪除的22所在的節點。
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

此時發現26所在的節點只有一個元素,小於2個(m/2),這個節點不符合要求,這時候的規則(向兄弟節點借元素):如果刪除葉子節點,如果刪除元素後元素個數少於(m/2),並且它的兄弟節點的元素大於(m/2),也就是說兄弟節點的元素比最少值m/2還多,將先將父節點的元素移到該節點,然後將兄弟節點的元素再移動到父節點。這樣就滿足要求了。

我們看看操作過程就更加明白了。

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 接著刪除28,刪除葉子節點,刪除後不滿足要求,所以,我們需要考慮向兄弟節點借元素,但是,兄弟節點也沒有多的節點(2個),借不了,怎麼辦呢?如果遇到這種情況,首先,還是將先將父節點的元素移到該節點,然後,將當前節點及它的兄弟節點中的key合併,形成一個新的節點
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

移動之後,跟兄弟節點合併。

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

刪除就只有上面的幾種情況,根據不同的情況進行刪除即可。

上面的這些介紹,相信對於B樹已經有一定的了解了,接下來的一部分,我們接著講解B+樹,我相信加上B+樹的對比,就更加清晰明了了。

2 B+樹

2.1 B+樹概述

B+樹其實和B樹是非常相似的,我們首先看看相同點

  • 根節點至少一個元素
  • 非根節點元素範圍:m/2 <= k <= m-1

不同點

  • B+樹有兩種類型的節點:內部結點(也稱索引結點)和葉子結點。內部節點就是非葉子節點,內部節點不存儲數據,只存儲索引,數據都存儲在葉子節點。
  • 內部結點中的key都按照從小到大的順序排列,對於內部結點中的一個key,左樹中的所有key都小於它,右子樹中的key都大於等於它。葉子結點中的記錄也按照key的大小排列。
  • 每個葉子結點都存有相鄰葉子結點的指針,葉子結點本身依關鍵字的大小自小而大順序鏈接。
  • 父節點存有右孩子的第一個元素的索引。

下面我們看一個B+樹的例子,感受感受它吧!

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

2.2 插入操作

對於插入操作很簡單,只需要記住一個技巧即可:當節點元素數量大於m-1的時候,按中間元素分裂成左右兩部分,中間元素分裂到父節點當做索引存儲,但是,本身中間元素還是分裂右邊這一部分的

下面以一顆5階B+樹的插入過程為例,5階B+樹的節點最少2個元素,最多4個元素。

  • 插入5,10,15,20
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 插入25,此時元素數量大於4個了,分裂
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 接著插入26,30,繼續分裂
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

有了這幾個例子,相信插入操作沒什麼問題了,下面接著看看刪除操作。

2.3 刪除操作

對於刪除操作是比B樹簡單一些的,因為葉子節點有指針的存在,向兄弟節點借元素時,不需要通過父節點了,而是可以直接通過兄弟節移動即可(前提是兄弟節點的元素大於m/2),然後更新父節點的索引;如果兄弟節點的元素不大於m/2(兄弟節點也沒有多餘的元素),則將當前節點和兄弟節點合併,並且刪除父節點中的key,下面我們看看具體的實例。

  • 初始狀態
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 刪除10,刪除後,不滿足要求,發現左邊兄弟節點有多餘的元素,所以去借元素,最後,修改父節點索引
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 刪除元素5,發現不滿足要求,並且發現左右兄弟節點都沒有多餘的元素,所以,可以選擇和兄弟節點合併,最後修改父節點索引
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

  • 發現父節點索引也不滿足條件,所以,需要做跟上面一步一樣的操作
Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他

這樣,B+樹的刪除操作也就完成了,是不是看完之後,覺得非常簡單!

3 B樹和B+樹總結

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

  • 單一節點存儲的元素更多,使得查詢的IO次數更少,所以也就使得它更適合做為資料庫MySQL的底層數據結構了。
  • 所有的查詢都要查找到葉子節點,查詢性能是穩定的,而B樹,每個節點都可以查找到數據,所以不穩定。
  • 所有的葉子節點形成了一個有序鏈表,更加便於查找。

精彩評論
「Java架構筆記」對文章【Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他】發表了「看了本文你心裡就有b樹了!!!」的評論
Java架構筆記

看了本文你心裡就有b樹了!!!


「愛吃零食的小時同學」對文章【Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他】發表了「我把這篇文章丟給了我的面試官,然後他叫我回去等通知,這都一個月了還沒消息[捂臉]」的評論
愛吃零食的小時同學

我把這篇文章丟給了我的面試官,然後他叫我回去等通知,這都一個月了還沒消息[捂臉]


「神經質上帝」對文章【Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他】發表了「索引結構」的評論
神經質上帝

索引結構


「琅環玉閣」對文章【Java架構師-面試官問你B樹和B+樹,就把這篇文章丟給他】發表了「Nice」的評論
琅環玉閣

Nice


相關文章

中國移動推首款WiFi 6路由器,10秒下載一部電影

中國移動推首款WiFi 6路由器,10秒下載一部電影

日前,中國移動舉辦了全家Wi-Fi專場發布會,正式推出了智能組網2.0,還發布了旗下首款Wi-Fi 6+路由器。
胡錫進的希望破滅,加拿大凌晨對華為下狠手,幫凶自會付出代價

胡錫進的希望破滅,加拿大凌晨對華為下狠手,幫凶自會付出代價

北京時間5月28日凌晨,加拿大對華為再下狠手,華為高管孟晚舟“雙重犯罪”案裁決終於公布了,但結果卻並不符合許多國人心中所
500元起!就昨天,諾基亞又發布了三款“電子垃圾”

500元起!就昨天,諾基亞又發布了三款“電子垃圾”

這幾天的新機可真是數不勝數,不止國內廠商,連國外的手機廠商也開始機海戰術,就昨天,諾基亞又發布了三款新機,以國內的情形來
還是要說再見?華為突然宣布,網友:只是沒想到那麼快

還是要說再見?華為突然宣布,網友:只是沒想到那麼快

眾所周知,這個月華為與美國之間的“鬥爭”就沒有消停過,或者說是美國那邊的動作就沒有停止過,不管是前段時間美國宣布的華為“
華為被欺負的太慘?民間人士看不過去了,紛紛上前應援華為

華為被欺負的太慘?民間人士看不過去了,紛紛上前應援華為

看著華為被美國步步緊逼,不少國人心裡不是滋味,畢竟美國這樣針對華為,是沖著我國科技崛起而來,這對一些愛國人士來說是不可以
專家談孟晚舟判令:沒有事實證據不足,應啟動兩個上訴

專家談孟晚舟判令:沒有事實證據不足,應啟動兩個上訴

對此,南京郵電大學教授、聯合國世界絲路論壇數字經濟研究院院長,中國法學會網路與信息法學研究會常務理事王春暉在接受《通信產
重磅!華為向全球P20 Pro和Mate10手機推送EMUI 10

重磅!華為向全球P20 Pro和Mate10手機推送EMUI 10

據XDA消息,華為終於將期待已久的基於Android 10的EMUI 10更新引入P20 Pro和Mate10,該公司已
大促不降價的蘋果,這次沒逃過京東618的真香定律

大促不降價的蘋果,這次沒逃過京東618的真香定律

除了上述保值換新的喜訊,據了解今年京東618期間還有超值福利,iPhone 11系列低至4599元,同樣十分火爆的iPh
措手不及,特朗普對華為禁令後,最大贏家出現了,並不是高通

措手不及,特朗普對華為禁令後,最大贏家出現了,並不是高通

而這個打壓會讓華為在手機領域中受到很大的波及,同時因為手機營收上的減少,這樣一來,華為在科技上投資的資金也會進一減少,降
蘋果官方將首次參與天貓 618 促銷活動;淘寶回應用戶賬號被禁用980年;Julia 1.5.0 beta1 發布 | 極客頭條

蘋果官方將首次參與天貓 618 促銷活動;淘寶回應用戶賬號被禁用980年;Julia 1.5.0 beta1 發布 | 極客頭條

整理 | 屠敏。頭圖 | CSDN 下載自東方 IC。微軟釋出 Windows 10 May 2020 Update。可

延伸閱讀

實時熱門搜索

  • 1 宋慧喬玄彬
  • 2 李敏鎬 永遠的君主
  • 3 宥勝老婆林宜嫻照片
  • 4 日劇月薪嬌妻線上看
  • 5 機智醫生生活 電視
  • 6 running man 線上看2016
  • 7 蔡尚樺照片
  • 8 吳青峰 太空人
  • 9 雙層公寓 東京 2019
  • 10 陳立農超話微博
  • 11 隋棠老公tony背景
  • 12 夫妻的世界結局
  • Copyright 每日要聞 © 2020
    友情鏈接: 陸劇吧 天天要聞