数据结构
普通查找树
- 满足条件：每个左节点都比父节点小，每个右节点都比父节点大；
- 链表可以看成是退化的无左节点查找树
平衡二叉树 AVL
- 一颗查找树
- 非叶子节点子节点数不超过2
- 树左右层级高度差不超过1
- 没有重复节点
- 应用场景中对**
插入删除不频繁，只是对查找要求较高**，那么AVL还是较优于红黑树
红黑树
特性：
- 每个节点非红即黑；
- 根节点和叶节点(NULL节点)是黑的；
- 如果一个节点是红的,那么它的两儿子都是黑的；
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
复杂度：红黑树的查找、插入、删除的时间复杂度最坏为O(log n)
五个性质的结果：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。
应用场景：
- IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查
- Linux进程虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
- Java中TreeMap的实现
AVL树 与 红黑树
- 对于查找操作，复杂度都是O(logN)，但是AVL树时**
严格**的平衡树，查找时效率优于红黑树 - 对于插入操作，AVL树和红黑树**
都最多两次旋转**即可再平衡 - 对于删除操作，AVL树**
最坏情况需要维护节点到根的平衡性，复杂度达到O(logN)，红黑树最多只需3次旋转**，只需要O(1)的复杂度 - AVL树较红黑更为平衡，因此在插入和删除**
更容易引起再平衡，在大量数据需要插入或者删除时，AVL树需要再平衡的频率会更高**。
B树(B-tree)/平衡**多路**查找树
- 所有节点关键字是按递增次序排列，并遵循左小右大原则；
- 子节点数: 对于M叉树，非叶子节点的子节点数量是1~M。至少是二叉树
- 每个节点关键字数：
B树与B+树
- b树所有节点都带数据，B+树只有叶子节点有数据。b+树非叶子节点可以存放更多的关键字，相反b树获取数据不需要访问叶子节点
- b+树所有叶子节点都通过指针连接，b树不连接。需要扫描一次数据时，只需根据叶子节点连接扫描即可，不需要遍历整棵树
红黑树与其他平衡树
- 平衡树每次加入数据都可能需要rebalance，红黑树不需要，只需要经过多次旋转即可重新符合红黑树规则。这个次数远小于平衡树
- 能用平衡树的地方，就可以用红黑树。用红黑树之后，读取略逊于AVL，维护强于AVL。
- 红黑树多用在内部排序，即全放在内存中的，适合用于内存型数据结构。
- B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构。
为什么b+磁盘友好？
- 磁盘读写代价更低。树的非叶子结点里面没有数据，这样索引比较小，可以降低io的次数。
- 查询效率更加稳定。只有叶子节点保存关键字索引，所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
- 遍历所有的数据更方便。B+树只要遍历叶子节点就可以实现整棵树的遍历，而其他的树形结构 要中序遍历才可以访问所有的数据。
二叉搜索树和平衡二叉树有什么关系，强平衡二叉树（AVL 树）和弱平衡二叉树红黑树）有什么区别
- 二叉搜索树必须满足左小右大的特性；平衡二叉树是在二叉树基础上添加了平衡特性：所有左右子树高度差不超过1；
- avl树是强平衡二叉树，在数据查找上比红黑树效果好；红黑树是弱平衡二叉树，平衡特性靠节点颜色和规则保持，对插入和删除的效果比较好；
B 树和 B+树的区别，为什么 MySQL 要使用 B+树
- B树所有节点保存数据，B+树只有叶子节点保存数据；B+树所有字节点有指针连接串起来。
- 原因：B+树非叶子节点只有关键字，节点可以保存更多关键字，降低树的高度；叶子节点才有索引，查找性能稳定；范围查找直接范叶子节点链表即可；