索引是用来提高数据库查询效率的.
其本质是数据结构, 通过选择不同的数据结构和算法, 来提高数据库的查询效率.
学习目标
MySQL04, MySQL05
- 常见索引模型及其适用场景
- InnoDB 的索引模型
- 索引维护以及主键索引的选择依据
- 常用索引优化方案: 覆盖索引, 最左前缀原则, 索引下推
常见索引模型
常见的索引数据结构有: 哈希表, 数组, 搜索树, 跳表以及 LSM 数. 这里只介绍了前三种.
哈希表
- 查询速度快, 添加删除也快
- 在不出现哈希碰撞的情况下, 时间复杂度均为 O(1); 出现哈希碰撞后, 一般适用链表保存数据, 链表查询时间复杂度为 O(n);
- 虽然查询和增删数据都比较快, 但是 key 值是没有排序的, 区间范围查询需要遍历整个数据库, 时间复杂度较高, 为 O(n);
- 适合作为 K-V 型数据库, 且没有太多重复哈希值的情况;
有序数组
- 查询速度快, 数组具备随机访问能力;
- 当数组是有序的时候, 查询时间复杂度为 O(log(n)), 且只支持区间查询;
- 但是添加数据时, 需要进行数据搬移, 时间复杂度较高, 为 O(n);
- 数组适合用来做静态数据分析;
搜索树
- 数据可以是有序的, 支持区间查询;
- 查询时间复杂度为 O(log(n)), 增删记录的时间复杂也为 O(log(n));
- 为保证查询性能, 尽可能少地随机访问磁盘, 降低树的高度, 一般采用 N 叉数, 而不是二叉树;
- 适用常见数据, MySQL 的 InnoDB 采用 B+ 树;
InnoDB 的索引模型
MySQL 的 InnoDB 采用 B+ 树作为索引.
表数据都是根据索引顺序进行组织, 索引分为主键索引(聚簇索引)和普通索引(二级索引);
- 聚簇索引上根据主键值存储该行记录的所有数据;
- 二级索引上根据索引值存储该行的主键值;
回表
当根据普通索引进行条件查询时, 如果该查询返回的某个字段在该普通索引上并不存在, 数据库这需要根据查询的主键重新去主键索引上查询对应数据.
这个过程成为回表.
由于该过程对两颗索引树进行查询, 会降低查询索引效率, 所以尽量根据主键进行数据查询, 以减少回表.
索引维护
索引可以提高查询效率, 但同时在添加数据的时候需要索引进行维护.
最好选用递增的主键索引
当添加数据的时候, 非递增主键索引会导致索引树的重排序, 甚至是页分裂, 从而降低数据库性能;
最好选用长度较短的主键
从存储的角度, 如果主键过长, 在建立二级索引的时候, 会使得索引存储空间较大.
索引优化方案
覆盖索引
当使用普通索引进行查询时, 可以用来避免回表来提高查询效率;
索引最左前缀原则
当建立了联合索引 (a, b) 时, 可以相当于建立了两颗索引树;
- (a, b) 联合索引;
- (a) 单索引, 该索引依据索引最左前缀原则, 可以用来提高查询效率;
最左前缀可以是索引最左边的 n 个字段, 也可以是字符串索引的左边 n 个字符.
索引下推
索引下推优化是在 MySQL 5.6 中引入的, 当普通索引中包含约束查询条件的字段时, 会使用该字段进行过滤不满足条件的记录, 减少回表次数.
当建立了联合索引 (a, b) 时, 一条查询语句的查询条件包括但不限于 a, b 两个字段时, a 索引将会被使用来优化查询效率, 同时数据库也会根据 b 的判断条件在联合索引树去过滤不符合条件的数据, 最后对满足条件的记录进行回表条件查询.