B-/B+樹

M為樹的階數(shù)疲吸,B-樹或?yàn)榭諛涓焕埃駝t滿足下列條件:
對(duì)于一棵M階的B-樹

  1. 任意非葉子結(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])的子樹夭委;
  8. 所有葉子結(jié)點(diǎn)位于同一層幅狮;
    如:(M=3)
    B-樹.jpg

B+樹是文件系統(tǒng)所需而出的一種B-樹的變型樹。一棵m階的B+樹和m階的B-樹的差異在于:

  1. 有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必然有k個(gè)關(guān)鍵碼株灸;
  2. 非葉結(jié)點(diǎn)僅具有索引作用崇摄,和記錄有關(guān)的信息均存放在葉結(jié)點(diǎn)中。
  3. 樹的所有葉結(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表慌烧,可以按照關(guān)鍵碼排序的次序遍歷全部記錄逐抑。

    通常在B+樹上有兩個(gè)頭指針,一個(gè)指向根結(jié)點(diǎn)屹蚊,一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)厕氨。
    B+樹

B和B+樹的區(qū)別在于,B+樹的非葉子結(jié)點(diǎn)只包含導(dǎo)航信息汹粤,不包含實(shí)際的值命斧,所有的葉子結(jié)點(diǎn)和相連的節(jié)點(diǎn)使用鏈表相連,便于區(qū)間查找和遍歷玄括。

B+ 樹的優(yōu)點(diǎn)在于:

由于B+樹在內(nèi)部節(jié)點(diǎn)上不包含數(shù)據(jù)信息冯丙,因此在內(nèi)存頁(yè)中能夠存放更多的key肉瓦。 因此訪問(wèn)葉子節(jié)點(diǎn)上關(guān)聯(lián)的數(shù)據(jù)也具有更好的緩存命中率遭京。
B+樹的葉子結(jié)點(diǎn)都是相鏈的,因此對(duì)整棵樹只需要一次線性遍歷葉子結(jié)點(diǎn)即可泞莉。而且由于數(shù)據(jù)順序排列并且相連哪雕,所以便于區(qū)間查找和搜索。而B樹則需要進(jìn)行每一層的遞歸遍歷鲫趁。相鄰的元素可能在內(nèi)存中不相鄰斯嚎,所以緩存命中性沒(méi)有B+樹好。

但是B樹也有優(yōu)點(diǎn),其優(yōu)點(diǎn)在于堡僻,由于B樹的每一個(gè)節(jié)點(diǎn)都包含key和value糠惫,因此經(jīng)常訪問(wèn)的元素可能離根節(jié)點(diǎn)更近,因此訪問(wèn)也更迅速钉疫。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末硼讽,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子牲阁,更是在濱河造成了極大的恐慌固阁,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件城菊,死亡現(xiàn)場(chǎng)離奇詭異备燃,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)凌唬,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門并齐,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人法瑟,你說(shuō)我怎么就攤上這事冀膝。” “怎么了霎挟?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵窝剖,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我酥夭,道長(zhǎng)赐纱,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任熬北,我火速辦了婚禮疙描,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘讶隐。我一直安慰自己起胰,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布巫延。 她就那樣靜靜地躺著效五,像睡著了一般。 火紅的嫁衣襯著肌膚如雪炉峰。 梳的紋絲不亂的頭發(fā)上畏妖,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音疼阔,去河邊找鬼戒劫。 笑死半夷,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的迅细。 我是一名探鬼主播巫橄,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼茵典!你這毒婦竟也來(lái)了嗦随?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤敬尺,失蹤者是張志新(化名)和其女友劉穎枚尼,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體砂吞,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡署恍,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了蜻直。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片盯质。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖概而,靈堂內(nèi)的尸體忽然破棺而出溶推,到底是詐尸還是另有隱情慷丽,我是刑警寧澤吠卷,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布当船,位于F島的核電站,受9級(jí)特大地震影響餐曼,放射性物質(zhì)發(fā)生泄漏压储。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一源譬、第九天 我趴在偏房一處隱蔽的房頂上張望集惋。 院中可真熱鬧,春花似錦踩娘、人聲如沸刮刑。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)雷绢。三九已至,卻和暖如春厚脉,著一層夾襖步出監(jiān)牢的瞬間习寸,已是汗流浹背胶惰。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工傻工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓中捆,卻偏偏與公主長(zhǎng)得像鸯匹,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子泄伪,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • B樹的定義 一棵m階的B樹滿足下列條件: 樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子殴蓬。 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外,其它每個(gè)結(jié)點(diǎn)至少有m...
    文檔隨手記閱讀 13,244評(píng)論 0 25
  • 原文鏈接 B樹 1.前言: 動(dòng)態(tài)查找樹主要有:二叉查找樹(Binary Search Tree)蟋滴,平衡二叉查找樹(...
    非典型程序員閱讀 1,164評(píng)論 0 3
  • B樹 1.前言: 動(dòng)態(tài)查找樹主要有:二叉查找樹(Binary Search Tree)染厅,平衡二叉查找樹(Balan...
    鐵甲依然在_978f閱讀 1,447評(píng)論 0 4
  • B-樹尔苦,就是B樹涩馆,B樹的原英文名是B-tree,所以很多翻譯為B-樹,就會(huì)很多人誤以為B-樹是一種樹、B樹是另外一...
    xx1994閱讀 23,816評(píng)論 1 17
  • 對(duì)支付流程的初識(shí)
    jlnbda3488375閱讀 205評(píng)論 0 0