本文共 608 字，大约阅读时间需要 2 分钟。

2-3树

2-3树是一颗自平衡的多路查找树，它并不是一颗二叉树，2-3树具有如下性质：

1. 每个节点有1个或2个key值，对应的子节点为2个子节点或者三个子节点
2. 所有叶子节点到跟节点的长度保持一致
3. 每个节点的key从左到右保持了从小到大的顺序，两个key之间的子树中所有的key一定大于它的父节点的左key，小于右节点的key

2-3树的插入：

B树

上面的2-3树其实就是3阶的B树，一颗m阶的B树定义如下：

• 每个节点最多有m-1个key
• 根节点至少有1个key
• 非根节点至少有Math.ceil(m/2)（向上取整）-1个key
• 每个节点中的key都按照从小到大的顺序排列，每个key的左子树中的所有key都小于它，而右子树中的所有key都大于它
• 所有叶子节点都位于同一层

B+树

B+树是对B树进行优化，它与B树的区别在于：

• 有k个子节点必然有k个key
• 非叶子节点仅具有索引作用，跟记录有关的信息均放在叶子节点中
• 树的所有叶子节点构成一个有序列表
• B+树的所有叶子节点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可

转载地址：http://mqjmb.baihongyu.com/