所有栏目 | 云社区 美国云服务器[国内云主机商]
你的位置:首页 > 云社区 » 正文

B+树和B-树的差别?

发布时间:2020-04-12 08:37:22

资讯分类:差别  结点  子树  叶子
B+树和B-树的差别?

  B+树

  性质:B+树是B-树的变体,也是一种多路搜索树:

  1.其定义基本与B-树同,除了:

  2.非叶子结点的子树指针与关键字个数相同;

  3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);

  4.为所有叶子结点增加一个链指针;

  5.所有关键字都在叶子结点出现;

  

  B-树

  性质:是一种多路搜索树(并不是二叉的):

  1.定义任意非叶子结点最多只有M个儿子;且M>2;

  2.根结点的儿子数为[2, M];

  3.除根结点以外的非叶子结点的儿子数为[M/2, M];

  4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

  5.非叶子结点的关键字个数=指向儿子的指针个数-1;

  6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];

  7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

  8.所有叶子结点位于同一层;

留言与评论(共有 0 条评论)
   
验证码:
Top