每日要聞

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


相關文章

Java 8 新特性-Time Api 使用指南

1.概述Java 8為Date和Time引入了新的API,以解決舊java.util.Date和ja

JAVA 中獲取BigInteger 類型獲取最多1位最小數

最近根據工作中需要股東持股數據繪制圖表,但是根據客戶持股數量有大有小,Y軸數據不能寫死,否則有些數據的圖表不能夠正常繪制出來。圖表使用的Echarts

Java 線程的 5 個使用技巧

點擊上方 "程序員小樂"關注, 星標或置頂一起成長 第一時間與你相約 每日英文 Never expe

Java 里的 for (;;) 與 while (true),哪個更快?

在JDK8u的jdk項目下做個很粗略的搜索:沒有差多少。其次,for

Java、Python、C++、PHP、JavaScript5編程語言,我該如何選擇?

簡介:很多朋友在後台給我留言,問:現在這么多變成語言,Python、Java、PHP、C++、JavaScript等,究竟哪種最流行?我想這應該也是你的困擾吧!其實他們各有優勢,但是對於選擇困難的程序員而言,這真的是個世紀難題。

java之父推薦19980元編程Java課程資料下載,僅此1次,免費領取

最近很多程序員朋友反映進入了晉升瓶頸期,其實是他們沒有搞對方向。想要進軍BAT大廠,JAVA語言是必須要掌握的。獵聘大數據表明,無論企業還是個人,都采取積極的行動應對,尋找人才,尋找路徑,尋找新的可能和機遇。

Java入門:常量變量和數據類型的全部基礎知識點

一、常量先介紹一下常量,也就是概述:指的就是在Java程序員里面固定的數據,這個數據是不會變的。我整理出來了各種常量的分類,大家可以拿起小本本記住!有關常量的基礎知識點很少,重點要記憶的就是類型含義和上圖當中的數據舉例。

JAVA堆大小不要超過32GB

文章來源:https://dwz.cn/7YcSeVQk作者:占小狼看ES官方文檔時,提到的一個觀點:Don’t

Java實現爬蟲技術Jsoup實例講解

Jsoup介紹Jsoup是一款Java 的HTML解析器,可直接解析某個URL地址、HTML文本內容

java開發,入職半年。對未來迷茫,如何發展?

蠻多人私密我一些問題,關於面試,關於技術的,我只能說有些路只能靠自己去走,沒人可以幫到自己,哪怕偶爾幫一到兩次,但是技術的路這么長,總歸需要自己獨自成長的。附一張自己藏書的照片,與各位共勉工作三年多,就個人方面而言,很多的工作都是面試造核彈,工作擰螺絲。

第七屆開源操作系統年度技術會議(OS2ATC)盛大開幕,從編譯器到軟件定義衛星精彩議題大曝光

12 月 14 日,由深圳鵬城實驗室主辦,CSDN、鑒釋科技、飛漫軟件、清華大學、CCF 系統軟件專

賈躍亭的破產人生:租2億豪宅、月均花50多萬、雇人洗衣做清潔

文 ✎ 張洋編輯 ✎ 邢昀北京世茂工三的地下停車場,停放着賈躍亭的夢想。 7輛「 ”LE”logo的汽車

Copyright 每日要聞 © 2019