常见的索引模型

1、哈希表

  • 哈希表是key-value存储数据的结构
  • 当出现hash冲突的情况，就会拉出一个链表
  • 优缺点：
    • 优点：
      • key是无序的（适合等值查询的场景），所以插入快速
    • 缺点：
      • 区间查询比较慢

  • 场景：Memcached以及其他一些NoSQL场景

    2、有序数组

  • 数组有序排列

  • 优缺点：
    • 优点：
      • 查询：可通过二分法快速得到，时间复杂度为O(log N)
      • 因为是有序的，所以区间查找比较快速
    • 缺点：
      • 插入比较慢，往中间插入一个数，必须得挪动后面的记录

  • 场景：适合静态存储引擎，比如保存的是2017年某个城市的人口信息， 这类不会修改的数据

    3、搜索树

  • 二叉树：左子节点<父节点<右子节点

  • N叉树：每个节点有多个子节点，子节点的大小从左到右依次递增
  • 实际上大多数的数据存储并不使用二叉树，原因是：索引不止存在内存上，还要写到磁盘上。你可以想象一下一棵100万节点的平衡二叉树，树高20。一次查询可能需要访问20个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要10 ms左右的寻址时间。也就是说，对于一个100万行的表，如果使用二叉树来存储，单独访问一个行可能需要20个10 ms的时间，这个查询可真够慢的。为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N叉”树。这里，“N叉”树中的“N”取决于数据块的大小

  • 以InnoDB一个整数字段索引为例，N大概为1200，树高为4时，可以存17亿个数，考虑到第一层和第二层大概率都在内存中，那么磁盘访问的次数就很少了

    InnoDB 的索引模型

    在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB使用了B+树索引模型，所以数据都是存储在B+树中的。
    每一个索引在InnoDB里面对应一棵B+树。
    假设，我们有一个主键列为ID的表，表中有字段k，并且在k上有索引。
    这个表的建表语句是：

    1. mysql> create table T(
    2. id int primary key, 
    3. k int not null, 
    4. name varchar(16),
    5. index (k))engine=InnoDB;

    表中R1~R5的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示例示意图如下。
    索引 - 图1
    图4 InnoDB的索引组织结构
    从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。
    主键索引的叶子节点存的是整行数据。在InnoDB里，主键索引也被称为聚簇索引（clustered index）。
    非主键索引的叶子节点内容是主键的值。在InnoDB里，非主键索引也被称为二级索引（secondary index）。
    根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？

  • 如果语句是select from T where ID=500，即主键查询方式，*则只需要搜索ID这棵B+树；

  • 如果语句是select from T where k=5，即*普通索引查询方式，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

索引维护

B+树为了维护索引有序性，在插入新值的时候需要做必要的维护。以上面这个图为例，如果插入新的行ID值为700，则只需要在R5的记录后面插入一个新记录。如果新插入的ID值为400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。
而更糟的情况是，如果R5所在的数据页已经满了，根据B+树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%。
当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。
基于上面的索引维护过程说明，我们来讨论一个案例：

你可能在一些建表规范里面见到过类似的描述，要求建表语句里一定要有自增主键。当然事无绝对，我们来分析一下哪些场景下应该使用自增主键，而哪些场景下不应该。

自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。
插入新记录的时候可以不指定ID的值，系统会获取当前ID最大值加1作为下一条记录的ID值。
也就是说，自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
除了考虑性能外，我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？
由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约20个字节，而如果用整型做主键，则只要4个字节，如果是长整型（bigint）则是8个字节。
显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。
有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：

  1. 只有一个索引；
  2. 该索引必须是唯一索引。

你一定看出来了，这就是典型的KV场景。
由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。
这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

覆盖索引

  1. 首先我们创建一张表 `` CREATE TABLEstudent(idint(11) NOT NULL AUTO_INCREMENT COMMENT '自增主键',namevarchar(32) COLLATE utf8_bin NOT NULL COMMENT '名称',ageint(3) unsigned NOT NULL DEFAULT '1' COMMENT '年龄', PRIMARY KEY (id), KEYI_name(name`) ) ENGINE=InnoDB;

INSERT INTO student (name, age) VALUES(“小赵”, 10),(“小王”, 11),(“小李”, 12),(“小陈”, 13); ``` 2、这里我们设置了主键为自增，那么此时数据库里数据为
索引 - 图2
3、每一个索引在 InnoDB 里面对应一棵B+树，那么此时就存着两棵B+树。

索引 - 图3
4、我们执行 SELECT age FROM student WHERE name = ‘小李’；
5、具体流程：

  • name索引树查到id=03
  • 主键索引树查到03这条记录
  • 从查询的记录中返回age字段的值
  • 整个过程查询存在一次回表，查询了两个B+树

6、如果这个根据name查询age的场景非常的多，那么可以如下优化：

  • 删除原来的name索引 ：ALTER TABLE student DROP INDEX I_name;
  • 添加一个name，age的索引：ALTER TABLE student ADD INDEX I_name_age(name, age);

索引 - 图4
7、再次查询 SELECT age FROM student WHERE name = ‘小李’；
8、具体流程如下：

  • name，age联合索引树上查找到name时小李的节点
  • 节点中包含了age的信息，直接返回age

9、覆盖索引减少了回表的次数，合理的设计可以显著的提升性能
10、如何确定使用了覆盖索引？

  • 当发起一个索引覆盖查询时，在explain的extra列可以看到using index的信息

索引 - 图5
这里我们很清楚的看到Extra中Using index表明我们成功使用了覆盖索引

最左前缀原则

  • 只要满足最左前缀（联合索引的最左N个字段，也可以是字符串索引的最左N个字符)。所以在建立联合索引的时候，我们要根据具体的业务场景来调整索引内部字段的顺序，这样可以减少不必要索引的维护。

  • 假如存在索引（a,b,c），那么他的最左前缀有（a）、(a,b)、(a,b,c)这些列的查询都会启用索引查询

    索引下推

    索引条件下推优化（Index Condition Pushdown (ICP) ）是MySQL5.6添加的，用于优化数据查询。

  • 不使用索引条件下推优化时存储引擎通过索引检索到数据，然后返回给MySQL服务器，服务器然后判断数据是否符合条件。

  • 当使用索引条件下推优化时，如果存在某些被索引的列的判断条件时，MySQL服务器将这一部分判断条件传递给存储引擎，然后由存储引擎通过判断索引是否符合MySQL服务器传递的条件，只有当索引符合条件时才会将数据检索出来返回给MySQL服务器。

**索引条件下推优化可以减少存储引擎查询基础表的次数，也可以减少MySQL服务器从存储引擎接收数据的次数。 **