B-樹
首先要區(qū)分的一個問題就是:B樹和二叉樹BinaryTree沒有太大的聯(lián)系。
B樹的B是balanced平衡的意思晨川,而不是binary的意思策肝。也就是說B樹一種多叉平衡樹,二叉樹僅有兩個分支椭微,B樹可以有多個分支吧慢。
B-樹是一種多路搜索樹,一顆m階B樹就是一顆平衡的m路搜索樹赏表。m階的意思是
B樹中的每個節(jié)點至多可以擁有m個子節(jié)點。
一顆m階的B-樹的特性如下:
- 1.每個節(jié)點至多有m個子節(jié)點.
- 2.根節(jié)點若不是葉子節(jié)點匈仗,則至少有兩個子節(jié)點.
- 3.除根節(jié)點和葉子節(jié)點外瓢剿,其他節(jié)點至少擁有ceil(m/2)個子節(jié)點.[mV2,m]
- 4.所有的葉子節(jié)點都出現(xiàn)在同一層.
- 5.每個非根子節(jié)點包含的關鍵字的個數(shù)k滿足: ceil(m/2)-1 <= k <= m-1.
B-樹的特點:
- 任意非葉子節(jié)點最多有m個子節(jié)點,并且m>2.
- 根節(jié)點的子節(jié)點數(shù)為[2,m].
- 除根節(jié)點外的非葉子節(jié)點的子節(jié)點數(shù)為[mV2,m].
- 每個節(jié)點存放的關鍵字的個數(shù)為[ ceil(m/2)-1,m-1].
- 非葉子節(jié)點的關鍵字個數(shù)= 子節(jié)點數(shù)-1.
- 非葉子節(jié)點中的關鍵字k[1],k[2]...k[m-1],滿足k[i] < k[i+1]
- 非葉子節(jié)點的子節(jié)點的指針p[1],p[2]...p[m],滿足p[1]指向的關鍵字小于k[1],p[m]指向的關鍵字都大于k[m-1]悠轩。
- 所有的葉子節(jié)點都在同一層
B-樹的特性決定了所有的關鍵字都會分布在整顆樹種间狂,任何一個關鍵字只能出現(xiàn)在一個節(jié)點中。對于一個關鍵字的搜索可能在非葉子節(jié)點中找到火架,搜索性能相當于在關鍵字全集中做一次二分查找鉴象。