1972 年 R. Bayer 和 E. McCreight 提出了 B 树。1979 年 Douglas Comer 在 The Ubiquitous B-Tree 提出了 B 树的一个变形——B+ 树。由于多路平衡树减少了磁盘读写次数，并且仍然保持 O(logN) 的插入/删除/查找的效率，被广泛应用于数据库和文件系统中。

定义（参考资料 [1, 3]）

模仿 B 树的定义（参考资料 [3]），一棵 m 阶的 B+ 树可以这样定义：

• 每个节点最多可以有 m 个元素；
• 除了根节点外，每个节点最少有 (m/2)

…

阅读全文…