B树及其基本操作、B+树的基本概念 |
您所在的位置：网站首页 › 关键字的概念是什么 › B树及其基本操作、B+树的基本概念 |
B树及其基本操作、B+树的基本概念
|
B树及其基本操作、B+树的基本概念
1、B树、B+树的基本概念(1)、B树的基本概念及性质(2)、B+树的基本概念及性质
2、B树与B+树的区别3、B树的基本操作(1)、B树的查找(2)、B树的插入(3)、B树的删除
1、B树、B+树的基本概念
(1)、B树的基本概念及性质
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。 一棵m阶B树或为空树,或为满足下列特性的m叉树： 若根结点不是终端节点，则至少有两棵子树，最多有m棵子树。除根结点外的所有非叶结点至少有⌈m/2⌉棵子树，最多有m棵子树。所有的非叶结点都出现在同一层次上，并且不带信息（可视为失败结点）。所有非叶结点的结构如下：
a)、Pi-1所指子树中所有结点的关键字均小于Ki b)、Pi所指子树中所有结点的关键字均大于Ki (2)、B+树的基本概念及性质B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。 一棵m阶的B+树需满足下列条件: 每个分支结点最多有m棵子树。非叶根结点至少有两棵子树,其他每个分支结点至少有⌈m/2⌉棵子树。结点的子树个数与关键字个数相等。所有叶结点包含全部关键字及指向相应记录的指针，而且叶结点中将关键字按大小顺序排列,并且相邻叶结点按大小顺序相互链接起来。所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。 2、B树与B+树的区别 在B树中，具有n个关键字的结点含有（n+1）棵子树；而在B+树中，具有n个关键字的结点只含有n棵子树,即每个关键字对应一棵子树。在B树中，根结点的关键字个数n的范围是1 |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |