红黑树，hash,b-,b+

1. 特殊的平衡二叉树，根节点黑色，叶子节点红色，每个叶子到根的节点不会出现俩个连续的红色节点，从任意一个节点到每个叶子节点的路径包含的相同的黑色节点
2. 近似平衡二叉树，排序问题是一个性能消耗点
3. 由于只有俩路，所以树高会很高，这点不好，太多的内存交互
4. 任何情况都不会退化成链表：红黑树叶子结点的定义是nil结点，nil结点没有数据，每个数据结点的子结点如果少于两个都用nil填满，也就是上图1-4都有另一个nil子结点，n有两个nil子结点，规则5说的到所有叶子的距离，不是到最靠下的数据结点的距离，而是到所有nil结点的距离。如下图，注意没画出来的俩个nil子节点

1. 根据key找value，性能极高
2. 仅支持 =  in但不支持范围查询
3. hash冲突问题
4. 具体结构如下图

1. 多路搜索树，树高就会降低
2. 数据和索引存在一起，所以索引分布在整棵树中，节点中数据从左到右递增，其性能等于在关键字集合中做一次二分查找，（二叉树适合有序数组查找）
3. 支持热点访问，在特定重复查询场景更高效，可以再内部节点存储键值和相关记录数据，让其更靠近树根

1. 多路搜索树，索引和数据分开存，也就是说一次磁盘io可以放更多的索引
2. 非叶子节点存放索引，叶子节点存放数据，叶子节点之间有指针，提高区间访问能力，可以理解成范围查询的实现

1. 聚集索引，又叫聚簇索引，主键索引
2. 非聚集索引，又叫二级索引，
3. 覆盖索引，利用二级索引查询完不需要回表既覆盖索引，或者说所查询字段都在查询的索引树上
4. 联合索引，一个索引包含多个字段，使用遵循最左前缀。至于为何遵守最左前缀看他的索引结构。
最左前缀使用时按顺序用索引字段，其他的遵守普通索引失效规则
5. 普通索引
6. 唯一索引

1. 避免页分裂，如果使用业务主键，且当前页写满了，那么就要申请新的数据页，并将上个数据页的部分数据移动到新的数据页上。