算法与数据结构(9): B-树

B-树的定义

B-树是为磁盘或其他直接存取的辅助存储设备而设计的一种多路平衡查找树。

一棵math阶的B-树,或为空树,或为满足下列特性的math叉树:

  • 树中每个结点至多有math棵子树。
  • 若根结点不是叶子结点,则它至少有两棵子树。
  • 除根结点外,所有的非终端结点至少为math棵子树。
  • 所有的非终端结点中包含下列信息数据math,其中math为关键字的个数,mathmath个递增的关键字,mathmath个子树的根结点指针。对任意mathmath所指的子树中所有结点的关键字均大于math且小于math。(math所指子树中所有结点的关键字均小于mathmath所指子树中所有结点的关键字均大于math
  • 所有叶子节点均在同一层,并且不携带信息。

math阶代表一个树节点最多有多少个查找路径。

4阶的B-树的实例如下所示

Comments
登录后评论
Sign In