一、定义
均衡树是搜寻树与堆的联合数学构造
均衡树是一颗空树或者其左右子树高度相差不大于 1，并且左右两颗子树都是均衡二叉树。
均衡树与二叉搜寻树的区别：均衡树自身是二叉搜寻树，但其是二叉搜寻树通过”旋转“失去的最优二叉搜寻树（最优二叉搜寻树：具备起码的均匀比拟次数的二叉搜寻树，均匀比拟次数 = 每个结点的查找概率 * 查找该节点的比拟次数 (从各节点一层一层还是比拟，也就是层数)）求和），集体了解均衡树不肯定是二叉，B 树就能够是多叉。
二、特点
均衡树的均匀查找时间 小于等于 二叉搜寻树的均匀查找时间
三、分类
(1) 均衡二叉树
(2) 红黑树
(3)B 树
根节点至多两个子节点，至少 M 个子节点
其余节点至多 M / 2 个子节点，至少 M 个子节点
每个节点至多 M /2- 1 个 Key，至少 M - 1 个 Key，并且升序排列
所有叶子节点位于同一层
实用于查问多
(4)B+ 树
非叶子节点只存储 Key 值，不存储数据 > 叶子节点存储 key 值和数据。非叶子节点仅具备索引性能，跟记录无关的信息寄存在叶子节点
叶子节点减少链指针，所有叶子节点形成一个有序链表
实用于索引与数据的拆散
一个节点中的 key 从左到右非递加排列，如果某个指针的左右相邻 key 别离是 keyi 和 keyi+1，且不为 null，则该指针指向节点的所有 key 大于等于 keyi 且小于等于 keyi+1。