几种树对比

树结构，是一种常用的数据结构。数据库中的索引，Map中的底层存储，极大提升了数据的检索效率。比如常见的B树、红黑树，都具有不同的特性，优缺点，应用于不同的场景，以下介绍常用的树的特点及其应用。

平衡二叉树

概念

平衡二叉树（Balanced BinaryTree）又被称为AVL树，是一棵空树，或它的左右两个子树的高度差的绝对值不超过1，并且左右子树都是一棵平衡二叉树。

特点

针对普通的二叉树添加了平衡因子的限制，即左右子树的高度差为1。如果不满足，则要通过一定的策略进行调整。增加这个策略的原因是为了通过二分法提升数据检索的效率，避免极端情况下树往一个方向偏，查询变成线性查找。特点如下：

非叶子节点最多拥有两个子节点；
非叶子节点值大于左子节点，小于右子节点；
树左右两边的高度差不会大于1；

如果不满足平衡需要通过左旋或者右旋来保证平衡。

B-Tree

概念

B树是一棵多路平衡查找树，假设树M阶，代表树为M个分叉，树高M。具有如下特点：

按照节点中的关键字递增排序，左小右大；
非叶子节点数>1并且<=M；
关键字数：节点的关键字>=ceil(M/2)-1，并且<=M-1；
所有叶子节点均在同一层，叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针。

数据的插入

假如一个5阶的B树，则非根节点最小关键字为2，最大关键字为4，插入的时候，则会判断关键字数量，如果数量大于4则要进行分裂。
如已经插入了4个数，12，13，14，16的树结构为：

再插入15的时候则进行分裂，变成：

数据的删除

如果删除一个元素，不满足关键字的个数的要求的时候需要进行调整，满足的话直接删除即可。

特点

B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。