B树

磁盘操作的缓慢导致需要一颗不那么高的查找树，以减少访问磁盘的次数。

对于一颗完全M叉树，其高度大约是LogmN。M叉查找树可以参照二叉查找树建立。

上述想法的一种实现是B树，基本的B树的定义使其原则上保证了只有少数的磁盘访问。

M阶B树具有以下特性：

  1. 数据项存储在树叶上
  2. 非叶节点存储直到M-1个关键字一指示搜索的方向；关键字i代表子树i+1中的最小的关键字
  3. 树的根或者是一片树叶，或者其儿子数在2和M之间
  4. 除根外，所有非树叶节点的儿子数载M/2和M之间
  5. 所有的树叶都在相同的深度上并由L/2和L之间个数据项，L的确定稍后描述

注：要求半满是为了使得B树不会退化为简单的二叉树

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 关于B树的一些总结(一)
    B树的定义 一棵m阶的B树满足下列条件： 树中每个结点至多有m个孩子。 除根结点和叶子结点外，其它每个结点至少有m...
    文档随手记阅读 13,470评论 0赞 25
  • B树（转）
    原文链接 B树 1.前言： 动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（...
    非典型程序员阅读 1,214评论 0赞 3
  • B树和B+树
    本文转载自博客，因为题主写的已经很详细了。 写在前面的一点，面试专用（m阶指的是每个节点最多有m个子树）。 一个m...
    放开那个BUG阅读 1,219评论 0赞 5
  • 6. B树
    B树 ： B-Tree是 平衡的 m 路查找树，"B"表示平衡；严格意义上 ： B-Tree并非二分查找树（多叉结...
    執著我們的執著阅读 3,697评论 0赞 3
  • B树
    B树 1.前言： 动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balan...
    铁甲依然在_978f阅读 1,473评论 0赞 4