B樹和B樹的區別是什麼,簡述B樹和B樹的區別

2021-03-03 23:12:31 字數 5619 閱讀 8020

1樓:乙熹羿懿

對於一棵m階的b-樹和一棵m階的b+樹,它們的主要差異:

①b-樹的葉子結點不含任何資訊,而b+樹的葉子結點含資訊(關鍵字及其記錄等)。

②b-樹上的葉子結點不會指向它的兄弟結點,而b+樹上的葉子結點會指向它的兄弟結點。

作點解釋:這些葉子結點乙個指向乙個,最終連線成乙個連結串列。

③b-樹只能進行分區間查詢,而b+樹上可以有兩種查詢:順序查詢和分區間查詢。

④b-樹上所有的非葉結點都滿足有n個關鍵字的話有n+1棵子樹,而b+樹上所有的非葉結點含n個關鍵字的話只含n棵子樹。這個不同引起了如下幾點的不同:

(1)b-樹的非葉結點有n+1個查詢區間,而b+樹的卻少了乙個區間,這個區間恰好是最右邊的區間(如果存在,這個區間所指的子樹上的所有關鍵字的值都大於結點的所有關鍵字的值)。

(2)在b-樹上,除根的非葉結點的子樹個數不能少於m/2取上界(這個值用lowbou表示),等價地,關鍵字的個數不能少於lowbou-1,但在b+樹上這個關係發生了變化,除根的其他結點的子樹個數同樣不能少於lowbou,但關鍵字的個數卻不能少於lowbou,而不是lowbou減一,這個會給b+樹的一些演算法的具體實現帶來不同。

(3)由於根結點至少需要兩棵子樹,因而b-樹上的根結點的關鍵字可以只有乙個,但是b+樹不能,它至少要有兩個關鍵字,這樣它才可以有兩棵子樹(至於為什麼根結點都需要兩棵子樹,是因為它們都是平衡的)。

⑤b-樹上每乙個關鍵字都配有記錄,而在b+樹上只有葉子結點上的關鍵字才配有記錄。

作點解釋:在b+樹上,所有關鍵字的記錄(指標)都集中在葉子結點上,其他地方的關鍵字只是充當索引,並沒有與之配有相應的記錄的指標。

⑥b-樹查詢可以停在某個非葉結點上,而b+樹不能停在非葉結點上,它需要一直查詢到葉子結點才能停下,因為b+樹的關鍵字的記錄只在葉子結點上。

作點補充和解釋:在b+樹上只要給定的關鍵字的大小不要比根結點的所有關鍵字都大(這樣就沒查詢的必要了,因為全樹最大的值就在根結點的最右邊),那麼對於這個關鍵字的查詢,最後一定是停在葉子結點上的,無論它是否存在在b+樹上,或者換句話說,無論查詢成功與否。

⑦b-樹上的關鍵字在全樹中出現且僅出現一次,而在b+樹上乙個關鍵字可以出現在多個位置,可以有多個,但只有乙個位置的關鍵字配有記錄。

⑧b+樹非葉結點上最右邊的關鍵字表明了它所有子樹中關鍵字的最大值,而b-樹沒有這規律

b+樹和b-樹最大的差別可以說是⑤,甚至這不僅是和b-樹的差異,和其他一般的bst樹都是這樣,b+樹上非葉結點上的關鍵字只是索引,它沒有記錄,而關鍵字真正的記錄是在葉子結點上。

注意:①b-樹上非葉結點是全部的內部結點,而b+樹上的非葉結點不是全部的內部結點,它除去了最下層的結點。

②lowbou是子樹下界的意思,或者說最小子樹個數。

b-樹和b+樹的區別是什麼?

2樓:景三四

b-樹是一種多路搜尋樹(並不是二叉的。),一顆m階的b-樹,或為空樹,或者定義任意非葉子結點最多只有m個兒子。

且m>2;根結點的兒子數為[2, m]。

除根結點以外的非葉子結點的兒子數為[m/2]。

每個結點存放至少m/2-1(取上整)和至多m-1個關鍵字;(至少2個關鍵字)非葉子結點的關鍵字個數=指向兒子的指標個數-1;

b+樹, b+樹是b-樹的變體,也是一種多路搜尋樹:其定義基本與b-樹同。

b-樹是一種  多路搜尋 樹(並不是二叉的。),一顆   m  階  的b-樹,或為空樹,或  者定 義任意非葉子結點最   多隻   有m  個兒子。

且m>2;根 結  點的兒 子   數   為  [2, m]。

除根結 點以  外的非葉子結點的兒子數為[m/2]。

每個結 點存放至  少m/2-1 (取上整) 和至 多 m- 1 個  關鍵  字;(至少2個關鍵字)非葉子結點的關  鍵 字個數 =指 向兒子  指標個數-1;

b+樹, b+樹是b-樹的變體, 也是一種多路搜尋樹:其定義基本與b-樹同。

簡述b-樹和b+樹的區別

3樓:樂意丶

對於一棵m階的b-樹和一棵m階的b+樹,它們的主要差異:

①b-樹的葉子結點不含任何資訊,而b+樹的葉子結點含資訊(關鍵字及其記錄等)。

②b-樹上的葉子結點不會指向它的兄弟結點,而b+樹上的葉子結點會指向它的兄弟結點。

作點解釋:這些葉子結點乙個指向乙個,最終連線成乙個連結串列。

③b-樹只能進行分區間查詢,而b+樹上可以有兩種查詢:順序查詢和分區間查詢。

④b-樹上所有的非葉結點都滿足有n個關鍵字的話有n+1棵子樹,而b+樹上所有的非葉結點含n個關鍵字的話只含n棵子樹。這個不同引起了如下幾點的不同:

(1)b-樹的非葉結點有n+1個查詢區間,而b+樹的卻少了乙個區間,這個區間恰好是最右邊的區間(如果存在,這個區間所指的子樹上的所有關鍵字的值都大於結點的所有關鍵字的值)。

(2)在b-樹上,除根的非葉結點的子樹個數不能少於m/2取上界(這個值用lowbou表示),等價地,關鍵字的個數不能少於lowbou-1,但在b+樹上這個關係發生了變化,除根的其他結點的子樹個數同樣不能少於lowbou,但關鍵字的個數卻不能少於lowbou,而不是lowbou減一,這個會給b+樹的一些演算法的具體實現帶來不同。

(3)由於根結點至少需要兩棵子樹,因而b-樹上的根結點的關鍵字可以只有乙個,但是b+樹不能,它至少要有兩個關鍵字,這樣它才可以有兩棵子樹(至於為什麼根結點都需要兩棵子樹,是因為它們都是平衡的)。

⑤b-樹上每乙個關鍵字都配有記錄,而在b+樹上只有葉子結點上的關鍵字才配有記錄。

作點解釋:在b+樹上,所有關鍵字的記錄(指標)都集中在葉子結點上,其他地方的關鍵字只是充當索引,並沒有與之配有相應的記錄的指標。

⑥b-樹查詢可以停在某個非葉結點上,而b+樹不能停在非葉結點上,它需要一直查詢到葉子結點才能停下,因為b+樹的關鍵字的記錄只在葉子結點上。

作點補充和解釋:在b+樹上只要給定的關鍵字的大小不要比根結點的所有關鍵字都大(這樣就沒查詢的必要了,因為全樹最大的值就在根結點的最右邊),那麼對於這個關鍵字的查詢,最後一定是停在葉子結點上的,無論它是否存在在b+樹上,或者換句話說,無論查詢成功與否。

⑦b-樹上的關鍵字在全樹中出現且僅出現一次,而在b+樹上乙個關鍵字可以出現在多個位置,可以有多個,但只有乙個位置的關鍵字配有記錄。

⑧b+樹非葉結點上最右邊的關鍵字表明了它所有子樹中關鍵字的最大值,而b-樹沒有這規律

b+樹和b-樹最大的差別可以說是⑤,甚至這不僅是和b-樹的差異,和其他一般的bst樹都是這樣,b+樹上非葉結點上的關鍵字只是索引,它沒有記錄,而關鍵字真正的記錄是在葉子結點上。

注意:①b-樹上非葉結點是全部的內部結點,而b+樹上的非葉結點不是全部的內部結點,它除去了最下層的結點。

②lowbou是子樹下界的意思,或者說最小子樹個數。

b+樹和b-樹的差別

4樓:匿名使用者

b+樹是對b-樹的改進,要求所有的資訊都在葉子節點上,且葉子節點都在同一深度,而b-樹的葉子節點可以在任意深度。

5樓:佘奇費莫昆琦

b-樹是一種多路搜尋樹(並不是二叉的。),一顆m階的b-樹,或為空樹,或者定義任意非葉子結點最多只有m個兒子。

且m>2;根結點的兒子數為[2,

m]。除根結點以外的非葉子結點的兒子數為[m/2]。

每個結點存放至少m/2-1(取上整)和至多m-1個關鍵字;(至少2個關鍵字)非葉子結點的關鍵字個數=指向兒子的指標個數-1;

b+樹,

b+樹是b-樹的變體,也是一種多路搜尋樹:其定義基本與b-樹同。

b-樹是一種

多路搜尋

樹(並不是二叉的。),一顆m階

的b-樹,或為空樹,或

者定義任意非葉子結點最

多只有m

個兒子。

且m>2;根

結點的兒子數

為[2,

m]。除根結

點以外的非葉子結點的兒子數為[m/2]。

每個結點存放至

少m/2-1

(取上整)和至多

m-1個關鍵

字;(至少2個關鍵字)非葉子結點的關

鍵字個數

=指向兒子

指標個數-1;

b+樹,

b+樹是b-樹的變體,

也是一種多路搜尋樹:其定義基本與b-樹同。

6樓:葷蕩冠運萊

b-樹:多路搜尋樹,每個結點儲存m/2到m個關鍵字,非葉子結點儲存指向關鍵字範圍的子結點;

所有關鍵字在整顆樹中出現,且只出現一次,非葉子結點可以命中;

b+樹:在b-樹基礎上,為葉子結點增加連結串列指標,所有關鍵字都在葉子結點中出現,非葉子結點作為葉子結點的索引;b+樹總是到葉子結點才命中;

7樓:樂意丶

對於一棵m階的b-樹和一棵m階的b+樹,它們的主要差異:

①b-樹的葉子結點不含任何資訊,而b+樹的葉子結點含資訊(關鍵字及其記錄等)。

②b-樹上的葉子結點不會指向它的兄弟結點,而b+樹上的葉子結點會指向它的兄弟結點。

作點解釋:這些葉子結點乙個指向乙個,最終連線成乙個連結串列。

③b-樹只能進行分區間查詢,而b+樹上可以有兩種查詢:順序查詢和分區間查詢。

④b-樹上所有的非葉結點都滿足有n個關鍵字的話有n+1棵子樹,而b+樹上所有的非葉結點含n個關鍵字的話只含n棵子樹。這個不同引起了如下幾點的不同:

(1)b-樹的非葉結點有n+1個查詢區間,而b+樹的卻少了乙個區間,這個區間恰好是最右邊的區間(如果存在,這個區間所指的子樹上的所有關鍵字的值都大於結點的所有關鍵字的值)。

(2)在b-樹上,除根的非葉結點的子樹個數不能少於m/2取上界(這個值用lowbou表示),等價地,關鍵字的個數不能少於lowbou-1,但在b+樹上這個關係發生了變化,除根的其他結點的子樹個數同樣不能少於lowbou,但關鍵字的個數卻不能少於lowbou,而不是lowbou減一,這個會給b+樹的一些演算法的具體實現帶來不同。

(3)由於根結點至少需要兩棵子樹,因而b-樹上的根結點的關鍵字可以只有乙個,但是b+樹不能,它至少要有兩個關鍵字,這樣它才可以有兩棵子樹(至於為什麼根結點都需要兩棵子樹,是因為它們都是平衡的)。

⑤b-樹上每乙個關鍵字都配有記錄,而在b+樹上只有葉子結點上的關鍵字才配有記錄。

作點解釋:在b+樹上,所有關鍵字的記錄(指標)都集中在葉子結點上,其他地方的關鍵字只是充當索引,並沒有與之配有相應的記錄的指標。

⑥b-樹查詢可以停在某個非葉結點上,而b+樹不能停在非葉結點上,它需要一直查詢到葉子結點才能停下,因為b+樹的關鍵字的記錄只在葉子結點上。

作點補充和解釋:在b+樹上只要給定的關鍵字的大小不要比根結點的所有關鍵字都大(這樣就沒查詢的必要了,因為全樹最大的值就在根結點的最右邊),那麼對於這個關鍵字的查詢,最後一定是停在葉子結點上的,無論它是否存在在b+樹上,或者換句話說,無論查詢成功與否。

⑦b-樹上的關鍵字在全樹中出現且僅出現一次,而在b+樹上乙個關鍵字可以出現在多個位置,可以有多個,但只有乙個位置的關鍵字配有記錄。

⑧b+樹非葉結點上最右邊的關鍵字表明了它所有子樹中關鍵字的最大值,而b-樹沒有這規律

b+樹和b-樹最大的差別可以說是⑤,甚至這不僅是和b-樹的差異,和其他一般的bst樹都是這樣,b+樹上非葉結點上的關鍵字只是索引,它沒有記錄,而關鍵字真正的記錄是在葉子結點上。

注意:①b-樹上非葉結點是全部的內部結點,而b+樹上的非葉結點不是全部的內部結點,它除去了最下層的結點。

②lowbou是子樹下界的意思,或者說最小子樹個數。

b2b和b2c是什麼意思,什麼是b2b和b2c

1 b2b是指進行電子商務交易的供需雙方都是商家 或企業 公司 她 他 們使用了網際網路的技術或各種商務網路平台,完成商務交易的過程。電子商務是現代b2bmarketing的一種具體主要的表現形式。2 b2c是business to customer的縮寫,而其中文簡稱為 商對客 商對客 是電子商務...

B2B和B2C是什麼意思,有什麼區別?

上面的已經給你講了!他們的區別了!b2b 的代表就是!阿里巴巴網!c2c的代表就是 網。希望採納。通俗易懂的說,b2b就是公司對公司 b2c就是公司對個人。b2b2和b2c都是電子商務中的銷售模式。b2b是企業對企業的銷售模式,例如 阿里巴巴網。b2c是企業對人的銷售模式,例如 天貓,京東。b2b,...

a志願和b志願的區別什麼,A志願和B志願的區別什麼?

只是志願錄取順序不同 1 a志願,相對於第1志願,是高考生平行志願中所在的批次首先選擇填報的院校,其次還也是考生每各院校第乙個選擇的專業。當高考生達到a志願錄取線,則a志願院校優先錄取。2 b志願,相對於第二志願,當考生沒達到第一志願的錄取分數時,第二志願可以錄取。b志願是自己第二想上的且一般可以上...