2、索引

索引基本概念

索引：数据的目录 InnoDB 存储引擎在创建表时：

• 有主键，默认使用主键作为聚簇索引的 key
• 没有
  • 有不包含 NULL 的唯一列：选择第一个符合的列作为聚簇索引的 key
  • 没有：自动生成一个隐式自增 id 作为聚簇索引的 key。

分类

• 数据结构：
  • B+ 树索引
  • Hash 索引
  • Full-text 索引
• 物理存储 ：
  • 聚簇索引（主键索引）：
    • 叶子节点存放的实际的完整数据
    • 一张表只有一个
  • 二级索引（辅助索引）：
    • 叶子节点存放的是主键值
    • 一张表可以有多个
• 字段特性：
  • 主键索引
  • 唯一索引：插入数据时会直接读取磁盘数据，绕开 change buffer，否则报错，保证唯一性，非唯一索引直接把插入数据丢到 change buffer 就不管了。
  • 普通索引
  • 前缀索引：如通过关键字的前几个字符检索，但是一般通过 es 实现
• 字段个数：
  • 单列索引
  • 联合索引
    • 需要满足最左匹配原则，前一个字段相同的情况下，后一个字段才是有序的，后面的字段全局是无序的
    • 遇到 >、<时，会停止匹配

优缺点：

• 优点：
  • 加快检索速度，减少 IO 次数
  • 唯一索引可以保证该列数据的唯一性
• 缺点：
  • 创建和维护索引需要耗费资源
  • 索引需要物理存储，需要 耗费空济南

一些概念

• 回表：二级索引中不包含所需要的所有数据，需要通过二级索引获取主键值回到主键索引获取完整数据（通过二级索引过滤的情况下）
• 覆盖索引：二级索引中包含所需要的所有数据，不需要回表
• 索引下推 ：在联合索引遍历过程中，对联合索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数

建立索引时，需要考虑区分度，区分度就是某个字段 column 不同值的个数「除以」表的总行数，区分度小的可以放在联合索引的后面，不适合建立单列索引 这样可以在索引页排除大部分不符合的数据，减少 I/O

经常用于 where / group by / order by的字段适合建立索引，可以降低 I/O、加快排序 经常更新或者区分度低的字段不适合建立索引，前者维护成本高，后者增效少

有什么优化索引的方法？

这里说一下几种常见优化索引的方法：

• 前缀索引优化；
  • 用字符串的前几个字符建立索引，提高效率
  • order by 无法使用
  • 无法作为为覆盖索引（缺少全部数据）
• 覆盖索引优化；
  • 包括查询需要的所有字段，可以避免回表
• 主键索引最好是自增的；
  • 否则插入容易造成页分裂，造成内存碎片，且降低查询效率
• 索引设置为 NOT NULL
  • 1、增加额外的 NULL 值列表
  • 计算等比较复杂
• 防止索引失效；
• 避免频繁更新的字段
  • 索引树会不断的进行调整
• 限制索引数量
  • 降低插入和更新的效率
  • MySQL 优化器评估执行计划效率更低
• 尽可能建立联合索引
• 避免冗余索引
  • 比如 联合索引可以覆盖的索引 或者 不会用到的索引
• 频繁用于查询（需求字段或者过滤字段）、排序、外连接的字段

索引结构选择

好的索引数据结构

• 能在尽可能少的磁盘的 I/O 操作中完成查询工作；
• 要能高效地查询某一个记录，也要能高效地执行范围查找； 差别
• 二分查找树：
  • 一个节点最多 2 个子节点
  • 所以时间复杂度最好是O(logN)
  • 极端情况会出现O(N)
  • 平衡二叉查找树（AVL 树）可以避免极端情况
• Hash：
  • 非常适合做等值查询，O(1) 时间复杂度
  • 但是非常不适合做范围查找，无序
• 跳表：二分查找，比较高，和二分查找树类似
  • redis 用跳表因为不需要考虑磁盘 IO，而跳表没有旋转平衡的开销，更快一些
• B 树：
  • 一个节点可以有 M 个节点 (M>2)，是一个多叉树
  • 其非叶子节点也存放数据，所以相对 B+树 来说，层数更高
  • 会使用中序遍历进行范围查找，会设计多个节点的磁盘 I/O，整体速度较低
• B+ 树：
  • 整体结构和 B 树类似
  • 只有叶子节点存放数据，非叶子节点存放索引，层数可以更低，更加的矮胖
  • 叶子节点之间有链表连接，可以更高的进行范围查找
• B 和 B+ 树
  • 单体查找：B 树可能一次就找到了（非叶子节点也是数据），但是波动很大
  • 插入和删除：
    • B+ 树在删除时，不需要变动整体结构，一般只需要删除叶子节点即可
    • B 树在删除时，因为可能删除非叶子节点，就导致树的复杂变化
    • 插入类似，因此，B+ 树的插入/删除效率更高
  • 范围查找：
    • B+ 树的叶子节点通过链表进行连接，只要找到第一个符合的数据，一直通过链表往后查找即可，不需要回到非叶子节点了。
    • B 树需要不断的回到非叶子节点。
• Innodb 使用的 B+ 树，使用双向链表进行连接，左右遍历都方便，更加适合不同场景的范围查找

单表数据

MySQL 为了提高性能，会将表的索引装载到内存中，在 InnoDB buffer size 足够的情况下，其能完成全加载进内存，查询不会有问题。

但是，当单表数据库到达某个量级的上限时，导致内存无法存储其索引，使得之后的 SQL 查询会产生磁盘 IO，从而导致性能下降，所以增加硬件配置（比如把内存当磁盘使），可能会带来立竿见影的性能提升哈。

• 索引结构不会影响单表最大行数，2000W 也只是推荐值，超过了这个值可能会导致 B + 树层级更高，影响查询性能。

索引失效

• 使用左模糊匹配，即 like %xx 或者 like %xx%这两种
  • 索引的排序失效
• 当我们在查询条件中对索引列进行变换。
  • 1、使用函数，可以使用函数索引避免失效
  • 2、进行表达式计算
  • 3、进行隐式类型转换，MySQL 在遇到字符串和数字比较的时候
  • 会把字符串转为数字，然后再进行比较。如果字符串是索引列，会失效。
• 联合索引要能正确使用需要遵循最左匹配原则，不需要 where 里面按照最左匹配，因为优化器会优化排序
• 在 WHERE 子句中，OR 中有非索引列，即使另一个是索引也失效。

从这个思考题我们知道了，使用左模糊匹配（like "%xx"）并不一定会走全表扫描，关键还是看数据表中的字段。

如果数据库表中的字段只有主键 + 二级索引，那么即使使用了左模糊匹配，也不会走全表扫描（type=all），而是走全扫描二级索引树 (type=index)。

再说一个相似，我们都知道联合索引要遵循最左匹配才能走索引，但是如果数据库表中的字段都是索引的话，即使查询过程中，没有遵循最左匹配原则，也是走全扫描二级索引树 (type=index)，比如下图：

count()

一个聚合函数:统计符合查询条件（where）的记录中，指定参数不为 NULL 的记录有多少个

• 参数可以是字段名，也可以是其他任意表达式
• 如果是 *或者 1 这种常量，那么直接统计行号，相当于用常量填充每一列，一定不为 NULL
  • * 和 1 这种基本一致，但是可能不同的（InnoDB是相同的）
• 如果是字段，那么需要逐行读取该列的值，因为有 NULL 值，不能被统计
  • 主键索引 >= 二级索引 >= 普通字段
  • 因为主键索引可以选择一个最小的索引树（二级索引），那么每次读取的内容最少，IO 次数少
  • 如果是非 null 字段，不会读取行内容，等于少一个 if 判断
• 如果带了 where 条件，会尽量走 where 的字段
• 如果是 MyISAM 引擎，会存一个总行数的值，所以不加 where 的话，只需要 O(1)时间复杂度统计行数
  • InnoDB 因为支持事务，每个事务行数不同，所以使用遍历方式统计
  • 如果加了 where，MyISAM 也会进行扫描
• 但是如果表很大，count() 还是很耗时
  • 如果不是需要很准确的，可以通过 explain select count(*) from t_order
  • 如果需要准确值，可以通过另外一个表进行记录，但是需要额外维护
  • 通过消费 binlog 将数据导入 hive，在 hive 中做查询

问题

高并发场景下，唯一索引偶尔出现插入重复数据问题

原因

• 1、如果唯一索引允许为 NULL，数据库会将多个 NULL 视为不重复
  • 字段禁止为 NULL
• 2、唯一索引是联合字段，插入缺失一些字段（应该不算重复）
• 3、先查询后插入，有滞后性，错误未捕获而不回滚可能会导致重复
• 4、隔离级别低于可重复读，两个事务并发插入，可能引发冲突
  • INSERT ... ON DUPLICATE KEY UPDATE 原子操作避免 3、4
• 5、分库分表场景下，唯一索引只作用于单表，不同表会有重复数据
  • 分布式锁