Java面试-各种树结构简单讲解
参考：https://www.cnblogs.com/caoshouling/p/13574423.html
理解：二叉树的查找的优化，也是利用了类似二分查找的思想，让查找的时间复杂度变成O(log2 n)
1. 树
N叉树浪费链接的存储空间，N越大浪费越严重
解决：N等于2时链接空间浪费率最低，于是有了二叉树
2. 二叉树
优点：链接空间浪费率达到最低。
缺点：无约束的二叉树是无序的，查找的时间复杂度为O(N)，
解决：有了二叉搜索树BST（Binary Search Tree）（又称排序二叉树、有序二叉树、二叉查找树）
3. 二叉搜索树BST
优点：排序二叉树查询、删除和插入的平均时间复杂度都是O(log2 n)
缺点：但是随着节点的添加和删除，查询的时间复杂度在O(log2 n) 到O(n)之间，
也就是说极端情况可能成为链表结构，查询时间复杂度变成O(n)
解决：在添加和删除节点时要维持二叉树的平衡 -> 平衡二叉树（AVL树）、红黑树等
场景：实际使用不多
4. 平衡二叉树（AVL树）
优点：AVL树是高度平衡的二叉树，查找效率非常高，接近二分查找。
缺点：每次插入和删除都需要维护平衡，代价高，耗时大。
解决：不维持严格平衡，只保证近似平衡 -> 红黑树
场景：实际使用不多
5. 近似平衡的二叉树-红黑树
优点：性能稳定，插入、删除、查找的复杂度在最好、最坏的情况都是O(log2 n) ，性能略微逊色AVL树。
实际中使用的比较多的。
缺点：比较适合数据全部加载到内存中。但是数据量大到大量数据在磁盘，需要多次加载到磁盘中，每个节点的访问都要经过一次磁盘I/O， 效率是非常低下的。
解决：为了减少减少磁盘IO，减少树的高度，使树变得“矮胖”（多叉树）-> B树和B+树
数据库索引多使用 B树和B+树
应用场景：使用比较多
JAVA8 HashMap的底层实现，数组+ 链表/红黑树
其中元素个数小于8时是链表，元素个数大于8时是红黑树;如果已经是红黑树，元素个数减为6（不是8的原因：避免频繁转换）时退化为链表。
6. B树（又称B-tree树或B-树）
优点：减少I/O次数，多路查找树，B树在提高了磁盘IO性能
B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)
缺点：没有解决元素遍历的效率低下的问题，不利于遍历和范围查找。
解决：所有数据放在叶子节点节点上，组成一个双向链表，非叶子节点存储主键索引 -> B+树
场景：MongoDB默认存储引擎使用了B树。
说明：读多写少且对遍历数据的需求不强，B 树与 LSM 树在该场景下相比B+树有更大的优势
7. B+树：B树的改进版
优点：只有叶节点会存储数据
场景：MySQL的InnoDB存储引擎使用了B+树
注意：B树和B+树的查询效率肯定不如红黑树，但是红黑树内存中才有优势。
8. B*树：B+树的改进版
9. 跳表：
链表加多级索引的结构
可以看成是链表实现二分查找，基于范围查询比红黑树效率高。
理论上经过改造后可以代替B+树成为数据库存储索引设计。
10. LSM树
无论是 B 树还是 B+ 树，向这些数据结构组成的索引文件中写入记录都需要执行的磁盘随机写。
LSM 树的优化逻辑就是牺牲部分的读性能，将随机写转换成顺序写以优化数据的写入。
a.在不限制写入的情况下；
LSM 树的写入性能是 B 树的 1.5 ~ 2 倍；
LSM 树的读取性能是 B 树的 1/6 ~ 1/3；
b.在限制写入的情况下；
LSM 树的写入性能与 B 树的性能基本持平；
LSM 树的读取性能是 B 树的 1/4 ~ 1/2；
场景：MongoDB默认存储引擎使用了B树，备用引擎是LSM树。
Hbase中存储设计使用了LSM树。
问题1：Redis为什么采用跳表而不是红黑树？
（1）插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
（2）跳表插入和删除更快、操作更简单。平衡树的插入和删除操作可能引发子树的旋转调转，逻辑复杂。
（3）算法实现简单
（4）跳表更加灵活，他可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
问题2：为什么MongoDB使用B树，而mysql使用B+树？
（1）B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。
B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)
MongoDB追求单条记录的效率发挥到极致，而不重视范围查找（虽然也支持，但是性能不如B+树）。
（2）B+树擅长范围查找，而B树不擅长。（最重要的原因）
B+树查询时间复杂度固定为logn，性能稳定。
MySQL追求稳定和范围查询。
（3）B+树中非叶子节点不存储关键字，利于加载到内存。
问题3：B+树、B树对比？
（1）B+树的所有数据都在叶子节点中，非叶子节点不存储数据，只是索引。
B树中的节点存储数据；
（2）B+树叶子节点之间是双向链表。
B 树中的叶子节点并不需要链表来串联。
（3）B+树更加适合范围查询、且查询性能更稳定