B- 树

1972 年 R. Bayer 和 E. McCreight 的论文(参考资料 [1])提出了 B- 树。B- 树是一棵平衡树,与一般的平衡二叉树(AVL,红黑树等)不同的是,B- 树的每个节点最多可以拥有 m(m=2)个元素,(m+1)个子节点,并且所有的叶子节点位于同一层。B- 树的查找和插入的时间复杂度和二叉树一样,都是 O(logn),但因为每个节点保存的元素比较多(一般是几十个到几百个之间),树的高度比一般的二叉树要小很多,访问硬盘次数更少,在数据不能全部加载到内存的时候比一般的二叉树效率要好。

定义

一棵最多有 2n+1 个元素(其中 n= 1)的 B- 树的定义如下(参考资料 [2, 3]):

  • 每个节点最多有 2n+1 个元素;
  • 每个非叶子节点(根节点除外)至少有 n+1 棵子树;
  • 如果根节点不是叶子节点,则至少有 2 棵子树;
  • 一个有 k 棵子树的非叶子节点有

阅读全文…