B樹
B樹即平衡查找樹竖慧,一般理解為平衡多路查找樹季研,也稱為B-樹鸽疾、B_樹熊尉。是一種自平衡樹狀數(shù)據(jù)結(jié)構(gòu)焚挠,能對存儲的數(shù)據(jù)進(jìn)行O(log n)的時(shí)間復(fù)雜度進(jìn)行查找、插入和刪除碳胳。B樹一般較多用在存儲系統(tǒng)上递沪,比如數(shù)據(jù)庫或文件系統(tǒng)豺鼻。
B樹特點(diǎn)
1.B樹可以定義一個(gè)m值作為預(yù)定范圍,即m路(階)B樹款慨。
1.每個(gè)節(jié)點(diǎn)最多有m個(gè)孩子儒飒。
2.每個(gè)節(jié)點(diǎn)至少有ceil(m/2)個(gè)孩子,除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外檩奠。
3.對于根節(jié)點(diǎn)桩了,子樹個(gè)數(shù)范圍為[2,m]附帽,節(jié)點(diǎn)內(nèi)值的個(gè)數(shù)范圍為[1,m-1]。
4.對于非根節(jié)點(diǎn)井誉,節(jié)點(diǎn)內(nèi)的值個(gè)數(shù)范圍為[ceil(m/2)-1,m-1]蕉扮。
5.根節(jié)點(diǎn)(非葉子節(jié)點(diǎn))至少有兩個(gè)孩子。
6.一個(gè)有k個(gè)孩子的非葉子節(jié)點(diǎn)包含k-1個(gè)值颗圣。
7.所有葉子節(jié)點(diǎn)在同一層喳钟。
8.節(jié)點(diǎn)內(nèi)的值按照從小到大排列。
9.父節(jié)點(diǎn)的若干值作為分離值分成多個(gè)子樹在岂,左子樹小于對應(yīng)分離值奔则,對應(yīng)分離值小于右子樹。
以下是一個(gè)四階B樹蔽午,
插入
假設(shè)現(xiàn)在構(gòu)建一棵四階B樹易茬,開始插入“A”,直接作為根節(jié)點(diǎn)及老,
插入“B”疾呻,大于“A”,放右邊写半,
插入“C”,按順序排到最后尉咕,
繼續(xù)插入“D”叠蝇,直接添加的結(jié)果如下圖,此時(shí)超過了節(jié)點(diǎn)可以存放容量年缎,對于四階B樹每個(gè)節(jié)點(diǎn)最多存放3個(gè)值悔捶,此時(shí)需要執(zhí)行分裂操作,
分裂操作為单芜,先選取待分裂節(jié)點(diǎn)的中值蜕该,這里為“B”,然后將中值“B”放到父節(jié)點(diǎn)中洲鸠,因?yàn)檫@里還沒有父節(jié)點(diǎn)堂淡,那么直接創(chuàng)建一個(gè)新的父節(jié)點(diǎn)存放“B”,而原來小于“B”的那些值作為左子樹扒腕,原來大于“B”的那些值作為右子樹绢淀。
繼續(xù)插入“E”,”E”大于“B”瘾腰,往右子節(jié)點(diǎn)皆的,
分別于“C”和“D”比較,大于它們蹋盆,放到最右邊费薄,
插入“F”硝全,“F”大于“B”,往右子樹楞抡,
“F”分別與“C””D”“E”比較伟众,大于它們,放到最右邊拌倍,此時(shí)觸發(fā)分裂操作赂鲤,
選取待分裂節(jié)點(diǎn)的中值“D”,然后將中值“D”放到父節(jié)點(diǎn)中柱恤,父節(jié)點(diǎn)中的“B”小于“D”数初,于是放到“B”右邊,而原來小于“D”的那些值作為左子樹梗顺,原來大于“D”的那些值作為右子樹泡孩。
繼續(xù)插入“M”,結(jié)果為寺谤,
插入“L’仑鸥,大于“B”“D”,往右子樹变屁,
“L”大于“E”“F”小于“M”眼俊,于是放到第三個(gè)位置,此時(shí)觸發(fā)分裂操作粟关,
選取待分裂節(jié)點(diǎn)的中值“F”疮胖,然后將中值“F”放到父節(jié)點(diǎn)中,父節(jié)點(diǎn)中的“B”“D”都小于“F”闷板,于是放到最右邊澎灸,而原來小于“F”的那些值作為左子樹,原來大于“F”的那些值作為右子樹遮晚。
插入“K”性昭,結(jié)果為,
插入“J”县遣,大于“B”“D”“F”糜颠,往右子樹,
“J”小于“K”“L”“M”萧求,于是放到第一個(gè)位置括蝠,此時(shí)觸發(fā)分裂操作,
選取待分裂節(jié)點(diǎn)的中值“K”饭聚,然后將中值“K”放到父節(jié)點(diǎn)中忌警,父節(jié)點(diǎn)中的“B”“D”“F”都小于“K”,于是放到最右邊,而原來小于“K”的那些值作為左子樹法绵,原來大于“K”的那些值作為右子樹箕速。此時(shí)父節(jié)點(diǎn)也觸發(fā)分裂操作,
選取待分裂節(jié)點(diǎn)的中值“D”朋譬,然后將中值“D”放到父節(jié)點(diǎn)中盐茎,由于還沒有父節(jié)點(diǎn),那么直接創(chuàng)建一個(gè)新的父節(jié)點(diǎn)存放“D”徙赢,而原來小于“D”的那些值作為左子樹字柠,原來大于“D”的那些值作為右子樹。
插入“I”狡赐,大于“D”窑业,往右子樹,
右子樹不是葉子節(jié)點(diǎn)枕屉,繼續(xù)往下常柄,這時(shí)“I”大于“F”而小于“K”,所以往第二個(gè)分支搀擂,
“I”小于“J”西潘,于是放到左邊,
類似地哨颂,插入“H”喷市,結(jié)果如下,
插入“G”威恼,往左子樹品姓,
往中間分支,
觸發(fā)分裂操作沃测,
選取待分裂節(jié)點(diǎn)的中值“H”,然后將中值“H”放到父節(jié)點(diǎn)中食茎,”H”大于父節(jié)點(diǎn)中的“F”而小于“K”蒂破,于是放到中間,而原來小于“H”的那些值作為左子樹别渔,原來大于“H”的那些值作為右子樹附迷。
綜上所述,插入操作的核心是分裂操作哎媚。無需分裂的情況比較簡單喇伯,直接插入即可;如果插入后超過節(jié)點(diǎn)容量拨与,這個(gè)容量可預(yù)先自定義稻据,則需要進(jìn)行分裂操作,需要注意的是分裂可能引起父節(jié)點(diǎn)需要繼續(xù)分裂买喧。
查找
對B樹進(jìn)行查找就比較簡單捻悯,查找過程有點(diǎn)類似二叉搜索樹匆赃,從根節(jié)點(diǎn)開始查找,根據(jù)比較數(shù)值找到對應(yīng)的分支今缚,繼續(xù)往子樹上查找算柳。
比如查找“I”,”I”大于“D”姓言,往右子樹瞬项,
“I”分別與節(jié)點(diǎn)內(nèi)值比較,大于“F”“H”而小于“K”何荚,往第三個(gè)分支囱淋,
逐一比較節(jié)點(diǎn)內(nèi)的值,找到“I”兽泣。
轉(zhuǎn)自:https://blog.csdn.net/wangyangzhizhou/article/details/82215430