问题：描述以下你了解过的二叉树、平衡树、红黑树、B树、B+树
1、二叉树、平衡树
二叉树只是一个普普通通的数据结构，一种数据保存的抽象思想。当我们去从二叉树中查找数据时，可以通过数据定义排序方式，更加效率的找到数据保存的叶子节点所在。
平衡树和二叉树的主要区别就在根节点的选择，因为二叉树根节点选择的不好，会直接影响查询效率，最坏的情况就相当于链表结构，去遍历数据。平衡二叉树，每次插入数据都会判断是否破坏了二叉树的平衡，保证树形结构中不存在每支数据过大的情况。
我没有见过哪个使用二叉树的实现。主要使用二叉树的变种。
2、红黑树:O(logn)
红黑树应用比较广泛，如jdk8+后，java对HashMap的实现就使用了红黑树。
我理解的红黑树是一个没有严格实现的平衡树。平衡树解决二叉树退化成链表的问题，但是频繁旋转调整根节点也会相对牺牲部分时间。二红黑树放弃了完全平衡，把每个存储节点抽象为红/黑两种颜色。要求每个节点非黑必红，根为黑，每个结束节点（即结束时的null节点）为黑色，如果一个节点是红色，那么两个子节点必须为黑色，限制了从任意节点到其每个结束节点路径中所包含的黑色节点数量相同。这些限制了红黑树从根到结束最长的路径不多于最短路径的两倍。所以即解决了二叉树的不平衡问题，又解决了平衡树的频繁调整根节点的问题。
3、B树
由于磁盘数据存储不等于内存中的数据存储，磁盘的存储是分块存储数据。如果使用平衡树或红黑树存储数据，者会频繁进行磁盘读取io，很大降低了数据查询效率，而B树则分块存储数据，一个节点中存储多条数据，即减少了io次数，同时减少了树的层数。
4、B+树
B+树是对B树的优化，B树中每个节点都会存储数据，而B+树的非结束节点（即叶子节点）只保存数据的索引。这样每个非结束节点保存的数据索引大大增加。B+树相当于数据和索引分开存储，找到索引即可以拿着此索引寻找数据保存地址。且B+树都会对数据进行排序，数据节点上也保存着相邻节点的索引地址，因此相对与B树能更快的找到数据。
文章转载自乐吧了吧，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
