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

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

本文導(dǎo)航

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

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

B-樹的定義

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

(1)每個(gè)結(jié)點(diǎn)至少包含下列數(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)是孩子指針。對(duì)于葉結(jié)點(diǎn)，每個(gè)P i 為空指針。

注意：

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

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

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

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

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

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

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

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

多叉樹的定義

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

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

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

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

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

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

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

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

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

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

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

7、非葉子結(jié)點(diǎn)的指針：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ù)

什么是一級(jí)樹形

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

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

tree命令使用

一、B樹的起源

B樹，最早是由德國計(jì)算機(jī)科學(xué)家Rudolf Bayer等人于1972年在論文 《Organization and Maintenance of Large Ordered Indexes》提出的，不過我去看了看原文，發(fā)現(xiàn)作者也沒有解釋為什么就叫B-trees了，所以把B樹的B，簡(jiǎn)單地解釋為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)的路徑

樹的直徑以什么高度計(jì)算

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

m階表示m路查找

m為2時(shí)就是二叉b樹，也即平衡二叉樹