java二叉树平衡二叉树B树B+树的区别
二叉树（普通二叉树）
1. 所有节点最多拥有两个子节点，即度不大于2
2. 左子树的键值小于根的键值，右子树的键值大于根的键值
平衡二叉树(AVL树) 使用avl算法为了减少二叉查找树层次，提高查找速度，可以通过旋转重新达到平衡。也称自平衡二叉树
1)它的左右两个子树的高度差(平衡因子)的绝对值不超过1，
2)并且左右两个子树都是一棵平衡二叉树，
3)同时，平衡二叉树必定是二叉搜索树
红黑树(Java集合中的TreeSet和TreeMap)
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种平衡二叉树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
B-树(多路搜索树（并不一定是二叉的）)把树的节点关键字增多后树的层级比原来二叉树的层级少了，这样就可以减少数据查找的次数
- 关键字集合分布在整颗树中；
- 任何一个关键字出现且只出现在一个结点中；
- 搜索有可能在非叶子结点结束；
- 其搜索性能等价于在关键字全集内做一次二分查找；
- 所有的叶子节点都在同一层上
B+树
是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点**。
1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好
是有序的；
2. 不可能在非叶子结点命中；
3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储
（关键字）数据的数据层；
4. 更适合文件索引系统；
总结
- B+tree 是在 B- tree基础上的优化，使其更适应存储索引结构
- B- tree的结构中，每个节点不仅包括数据的key值，也包括data值。而每一页的存储空间都是有限的，如果data数据较大的时候，会导致，每一页中存储的key比较少，当存储的数据量比较大时，同样会导致B- tree的查询深度很大，增加磁盘IO次数，进而影响查询效率
- B+ tree中，非叶子节点上只存储key的信息，这样可以加大每一页中存储key的数量，降低B+ tree的高度。
和b树的区别：
- 非叶子节点只存储key信息
- 所有叶子节点之间有一个链指针
- B+的非叶子节点只进行数据的索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样。
- B+树的应用场景主要是数据库索引结构，数据库的查询有时候可能一次多条，如果分布在不同的层（树的层级），那么在取出数据后，还需要做排序。而在一个层级上，且有指针连接各个叶子节点也使得查询效率更高。