m階b樹m指的什么意思 tree命令使用

在數(shù)據(jù)結(jié)構(gòu)中m階B樹是什么意思呀？B-樹的定義，二叉樹的階數(shù)是什么？“m階B樹”這里的“m階”是什么意思？m階b樹是什么意思？b tree 和 b+ tree 的區(qū)別，什么是樹的階數(shù)？

本文導航

• 數(shù)據(jù)結(jié)構(gòu)中樹的深度與高度
• 多叉樹的定義
• 二叉樹的深度和層數(shù)一樣嗎
• 什么是一級樹形
• tree命令使用
• 樹的直徑以什么高度計算

數(shù)據(jù)結(jié)構(gòu)中樹的深度與高度

B-樹的定義

　 一棵m(m≥3)階的B-樹是滿足如下性質(zhì)的m叉樹：

(1)每個結(jié)點至少包含下列數(shù)據(jù)域：

(j，P 0 ，K l ，P 1 ，K 2 ，…，K i ，P i )

其中：

j為關(guān)鍵字總數(shù)

K i (1≤i≤j)是關(guān)鍵字，關(guān)鍵字序列遞增有序：K 1 <K 2 <…<K i 。

P i (0≤i≤j)是孩子指針。對于葉結(jié)點，每個P i 為空指針。

注意：

　 ①實用中為節(jié)省空間，葉結(jié)點中可省去指針域P i ，但必須在每個結(jié)點中增加一個標志域leaf，其值為真時表示葉結(jié)點，否則為

內(nèi)部結(jié)點。

　 ②在每個內(nèi)部結(jié)點中，假設(shè)用keys(Pi)來表示子樹Pi中的所有關(guān)鍵字，則有：

　 keys(P 0 )<K 1 <keys(P 1 )<K 2 <…<K i <keys(P i )

即關(guān)鍵字是分界點，任一關(guān)鍵字Ki左邊子樹中的所有關(guān)鍵字均小于K i ，右邊子樹中的所有關(guān)鍵字均大于K i 。

(2)所有葉子是在同一層上，葉子的層數(shù)為樹的高度h。

(3)每個非根結(jié)點中所包含的關(guān)鍵字個數(shù)j滿足：

(4)若樹非空，則根至少有1個關(guān)鍵字，故若根不是葉子，則它至少有2棵子樹。根至多有m-1個關(guān)鍵字，故至多有m棵子樹。

多叉樹的定義

B-樹是一種多路搜索樹（并不一定是二叉的）1970年，R.Bayer和E.mccreight提出了一種適用于外查找的樹，它是一種平衡的多叉樹，稱為B樹（或B-樹、B_樹）。一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜索樹。它或者是空樹，或者是滿足下列性質(zhì)的樹：1、根結(jié)點至少有兩個子女；2、每個非根節(jié)點所包含的關(guān)鍵字個數(shù) j 滿足：┌m/2┐ - 1 <= j <= m - 1；3、除根結(jié)點以外的所有結(jié)點（不包括葉子結(jié)點）的度數(shù)正好是關(guān)鍵字總數(shù)加1，故內(nèi)部子樹個數(shù) k 滿足：┌m/2┐ <= k <= m ；4、所有的葉子結(jié)點都位于同一層。在B-樹中，每個結(jié)點中關(guān)鍵字從小到大排列，并且當該結(jié)點的孩子是非葉子結(jié)點時，該k-1個關(guān)鍵字正好是k個孩子包含的關(guān)鍵字的值域的分劃。因為葉子結(jié)點不包含關(guān)鍵字，所以可以把葉子結(jié)點看成在樹里實際上并不存在外部結(jié)點，指向這些外部結(jié)點的指針為空，葉子結(jié)點的數(shù)目正好等于樹中所包含的關(guān)鍵字總個數(shù)加1。B-樹中的一個包含n個關(guān)鍵字，n+1個指針的結(jié)點的一般形式為： （n,P0,K1,P1,K2,P2,…,Kn,Pn）其中，Ki為關(guān)鍵字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之間的關(guān)鍵字的子樹的指針。

二叉樹的深度和層數(shù)一樣嗎

二叉樹的階數(shù)是一個節(jié)點的子節(jié)點數(shù)目的最大值。對于一棵m階B-tree，每個結(jié)點至多可以擁有m個子結(jié)點。

各結(jié)點的關(guān)鍵字和可以擁有的子結(jié)點數(shù)都有限制，規(guī)定m階B-tree中，根結(jié)點至少有2個子結(jié)點，除非根結(jié)點為葉子節(jié)點；

相應(yīng)的，根結(jié)點中關(guān)鍵字的個數(shù)為1~m-1，比節(jié)點數(shù)目少一個；非根結(jié)點至少有[m/2]（[]，向上取整）個子結(jié)點，相應(yīng)的，關(guān)鍵字個數(shù)為[m/2]-1~m-1。

1、M為樹的階數(shù)，B-樹或為空樹，否則滿足下列條件：定義任意非葉子結(jié)點最多只有M個兒子；且M>2；

2、根結(jié)點的兒子數(shù)為[2, M]；

3、除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M]；

4、每個結(jié)點存放至少M/2（取上整）-1和至多M-1個關(guān)鍵字；（至少2個關(guān)鍵字,根節(jié)點至少一個關(guān)鍵字）；

5、非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1；

6、非葉子結(jié)點的關(guān)鍵字：K[1], K[2], …, K[m-1]，m<M+1；且K[i]< K[i+1] ；

7、非葉子結(jié)點的指針：P[1], P[2], …, P[m]；其中P[1]指向關(guān)鍵字小于K[1]的子樹，P[m]指向關(guān)鍵字大于K[m-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹；

參考資料來源：百度百科-階數(shù)

什么是一級樹形

m階為一節(jié)點至多有m棵子樹

，也就是說B樹上的結(jié)點最多只能有m棵子樹。。。

tree命令使用

一、B樹的起源

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

二、B樹長啥樣

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

總的來說，m階B樹滿足以下條件：

每個節(jié)點至多可以擁有m棵子樹

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

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

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

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

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

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

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

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

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

三、Plus版——B+樹

作為B樹的加強版，B+樹與B樹的差異在于：

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

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

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

請點擊輸入圖片描述

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

樹的直徑以什么高度計算

b樹是一種用于查找的數(shù)據(jù)結(jié)構(gòu)

m階表示m路查找

m為2時就是二叉b樹，也即平衡二叉樹