B樹(m叉樹)

(1)每個(gè)結(jié)點(diǎn)最多m棵子樹

(2)根結(jié)點(diǎn)(非葉子)至少2棵子樹

(3)葉結(jié)點(diǎn)同一層

(4)其他?至少m/2(上整)棵子樹,格式(n,A0,K1,A1,K2,A2...Kn,An),n個(gè)數(shù)據(jù),數(shù)據(jù)和子樹嚴(yán)格有序

B樹查找:查結(jié)點(diǎn)(磁盤)+查子樹(內(nèi)存)

B樹插入:最下層插入或分裂(分裂成3部分:滿結(jié)點(diǎn)+單數(shù)據(jù)+剩下結(jié)點(diǎn)->往上插)

B樹刪除:最下層刪除或借(向兄弟:父下移,兄上移)或合并(剩下結(jié)點(diǎn)+父數(shù)據(jù)+(右/左)兄弟)往上迭代借或合并

? ? ? ? ? ? ? (非最下層可以轉(zhuǎn)化為最下層:右子樹最小替換)

=====================================================================

B+樹(變形B樹)

(1)結(jié)點(diǎn)k棵子樹,k個(gè)數(shù)據(jù)

(2)葉結(jié)點(diǎn)含所有數(shù)據(jù)

(3)非葉結(jié)點(diǎn)數(shù)據(jù)為子樹最值

總結(jié)

以上是生活随笔為你收集整理的B树,B+树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。