數(shù)據(jù)結(jié)構(gòu)B樹或者B樹怎么構(gòu)造求告知

發(fā)布時(shí)間：2025-12-05 | 來源：互聯(lián)網(wǎng)轉(zhuǎn)載和整理

一、B樹的起源

B樹，最早是由德國計(jì)算機(jī)科學(xué)家RudolfBayer等人于1972年在論文《OrganizationandMaintenanceofLargeOrderedIndexes》提出的，不過我去看了看原文，發(fā)現(xiàn)作者也沒有解釋為什么就叫B-trees了，所以把B樹的B，簡單地解釋為Balanced或者Binary都不是特別嚴(yán)謹(jǐn)，也許作者就是取其名字Bayer的首字母命名的也說不定啊……

二、B樹長啥樣

還是直接看圖比較清楚，圖中所示，B樹事實(shí)上是一種平衡的多叉查找樹，也就是說最多可以開m個(gè)叉（m>=2），我們稱之為m階b樹，為了體現(xiàn)本博客的良心之處，不同于其他地方都能看到2階B樹，這里特意畫了一棵5階B樹。

總體而言m階B樹滿足以下條件：

每個(gè)節(jié)點(diǎn)至多可以擁有m棵子樹

根節(jié)點(diǎn)只有至少有2個(gè)節(jié)點(diǎn)（要么極端情況，就是一棵樹就一個(gè)根節(jié)點(diǎn)，單細(xì)胞生物，即是根，也是葉，也是樹)

非根非葉的節(jié)點(diǎn)至少有的Ceil(m/2)個(gè)子樹(Ceil表示向上取整，圖中5階B樹，每個(gè)節(jié)點(diǎn)至少有3個(gè)子樹，也就是至少有3個(gè)叉)

非葉節(jié)點(diǎn)中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示該節(jié)點(diǎn)中保存的關(guān)鍵字個(gè)數(shù)，K為關(guān)鍵字且Ki<Ki+1，A為指向子樹根節(jié)點(diǎn)的指針

從根到葉子的每一條路徑都有相同的長度，也就是說，葉子節(jié)在相同的層，并且這些節(jié)點(diǎn)不帶信息，實(shí)際上這些節(jié)點(diǎn)就表示找不到指定的值，也就是指向這些節(jié)點(diǎn)的指針為空

B樹的查詢過程和二叉排序樹比較類似，從根節(jié)點(diǎn)依次比較每個(gè)結(jié)點(diǎn)，因?yàn)槊總€(gè)節(jié)點(diǎn)中的關(guān)鍵字和左右子樹都是有序的，所以只要比較節(jié)點(diǎn)中的關(guān)鍵字，或者沿著指針就能很快地找到指定的關(guān)鍵字，如果查找失敗，則會(huì)返回葉子節(jié)點(diǎn)，即空指針

例如查詢圖中字母表中的K

從根節(jié)點(diǎn)P開始，K的位置在P之前，進(jìn)入左側(cè)指針

左子樹中依次比較C、F、J、M，發(fā)現(xiàn)K在J和M之間

沿著J和M之間的指針，繼續(xù)訪問子樹，并依次進(jìn)行比較，發(fā)現(xiàn)第一個(gè)關(guān)鍵字K即為指定查找的值

三、Plus版——B+樹

作為B樹的加強(qiáng)版，B+樹與B樹的差異在于：

有n棵子樹的節(jié)點(diǎn)含有n個(gè)關(guān)鍵字（也有認(rèn)為是n-1個(gè)關(guān)鍵字）

所有的葉子節(jié)點(diǎn)包含了全部的關(guān)鍵字，及指向含這些關(guān)鍵字記錄的指針，且葉子節(jié)點(diǎn)本身根據(jù)關(guān)鍵字自小而大順序連接

非葉子節(jié)點(diǎn)可以看成索引部分，節(jié)點(diǎn)中僅含有其子樹（根節(jié)點(diǎn)）中的最大（或最?。╆P(guān)鍵字

請(qǐng)點(diǎn)擊輸入圖片描述

B+樹的查找過程，與B樹類似，只不過查找時(shí)，如果在非葉子節(jié)點(diǎn)上的關(guān)鍵字等于給定值，并不終止，而是繼續(xù)沿著指針直到葉子節(jié)點(diǎn)位置。因此在B+樹，不管查找成功與否，每次查找都是走了一條從根到葉子節(jié)點(diǎn)的路徑