1. 索引概念知识

1.1 索引的作用

  • 索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。

    1.2 索引的结构

  • 哈希表、有序数组、搜索树、跳表、LSM树

    1.2.1 哈希表

  • 哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。

  • 缺点：

    • 在哈希函数在计算位置时，可能出现重复的情况
    • 只适合等值查询，范围查询效率非常低，需要遍历完成数据

      1.2.2 有序数组

  • 有序数组在等值查询和范围查询场景中的性能就都非常优秀。

  • 缺点：插入一个记录就必须得挪动后面所有的记录，成本太高。

  • 适用于：有序数组索引只适用于静态数据，不经常变的。

    1.2.3 二叉搜索树

  • 二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。

  • 查询一个值的时间复杂度是 O(log(N))。为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。
  • 实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。

    硬盘的最小存储单位是扇区，硬盘本身没有block的概念 文件系统若按照一个扇区一个扇区读数据速度太慢，所以有了block（块）的概念，是一个块一个块读取的，block才是文件存取的最小单位。扇区是对硬盘而言，块是对文件系统而言。

1.2.4 跳表

1.2.5 LSM 树

2. MySQL中的索引：InnoDB

  • 在 MySQL 中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。
  • Memory: MEMORY存储引擎支持HASH和BTREE索引。你可以通过添加一个如下所示的USING子句为给定的索引指定一个或另一个
  • InnoDB：B+树，聚簇索引叶子节点存储数据，非聚簇索引叶子节点存储主键ID;
  • MyISAM：B+树，和InnoDB不同的是，无论是主键还是非主键索引都是叶子节点存储数据在硬盘上的位置（innode(硬盘数据区的编号)）

image.png

下面主要是InnoDB。

2.1 InnoDB的索引的结构

  • InnoDB中默认使用主键作为默认的聚簇索引，如果不设置主键，innodb会给默认创建一个Rowid做主键。
  • InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。
  • 首先Innodb是聚集存储的，每条记录的数据以主键进行聚集存储，通过主键进行索引。如果没有定义主键，系统默认使用6个字符作为主键进行聚簇存储。而辅助索引（secondary indexes）中的每条记录包含主键（primary key）和索引字段。
  • 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

image.png

  • 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

image.png

2.2 InnoDB的索引的使用

InnoDB的索引包括：主键索引、普通索引、联合索引

2.2.1 查询

  • 在使用主键查询时：只需要从主键索引的树获取一次即可拿到数据
  • 在使用非主键索引时，需要做两次获取，第一次去查非主键索引树，找到主键，然后再去主键索引树去找一次。
    • 回表：从非主键索引回到主键索引树搜索的过程，我们称为回表
  • 覆盖索引： 如果执行的语句是select id from tableA where idx_a = ?，这时只需要查 id 的值，而 ID 的值已经在 idx_a 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。
    • 覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
    • 只会存在两种情况：一种是主键，一种是联合索引字段。
  • 最左前缀原则：不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。
    • 如何选择联合索引的顺序
    • 如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。
    • 如果（A,B）这样的索引不满足需求，需要B的单独索引，往往需要考虑占用空间大小，A大还是B大，遵从大在前原则，占用空间小的字段单独建立索引所需要的空间小。
  • 索引下推（MySQL5.6+）： 索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

image.png
select * from people where name like ‘张%’ and age = 10; 的索引下推

2.2.2 修改数据

  • 插入数据，如果当前数据页有空间，就会直接插入，但是如果当前数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能会受影响。除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。
  • 删除数据也会有问题：当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

  • 当索引页面的“page-full”百分比低于50％时，InnoDB会尝试将索引页与相邻页合并。 如果两个页面都接近50％已满，则在合并页面后很快就会发生页面拆分。 如果频繁发生此合并拆分行为，则可能会对性能产生负面影响。 为避免频繁的合并拆分，您可以降低MERGE_THRESHOLD值，以便InnoDB以较低的“page-full”百分比尝试页面合并。 以较低页面满百分比合并页面会在索引页面中留出更多空间，并有助于减少合并拆分行为。

    2.2.3 主键索引的选择

  • 如果你业务内有唯一且有序的字段，可以作为主键索引，你要怎么设置主键索引？比如身份证？

  • 先说结论：
    • 主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
    • 每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
    • 从性能和存储空间方面考量，自增主键往往是更合理的选择。
  • 有没有什么场景适合用业务字段直接做主键的呢？
    • 只有一个索引；
    • 该索引必须是唯一索引。

由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。

2.2.4 如何重建索引

  • 非主键索引 ```sql

alter table T drop index k; alter table T add index(k);

  2. - **主键索引重建**
  3. ```sql
  4. alter table T engine=InnoDB;

2.2.5 索引失效

  • 使用函数 如: where month(update_time) = 7;
  • 字段做计算：如：where age + 1 = 20;

https://dev.mysql.com/doc/refman/8.0/en/type-conversion.html

  • 隐适转换：如：where trace_id = 1234; 注意：trace_id 是varchar(32)
    • 字符编码转换 如：where a.trace_id = a.trace_id; 前表是utf8，后表是utf8mb4;
    • 字符串和数字做比较的话，是作为浮点数的比较进行的。
    • 按数据长度增加的方向，字符串编码转换的例子：a表的条件会加上 using utf8mb4
      • 常见错误：int -> long，decimal_a = int_b,
      • 日期和时间戳：在和常量比较时，会把常量转成时间戳。
  • 除开最左前缀外情况的，通配符匹配
  • 使用OR
  • 使用IN：两种情况：一个是IN(集合)的集合过大，一个是IN的所属字段的区分度过小，约30%。

2.2.6 索引优化

  • 做碎片整理，索引重建：alter table t engine=innodb
  • 条件覆盖 主键索引、组合索引
  • 使用组合索引的最左前缀、索引覆盖、索引下推来优化索引查询的。
  • 使用区分度大的字段做索引。
  • 组合索引通过最左前缀排序后，可以减少索引的数量。