数据库技术
mysql

mysql-innodb的索引

数据库索引是数据库管理系统中一个排序的数据结构，以协助快速查询更新数据库表中数据

索引类型：normal普通索引、unique唯一索引、全文索引

  • 普通索引：也叫非唯一索引，没有任何的限制
  • 唯一索引：要求索引的键值不能重复，另外，主键索引是一种特殊的唯一索引，比唯一索引多了一条限制。即键值不能为null
  • 全文索引：针对较大的数据，比如我么存放的是消息内容没有几KB的数据这种情况。如果要解决like查询效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如：char、varchar、text

1、索引用什么数据结构？

索引是用来加快记录的查找速度，但是在查询记录之前是不是需要先定位到记录索引呢。因此为了加快索引的查找速度，可以考虑将索引按照顺序进行存放，然后使用二分查找法查找。

既然是按照顺序存放，那么可以考虑的数据结构就有以下几种：

1.1 有序列表

有序列表查询没有问题，但是插如记录的时候需要同步插入记录的索引，有序列表的插入需要移动大量的数据，所以有序列表排除。

1.2 单链表

单链表插入没有问题，查找的时候需要重头开始遍历，不能使用二分查找，因此排除

1.3 二叉树查找树

既然单链表不能二分查找，那么就用支持二分查找的二叉树，但是极端情况下（插入顺序有序），二叉链表回退化成单链表，排除

1.4 AVL树-平衡二叉树

平衡二叉树解决了二叉树左右子树高度相差太大的极端问题，但是它也存在其他问题：

  • 二叉树每个节点只能存放一条索引记录，当数据量很大的时候，树会长的很高，查询效率降低
  • 平衡二叉树的平衡操作开销比较大
  • 索引数据是以节点为单位存放到磁盘上，磁盘的最小单位是一页16KB，使用二叉树意味着每页磁盘页只能存放一条索引，浪费巨大显然不合理。
1.5 多路平衡查找树 B Tree

跟 AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。

它有一个特点：分叉数（路数）永远比关键字数多 1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。

B Tree 的查找规则是什么样的呢？

比如我们要在这张表里面查找 15。

因为 15 小于 17，走左边。

因为 15 大于 12，走右边。

在磁盘块 7 里面就找到了 15，只用了 3 次 IO。

B树的缺点：范围查询时性能捉急：因为需要中序遍历

1.6 B+树（加强版多路平衡查找树）

B Tree 的效率已经很高了，为什么 MySQL 还要对 B Tree 进行改良，最终使用了 B+Tree 呢？

总体上来说，这个 B +树的改良版本解决的问题比 B Tree 更全面。 我们来看一下 InnoDB 里面的 B+树的存储结构：

的 B+Tree 有几个特点：

1、它的关键字的数量是跟路数相等的；

2、B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。查找到索引键值不会直接返回，会到最后一层的叶子节点。比如我们搜索 id=28，虽然在第一层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜索，一直到叶子节点。

我们举个例子：假设一条记录是 1K，一个叶子节点（一页）可以存储 16 条记录。

非叶子节点可以存储多少个指针？

假设主键为自增的bigint类型，占8字节，B+树指针为6字节，中间节点一页能存放的索引数量是16KB/14B=1170，

即至少有1170页即18MB存放行数据。而实际上这个这个值应该比计算出来的要大，原因是理论上一个叶节点中可能存放的记录数应该是1-1170行，但是1170是按照主键大小+指针大小计算出来的值，真正的行数据肯定还会有其他的字段，因此叶节点不能存放1170行数据是肯定的，那么多出来的行数据就会使用新的页进行存储并通过指针进行连接，这部分页并没有直接与B+树的中间节点连接，所以也无法进行精确计算。

如下图所示

树深度为2的时候，有1170^2个叶子节点 ，可以存储的数据为 1170X1170X16=21902400。

在查找数据时一次页的查找代表一次 IO，也就是说，一张 2000 万左右的表，查询数据最多需要访问 3 次磁盘。

所以在 InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。

3、B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。

4、它是根据左闭右开的区间 [ )来检索数据。

B+Tree 的数据搜寻过程：

1）比如我们要查找 28，在根节点就找到了键值，但是因为它不是页子节点，所以 会继续往下搜寻，28 是[28,66)的左闭右开的区间的临界值，所以会走中间的子节点，然后继续搜索，它又是[28,34)的左闭右开的区间的临界值，所以会走左边的子节点，最后在叶子节点上找到了需要的数据。

2）第二个，如果是范围查询，比如要查询从 22 到 60 的数据，当找到 22 之后，只需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点，这样就极大地提高了区间查询效率（不需要返回上层父节点重复遍历查找）。

重点

总结一下，InnoDB 中的 B+Tree 的特点：

1)它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。B Tree 解决的两大问题是什么？（每个节点存储更多关键字；路数更多）

2)扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵 B+Tree 拿到所有的数据）

3) B+Tree 的磁盘读写能力相对于 B Tree 来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）

4)排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）

5)效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）

数据结构可视化网站

2、B+Tree 落地形式

不同的存储引擎文件不一样。

1
show VARIABLES LIKE 'datadir';

每 张 InnoDB 的 表 有 两 个 文 件 （ .frm 和 .ibd ） ， MyISAM 的 表 有 三 个 文 件 （.frm、.MYD、.MYI）。

有一个是相同的文件，.frm。 .frm 是 MySQL 里面表结构定义的文件，不管你建表的时候选用任何一个存储引擎都会生成，我们就不看了。

我们主要看一下其他两个文件是怎么实现 MySQL 不同的存储引擎的索引的。

2.1 MyISAM

在 MyISAM 里面，另外有两个文件：

一个是.MYD 文件，D 代表 Data，是 MyISAM 的数据文件，存放数据记录，比如我 们的 user_myisam 表的所有的表数据。

一个是.MYI 文件，I 代表 Index，是 MyISAM 的索引文件，存放索引，比如我们在id 字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面。

也就是说，在 MyISAM 里面，索引和数据是两个独立的文件。

那我们怎么根据索引找到数据呢？

MyISAM 的 B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址，也就是指针。所以从索引文件.MYI 中找到键值后，会到数据文件.MYD 中获取相应的数据记录。

2.2 InnoDB

InnoDB 只有一个文件（.ibd 文件），那索引放在哪里呢？

在 InnoDB 里面，它是以主键为索引来组织数据的存储的，所以索引文件和数据文 件是同一个文件，都在.ibd 文件里面。

在 InnoDB 的主键索引的叶子节点上，它直接存储了我们的数据。

什么叫做聚集索引（聚簇索引）？

就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。（比如字典的目录 是按拼音排序的，内容也是按拼音排序的，按拼音排序的这种目录就叫聚集索引）。

在 InnoDB 里面，它组织数据的方式叫做叫做（聚集）索引组织表（clustered index organize table），所以主键索引是聚集索引，非主键都是非聚集索引。

主键之外的索引，比如我们在 name 字段上面建的普通索引，又是怎么存储和检索 数据的呢？

InnoDB 中，主键索引和辅助索引是有一个主次之分的。

辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终取得数据。

比如我们用 name 索引查询 name= ‘青山’，它会在叶子节点找到主键值，也就是 id=1，然后再到主键索引的叶子节点拿到数据。

3、主键索引的三种情形

有primaryKey –使用主键组织数据存储

没有主键，存在unique字段– 使用该unique字段组织数据存储

没有主键，没有unique字段–使用隐藏字段_rowid组织数据

4、使用索引的注意点

回表查询：命中辅助索引后，根据辅助索引查询到的主键，再去主键索引中查询数据，称为回表

覆盖索引：组成联合索引的字段包含了所需查询的字段，查询到辅助索引页即可得到结果，无需回表查询

  1. 为什么不建议使用Select * ？

    阻止了覆盖索引生效，导致回表查询，使用指定列的sql能节省数据库内存占用，提高数据传输效率

  2. 索引的最左匹配原则是什么意思？

    有联合索引 index(A,B,C)

    查询时，使用A、A&B 、A&B&C 查询都能命中该索引，且与字段顺序无关，即B&A也能命中

    A&C B&C B C 都不符合最左匹配原则，不能命中

  3. 模糊匹配可以用到索引吗？

    like %abc 不能命中索引，like abc%可以命中

    因此我们得出结论：前导模糊匹配不能命中索引

  4. 负向查询 != not in <> 能不能用到索引？

    能不能用到索引是优化器决定的，优化器基于开销判断，一般不推荐使用负向查询

  5. 为什么推荐递增字段做主键索引？

    InnoDB的索引底层是B+树，且通过主键索引来组织数据存储。如果使用自增主键，那么每次插入新的记录，就会顺序添加到当前索引节点的后续位置（右边），当写满一页就会开辟新页，这样就会形成一个近似顺序填满的紧凑结构，插入过程无需移动已有数据。

    而如果使用uuid或者身份证号这种不规则的数据作为主键索引，那么插入数据时，相当于随机插入，导致已有数据频繁移动，磁盘io开销变大，且可能产生大量的叶碎片

总结

使用索引应注意以下几点：

  • 负向查询不能命中索引
  • 前导模糊查询不能命中索引（like条件前面带%）
  • 字符串不加引号，出现隐式转换 ，不能命中索引
  • 数据区分度不大不宜建立索引（性别）
  • 在索引属性上进行计算（函数或表达式）不能命中索引

并非周知的sql实践：

  • 业务存在大量单条查询，实用hash索引效率高
  • 允许为null的字段有大坑，单列索引不存null值，复合索引不存全为null的值，设置为not null 或者设置默认值
  • 固定范围取值的字段使用枚举类型而不是字符串

小众实用的规则：

  • 明确返回结果数量，实用limit能提升查询效率
  • 把计算放到业务层而不是数据库层
  • 强制类型转换会扫描全表

参考：

数据库索引，到底是什么做的？