详解索引数据结构和类型

1. 介绍索引的基本概念和数据结构

2. 详解Explain字段的用户

3. 介绍常见的索引类型

索引概述及数据结构

索引是帮助MySQL高效获取数据的数据结构，提高查询效率。 就像字典的目录一样，查询汉字会先在目录查找，不是盲目全书查询

索引的优缺点：

1. 提高查询效率，减少IO成本
2. 索引会占用一定空间，同时对表数据做DML操作，结构也会实时更新

索引常见的数据结构：

1. Hash Table，特点如下：

• Key-Value存储结构，查询的复杂度为O(1)
• 无法用于范围查询、模糊、排序情景
• 当数据量过大时，容易发生Hash冲突

1. 有序数组，特点如下：

• 通过二分法，时间复杂度为（O(logN)）查找，适用于等值，范围查找
• 更新代价大，增加和删除数据需要变更整个数组，仅使用于静态存储（不会再修改的数据），

1. 二叉树，特点如下：

• 查找、删除的效率的时间复杂度均为O(logN)
• 当数据量过大时，二叉树的高度过深，不易于查找
• 在面对特殊的数据类型时，二叉树会退化为“链表”

1. B树，特点如下：

• 相较于二叉树，层级较少，查找效率高
• B树的非叶子节点也会保存数据，指针和数据共同保存在同一节点中，查找数据的效率不稳定
• 插入和删除数据需要频繁变更树的结构，结构不稳定

1. B+树（最常见），特点如下：

• 数据均保存在叶子节点，保证了搜索的稳定性，（每次查找都会从父节点到叶子节点结束）
• 插入和删除数据操作均放在叶子节点，维护了树结构的稳定性
• 叶子节点同时还维护了一条双向链表，提高范围查询的效率

B+树的高度优势计算

MySQL规定，一页的默认大小为16K，假设一张表的主键为bigint，长度为8B，每有一个主键便存在一个大小为6B的指针。即B+树中，一页可存放的数据的极限大小为：

N ≈ 16×1024/(6+8) = 1200

假设B+树的高度为3，且表中存储的数据一行大小为1K，一颗高度为3的B+树，可存储的数据量为：

Count ≈ 1200×1200×(16/1) = 23040000

ps: 父节点可存放1200个指针，可指向1200张数据页，1200张数据页可存放1200×1200个指针，每指向的一个叶子节点中，可存放16条数据

对于二叉树来说，若想拥有2300W个节点，则高度h的计算如下：

h ≈ log2(23040000) + 1 = 25

对比于B+树，需要多进行22次IO！！！

---

Explain字段详解

通过创建索引的手段来优化我们的查询sql语句后，通过explain便可详细分析我们的sql好坏，Mysql官方对Explain的作用描述如下：

- When EXPLAIN is used with an explainable statement, MySQL displays information from the optimizer about the statement execution plan. That is, MySQL explains how it would process the statement, including information about how tables are joined and in which order.

explain能解释MySQL是如何处理sql语句，以及表的加载顺序，连接情况，以及索引的使用情况，是sql优化的重要工具

执行一条explain语句，重要字段，分析如下：

• id（重要）, 表明执行顺序。id相同，由上到下执行；id不同，从大到小执行

• select_type, 表明select的查询类型，有SIMPLE，PRIMARY，UNION，SUBQUERY等

• table, 显示数据来自于哪张表

• type（重要）, 直接表明sql语句的性能是否高效，性能由好到坏排序为：

  • system, 针对系统表查询，且表数据只有一行，几乎不会出现
  • const, 命中主键索引或唯一索引的等值查询，只会返回一行数据，效率极高
  • eq_ref, 在多表查询情况下，命中主键索引或唯一索引的等值连接查询
  • ref, 命中普通索引，返回匹配某个单独值的所有数据
  • fulltext, 全文索引，仅在MyISam引擎中才会用到
  • ref_or_null, ref的特例，在ref的查询基础上加上 or column = null
  • range, 范围查询，命中索引列中的between and, IN, like, >, <, is null
  • index, 全盘扫描索引树，性能差，但优于全表扫描，一般用于count统计
  • ALL, 全表扫描，未命中索引，性能最差

• possible keys（重要）, 该条sql语句可能会命中的索引

• key（重要）, 该条sql语句实际命中的索引

• Key_len（重要）, 命中的索引长度（索引所用到的字节数），在联合索引中有大用处

  • 索引为int类型时，占用4个字节；bigint类型，占用8个字节；date类型，占用3个字节；datetime类型，占用4个字节
  • 索引为char类型时，char(n)占用 m × n个字节，n为字符个数，m为1个字符占用的字节大小。因此，m视字段的字符集变动，utf8对应的m为3，utf8mb4对应的m为4，gbk对应的m为2
  • 索引为varchar类型时，varchar(n)占用m × n + 2个字节，2个字节记录varchar的实际长度，如果该varchar字段允许为null，所占用的字节数还要多1

• row, MySQL预估要扫描的行数，这个不一定准

• Extra（重要）, 执行sql产生的额外信息

  • Using index, 运用到了覆盖索引，只用到索引的信息，性能高
  • Using Where, MySQL的Server层在引擎层检索后再进行的过滤
  • Using filesort, 排序时出现，表明用到了额外内存来排序
  • Using temporary, 创建临时表来查询，常发生于无索引情况
  • Using index condition, 出现索引下推

---

索引的分类

索引的种类五花八门，有主键索引、唯一索引、普通索引、联合索引等，不同索引的特点如下展开

1. 主键索引，又称聚簇索引 or 聚集索引

• 针对表中主键创建的索引，一张表中只能有一个
• 若表没有主键，选定第一个唯一字段作为主键索引
• 若都没有，InnoDB存在一隐藏列，rowID, 以rowID字段为索引
• 主键索引树中，叶子节点存储的是完整的行数据

1. 唯一索引（二级索引）

• 针对唯一索引创建的索引，一张表中可以存在多个
• 二级索引树的叶子节点存储的是主键值

1. 普通索引（二级索引）

• 针对普通索引创建的索引，一张表中可以存在多个

1. 联合索引

• 多个字段所组成的索引，需要遵循最左匹配原则

主键索引和二级索引的区别

对比——主键索引和普通索引

树的叶子节点存储的数据不同，主键索引为行数据，普通索引则为主键值

容易产生回表现象

假设存在一张表T，主键为ID，普通索引列为s, 非索引列为k，对于如下两条sql语句：

                        select * from T where ID = 1;
                        select * from T where s = 1;

*为全局匹配，会被MySQL自动替换成 ID, s, k字段

对于sql(1), 为主键查询，只需要在主键索引树的叶子节点找到数据即可（叶子节点包含了完整数据）

对于sql(2), 为普通索引查询，需要先走s索引索引树，在叶子节点找到对应的主键，（此刻无法获取k的值）, 因此需要再通过主键索引树查询到对应的k值。该行为即为回表

可通过覆盖索引，来避免回表现象

若sql语句变为：

                        select ID, s from T where ID = 1;

`

对于该sql, 依旧为普通索引查询，需要先走s索引索引树，在叶子节点找到对应的主键，（此刻无法获取k的值）, 但不需要找到k了，因此不需要再去主键索引树查找

通过explain来验证，如下

Extra中出现Using Index字段，表明用到了索引中的信息，即覆盖索引

细解最左匹配原则

对于联合索引，必须要遵循最左匹配原则。规则为：建立的联合索引，需要从左到右去依次匹配，若中间*，后续索引直接失效

假设存在一张表user，字符编码为utf8mb4，存在id, name(varchar(32)), age(int(11)), male(tinyint(1)), grade字段，建立name-age-male联合索引，对于如下sql：

            select * from user where name like "张%" and age = 10 and male = 1;
            select * from user where name like "张%" and male = 1;
            select * from user where male = 1;
            select * from user where name like "张%";

对于sql(1), 根据最左匹配原则，name, age, male会依次命中所建立的name-age-male联合索引, 依据如下：

通过key_len可知，走了name-age-male联合索引，key_len = (32×4+3)+(4+1)+(1+1) = 138判断， +1是由于字段允许为NULL，需要多一个字节记录

对于sql(2), 根据最左匹配原则，name会命中所建立的联合索引中的name, 而没有命中age, 会直接导致后续的age和male失效,但仍然会走name索引, 依据如下：

通过key_len可知，走了name索引，根据key_len = 32×4+3 = 131判断

对于sql(3), 根据最左匹配原则，where查询条件中没有name，未命中联合索引中的最左字段，会导致索引直接失效，依据如下：

对于sql(4), 根据最左匹配原则，直接命中name，索引中的name会生效，但无后续查询条件，同sql(2), 会走name索引，如下：

总结：建立一条（a,b,c）联合索引，根据最左匹配原则，可以约等于建立了a, （a,b）, （a,b,c）索引，依次比较即可

联合索引产生的索引下推

基于上文的联合索引，对于sql(2),只匹配到了name，后续的索引便失效，而那些不符合最左匹配的部分会怎么样？

对于MySQL5.7以前的版本，sql(2)的执行顺序如下：

1. 把符合查询条件中name字段的主键ID全部搜集起来
2. 通过回表去做一一比较，不符合male字段的数据被剔除掉

这是一个比较笨的操作，因为完全能先对索引中包含的字段先做判断（联合索引中其实是包含male字段的），直接过滤掉不符合的数据，减小回表次数

从MySQL5.7开始，引入索引下推，即会直接过滤掉不符合的数据，再进行回表

• 无索引下推，将匹配到符合条件的name字段的主键ID，不经筛选直接去回表
• 有索引下推，将匹配到符合条件的name字段的主键ID，筛选出符合male=1的ID，再去回表

Extra中的Using index condition, 表明该sql在执行的过程中运用到索引下推

---

本篇ending~~~ 待续