B tree

B树比较简单,以前写过的最小堆、最大堆之类的,就是在堆内实现的B树,每个节点的左分叉为小于该节点值,右分叉为大于该节点值,这样就实现了快速查找。

B-Tree

首先给下定义,假设节点最多有M(M>2)个子节点,则称为M阶B-Tree,那么满足以下条件的树就是B-Tree。

1.所有节点最多有M个子节点
2.假设不是空树,根节点最少有2个子节点
3.非根节点的节点,最少有(M+1)/2个子节点,假设M=4,则最少有2个子节点
4.假设某个节点有N个节点,则该节点则有N-1个关键字
5.由(3)和(4)可知,某个节点的关键字数=节点的子节点数-1,假设该节点的关键字分别为k(1)、k(2)、k(N-1),则必须满足k(1)>k(2)>…>k(N-1);假设该子节点分别为c(1)、c(2)、c(N),则假设搜索某个关键词k,该关键词满足条件k<k(1),则子节点c(1)满足条件,假设k(1)<k<k(2),则满足子节点c(2),假设k满足k>k(N-1),则满足子节点c(N)

B+Tree

B+Tree的定义和B-Tree差不多,主要有以下几点差异:

1.节点数和关键词数相同
2.比较范围不同,假设k满足条件k(1)<=k<k(2),则k满足子节点c(1),在c(1)中必然第一个元素是k(1) ,所以在叶子节点中,包含了全部的关键词信息
3.由于(2),所以B-在任意的节点均可以查找完成,而B+必须得搜索到叶子节点才能完成,所以某个值假如正好是父节点的k(1),则k(1)会不断往下传递

共 0 条回复
暂时没有人回复哦,赶紧抢沙发
发表新回复

作者

sryan
today is a good day