腾讯、阿里面试题 了解B+树吗?
騰訊、阿里面試題: 了解B+樹嗎?
由于MySQL的索引結構是B+樹,所以B+樹是大廠的高頻面試題,想理解B+樹,最好先理解B樹,下面詳細介紹B樹、B+樹
B樹
-  B樹的概念B樹又稱為B-樹,是一種平衡多路查找樹,描述B樹,一般需要指定其階數MMM,階數指的是一個節點包含的子節點最大數量。當MMM取2的時候,就是常見的二叉樹 其有如下性質: - 每個節點最多有M?1M-1M?1個關鍵字
- 除根節點外,其余的節點至少有ceil(M/2)?1ceil(M/2)-1ceil(M/2)?1個關鍵字(ceilceilceil向上取整函數)
- 每個結點中的關鍵字都按照從小到大的順序排列,每個關鍵字的左子樹中的所有關鍵字都小于它,而右子樹中的所有關鍵字都大于它
- 所有葉子結點都位于同一層,或者說根結點到每個葉子結點的長度都相同。
 
-  B樹的插入操作如下描述是B樹的插入算法,相對來說比較簡單 
-  找到關鍵字的插入位置,一定是葉節點位置,進行插入操作 
-  插入后,如果當前節點的關鍵字數量小于等于M?1M-1M?1,則結束,否則執行步驟3 
-  進行分裂操作,當前節點按中間關鍵字分裂成三部分,中間關鍵字插入到父節點中, 
-  B樹的構建過程下面以構建一個5階樹,介紹B樹的構建過程。 -  依次插入關鍵字3,5, 2, 6 
-  插入4的時候,由于當前節點關鍵字數量等于M(5),需要進行分裂操作 
-  依次插入關鍵字1,8,7,9插入9的時候又進行了分裂 
-  依次插入關鍵字10,11,12插入12的時候又進行了分裂過程 
-  插入關鍵字13,14,15,16,17,中間插入15的時候進行了分裂操作 
-  最后插入18,進行了兩次分裂操作 其實插入的過程會發現,順序插入空間效率最差,比如[11,12]節點,就插入不了任何元素. 
 
-  
-  B樹的刪除過程B樹的刪除算法較為復雜,下面首先介紹算法,之后結合實例,闡述 
- 查找關鍵字,如果不存在,結束,否則進入步驟2.
- 如果關鍵字處于葉節點,直接刪除。如果關鍵字處于非葉子節點,則用其前繼關鍵字(前繼關鍵字一定位于葉節點)覆蓋要刪除的關鍵字,之后刪除后繼關鍵字,將當前節點指向包含后繼關鍵字的節點。以上兩種情況,均最后轉入步驟3
- 如果當前節點關鍵字數量大于等于ceil(M/2)?1ceil(M/2)-1ceil(M/2)?1,則結束,否則轉入4
- 如果兄弟節點(不論左兄弟,還是右兄弟),關鍵字數量大于ceil(M/2)?1ceil(M/2)-1ceil(M/2)?1,則父節點中對應的關鍵字下移到當前節點,兄弟節點對應的關鍵字上移到父節點,結束。若無兄弟節點關鍵字數量大于ceil(M/2)?1ceil(M/2)-1ceil(M/2)?1,則轉入步驟5
- 合并操作,將父結點中關鍵字下移與當前結點及它的兄弟結點中的官架子合并,形成一個新的結點。原父結點中的key的兩個孩子指針就變成了一個孩子指針,指向這個新結點。當前節點指向父節點,重復2,進行遞歸操作。
-  刪除關鍵字7其前繼關鍵字(類似于平衡二叉樹的前繼節點,其實也可以為后繼節點)為6,覆蓋刪除后,當前節點只有一個關鍵字5,而其左兄弟節點有3個關鍵字節點大于2.所以3上移,4下移到當前節點. 
-  刪除關鍵字18刪除關鍵字18,其實是一個復雜的過程,刪除完之后,沒有兄弟節點關鍵字數量大于2,所以進行合并操作左兄弟節點[14,15],父節點中的16,和當前節點合并成一個新節點[14,15,16,17],合并后父節點由于只剩13,所有又要與其父節點關鍵字,左兄弟節點合并,構造一個新的節點,最后結果如下 
-  B樹的優缺點B樹主要的優點是相對于二叉樹,每個節點包括更多的關鍵字,所以其樹高相對較低,查找效率很高. 
左邊部分,成為中間關鍵字的左節點,右邊部分成為中間關鍵字的右節點,然后
當前節點指向父節點,轉到2,執行遞歸操作。
下面是一個5階B樹的分裂過程,上面圖是分裂前,下面圖是分裂后
下面是一個5階數的刪除過程實例
原B樹如下圖所示
 
B+樹
-  B+樹的概念- B+樹包含兩種節點,一種是非葉子節點(索引節點),一種是葉子節點。
- B+樹與B樹,最大的不同是B+樹的非葉子節點不保存數據,只用于索引,所有數據都保存在葉子節點
- 非葉子節點最多有M?1M-1M?1個關鍵字,階數MMM同時限制了葉子結點最多存儲M?1M-1M?1個記錄。
- 索引節點中的key都按照從小到大的順序排列,對于內部結點中的一個key,左樹中的所有key都小于它,右子樹中的key都大于等于它。葉子結點中的記錄也按照key的大小排列。
- 每個葉子節點都存有相鄰葉子節點的指針,葉子節點本身依關鍵字的大小自小而大順序鏈接(范圍查找特性)
 
-  B+樹插入-  B+樹插入算法
-  通過查找,確定關鍵字的插入位置,插入位置一定位于葉節點,插入后,如果當前 節點關鍵字數量小于等于M?1M-1M?1,算法結束,否則轉入步驟2. 
-  分裂過程,將當前節點,分為左右兩個葉子節點,左葉子節點包含前M/2M/2M/2個記錄, 右葉子節點包含剩余記錄,并且將第M/2+1M/2+1M/2+1個記錄的關鍵字上移到父節點。當前節點指針指向父節點,然后執行步驟3.(父節點一定是索引節點) 
-  如果當前節點的關鍵字數量小于MMM,則插入結束,否則,將當前索引節點以中間關鍵字為中心分裂成兩個索引節點,左索引節點和右索引節點,并將中間關鍵字上移到父節點中。并且其左節點為上面提到的左索引節點,其右節點為右索引節點。將當前節點指針指向父節點,重復步驟3 
 
-  
-  B+樹插入實例如下是一個5階B+數的構造過程 -  依次插入1、5、9、13 
-  插入17的時候,發生分裂過程 
-  依次插入2、3、4,插入4的時候,發生分裂過程 
-  依次插入10,11,插入11的時候,發生分裂過程 
-  插入12,14,插入14的時候,發生分裂過程 
-  插入15,16,插入16的時候,發生兩次分裂過程,依次在葉節點,和索引節點 
 
-  
B+樹刪除
-  B+樹刪除算法
-  找到目標關鍵字所在的葉節點位置,進行刪除,若刪除后,當前節點關鍵字數量大于 等于ceil(M/2)?1ceil(M/2)-1ceil(M/2)?1,結束,否則轉到步驟2 
-  若兄弟節點有富余(大于ceil(M/2)?1ceil(M /2 )-1ceil(M/2)?1),向兄弟借一個記錄,同時用借到的key替換父節點中對應的關鍵字,結束。否則轉到步驟3 
-  若兄弟節點沒有富余,則當前節點和兄弟節點合并成一個新的節點,刪除父節點的關鍵字,新節點指向父節點相應的位置。執行步驟4 
-  若索引節點的關鍵字個數大于等于ceil(M/2)?1ceil(M/2)-1ceil(M/2)?1,則結束,否則執行5 
-  若兄弟結點有富余,父結點key下移,兄弟結點key上移,刪除結束。否則執行第6步 
-  當前結點和兄弟結點及父結點下移key合并成一個新的結點。將當前結點指向父結點,重復第4步 
4,5,6步類似B樹的刪除過程
B+樹刪除算法實例
原來的一個5階樹
-  刪除10左兄弟節點有富余,借一個記錄5,并且替換父節點中的關鍵字 
-  刪除11刪除11這個過程非常復雜,首先沒有兄弟節點有富余,所以當前節點和兄弟節點合,并且刪除掉父節點中對應的關鍵字,也就是13。之后由于父節點只有15一個關鍵字,需要一次索引節點的合并過程 每次刪除的時候,記得更新索引結構,即將索引結構中的要刪除的關鍵字,替換成其后繼節點
B+樹的優點
1、B+樹的層級更少:相較于B樹B+每個非葉子節點存儲的關鍵字數更多,樹的層級更少所以查詢數據更快;
2、B+樹查詢速度更穩定:B+所有關鍵字數據地址都存在葉子節點上,所以每次查找的次數都相同所以查詢速度要比B樹更穩定;
3、B+樹天然具備排序功能:B+樹所有的葉子節點數據構成了一個有序鏈表,在查詢大小區間的數據時候更方便,數據緊密性很高,緩存的命中率也會比B樹高。
4、B+樹全節點遍歷更快:B+樹遍歷整棵樹只需要遍歷所有的葉子節點即可,,而不需要像B樹一樣需要對每一層進行遍歷,這有利于數據庫做全表掃描。
B樹相對于B+樹的優點是,如果經常訪問的數據離根節點很近,而B樹的非葉子節點本身存有關鍵字其數據的地址,所以這種數據檢索的時候會要比B+樹快。
參考文章
B樹和B+樹的插入、刪除圖文詳解
 平衡二叉樹、B樹、B+樹、B*樹 理解其中一種你就都明白了
總結
以上是生活随笔為你收集整理的腾讯、阿里面试题 了解B+树吗?的全部內容,希望文章能夠幫你解決所遇到的問題。
 
                            
                        - 上一篇: C#实现IVR(基于东进的语音卡)-3
- 下一篇: G711 G723 G729 等语音编码
