索引结构
索引结构
索引结构分类
支持情况
BST 二叉查找树
缺点：
- 不平衡，顺序插入时，形成链表（退化），查询性能大大降低。
- 大数据量情况下，层级较深，检索速度慢。
AVL 平衡二叉树
优点：始终保持平衡，操作都是稳定logn复杂度
缺点：旋转耗时
RBT 红黑树
性质 ：
结点是红色或黑色。
根结点是黑色。
所有叶子都是黑色。
（叶子是 NIL 结点）
每个红色结点的两个子结点都是黑色。
（从每个叶子到根的所有路径上不能有两个连续的红色结点）
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
优点：相比于 AVL 树，无需频繁旋转，更加省时
缺点：大数据量情况下，层级仍然较深，检索速度慢
B-Tree
多路平衡查找树
B树也称B-树（其中-不是减号），是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，B树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。
定义B树最重要的概念是阶数(Order),对于一颗m阶B树，需要满足以下条件：
以一颗最大度数(max-degree)为 5 阶的 b-tree 为例(每个节点最多存储 4 个 key，5 个指针)，中间元素向上分裂。
缺点：
- 每个节点均存数据，可以记录的子树有限，层数相对还是较深。
B+Tree
数据存储只在叶子结点中
非叶结点只起索引的作用，叶子结点形成一个单向链表
中间元素向上分裂，同时会保留在右子树里
MySQL 中对 B+Tree 进行了优化，叶子层单向指针变成双向，更加便于范围查询
一页 16k，上面层，每一个节点都只存 key 和指针，就可以存很多很多
InnoDB 主键索引 B+tree 高度估算：
一个页 16k，一层大概有 1171 个指针
2 层是 2w 数据，即使存 2kw 多的数据，也只有 3 层，B+树一般是2-4层
优点：
更少的 IO 次数：B+树的非叶节点只包含键，而不包含真实数据，因此每个节点存储的记录个数比 B 数多很多（即阶 m 更大），因此 B+树的高度更低，访问时所需要的 IO 次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
更适于范围查询：
- B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；
- B+树的范围查询，只需要对链表进行遍历即可。
更稳定的查询效率：
- B 树的查询时间复杂度在 1 到树高之间(分别对应记录在根节点和叶节点)
- B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。
劣势：由于键会重复出现，因此会占用更多的空间。但是与带来的性能优势相比，空间劣势往往可以接受，因此 B+树的在数据库中的使用比 B 树更加广泛。
Hash 索引
特点：冲突时，就用链表存储
优点：查询效率高，O1
缺点：只支持等值匹配，不支持范围索引和排序操作
只有 Memory 引擎支持
而 InnoDB 中具有自适应 Hash 索引（内存结构 Buffer Pool），满足条件时，自动设计为 Hash
为什么采用 B+ 树
相对于二叉树，层级更少，搜索效率高；
相对于 B-tree，
- 无论是叶子节点还是非叶子节点，都会存数据，这样导致一页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能增加树的高度，导致性能降低；
而且 B+搜索效率稳定，而且最下层有双向链表，便于范围搜索和排序
相比于 Hash，B+支持范围索引（模糊查询）和排序操作