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 棵子树的非叶子节点有 k-1 个元素，按升序排列；

…

阅读全文…