MySQL - 进阶篇 - 第4篇 - MySQL索引彻底刨析

概述

• 在本篇章的 MySQL - 进阶篇 - 第1篇 - MySQL索引基础篇 和 MySQL - 进阶篇 - 第2篇 - MySQL索引高级篇 已经详细讲解了MySQL数据库的索引 。所以本篇着重点不是上述文章重复的内容

索引是什么

• 数据库索引，是数据库索引系统（DBMS）中一个排序的数据结构，以协助快速查询、更新数据库表中的数据
• 数据是以文件的形式存储在磁盘文件中的，每一行的数据都有其磁盘地址。

索引类型

• 普通索引（Normal）：也叫非唯一索引，是最普通的索引，没有任何限制
• 唯一索引（Unique）：唯一索引要求键值不能重复。另外注意的是，主键索引是一种特殊的为唯一索引，它还要求了一个限制条件，要求键值不能为空。主键索引引擎用 primary key创建
• 全文索引（FullText）：针对比较大的数据，比如存放的是消息内容，有几kb的情况。而且只有文本类型的字段才可以创建全文索引，如char、varchar、text
  • MyISAM和Innodb支持全文索引

索引存储模型推演

二叉查找树（BST Binary Search Tree）

• 二叉查找树的左子树的节点都小于父节点，右子树的所有节点都大于父节点，投影到平面之后，就是一个有序的线性表。
• 二叉查找树既可以实现快速查找，又可以快速插入，但是其有一个问题，就是查找耗时是和这棵树的深度是有关的，在最坏的情况下退化到 O（N）

平衡二叉树（AVL Tree / Balanced binary search Tree）

• 平衡二叉树的定义：最优子树深度差的绝对值不能超过1
• 为什么其可以做到，是因为每次插入都会进行自平衡 - 也就是左旋和右旋
• 在AVL树中，如何存储？
  • 每一个节点它的大小都是一个固定的单位
  • 作为索引其应该存储三块的内容
    • 第一个就是索引的键值。
    • 第二个就是索引的存储地址
    • 第三个就是左子节点和右子节点的引用
  • 这样存储会不会有问题？
    • Innodb中一页、也就是一个节点的大小是16kb，仅仅存储这些数据，只用了一点点的空间，访问一次IO，浪费了大量的空间
  • 所以如何解决？
    • 让每个节点存储更多的数据
    • 节点上的关键字的数量越多，指针数也就越多，也就是意味着有更多的分叉，分叉多了，树的深度就回减少

多路平衡查找树（B Tree）（分裂/合并）

• Balanced Tree
• 和AVL树一样，B数在叶子节点存储键值，数据地址，节点引用
• 它有一个特点：分叉树（路数）永远比关键字多1.
• 也就是说每个节点只存储2个关键字，但是每个节点指向3个节点
• B Tree 是一个分裂合并的树
  • 节点的分裂和合并，其实就是InnoDB页（page）的分裂和合并

B+Tree （加强版多路平衡二叉树）

• 虽然B树的效率很高了，但是MySQL还是对B Tree 进行了改良，最终使用了 B+Tree
• MySQL的B+Tree的几个特点
  • 它的关键字的数量是和路数相等的
  • B+Tree 的根节点和枝节点都不会存储数据，只有叶子节点才存储数据
  • 目前的认知：我们这要存放的数据是什么？是不是真实的地址？
  • 搜索到关键字不会直接返回，会到最后一层的叶子节点。因为真实的数据地址是保存在叶子节点的
  • B+Tree 的每个叶子节点增加了一个指向相邻的叶子节点的指针， 它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。
• InnoDB中的B+Tree这种特点带来的优势
  • 它是B Tree的变种，B Tree 能解决的问题，它都会解决。B Tree 解决的两大问题是什么？
    • 每个节点存储更多的数据
    • 路数更多
  • 扫库、扫表能力更强（对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整个B+Tree拿到所有的数据）
  • B+Tree 的磁盘读写能力相对于 B Tree 来说更强，（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
  • 排序能力增强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
  • 效率更加稳定（B+Tree永远都是在叶子节点拿到数据，所以IO次数是稳定的）

索引方式：真的是使用B+Tree吗？

• 在Navicat的工具，创建索引，索引方式有2种
• HASH：以KV的形式检索数据，也就是说，它会根据索引字段生成哈希码和指针，指针指向数据
• 哈希索引的特点
  • 时间复杂度是O（1）查询速度快，但是哈希索引里面的数据不是按照顺序存储的，所以不能用来排序
  • 在查询数据的时候需要根据键值计算哈希码，所以只支持等值查询 （= IN）不支持范围查询（> < >= <= between and）
  • 如果字段重复值很多的时候，会出现大量的哈希冲突（采用拉链法解决），效率会降低
• 需要注意的是：Innodb不能显示创建一个hash索引，但是Mamory可以使用Hash索引

B+Tree的落地形式

MySQL数据存储文件

• 我们知道了不同的存储引擎文件不一样：show variables like 'datadir';
• 每张innodb表有两个文件（.frm / .ibd），MyISAM的表有3个文件（.frm / .MYD / .MYI）

MyISAM

• MyISAM文件中，D代表Data，是MyISAM的数据文件，存放数据记录，I标识index，是MyISAM的索引文件，所以索引和数据是两个单独的文件
• 那么如何找到数据呢?
  • MyISAM的B+Tree里面，叶子节点存储的是数据文件对应的磁盘地址，所以从索引文件 .MYI中找到键值之后，会到 .MYD 文件获取相应的数据
• 在MyISAM里面，辅助索引也在这个文件里面。辅助索引和主键索引和检索数据的方式是没有任何区别的，一样实在索引文件里面找到磁盘地址，然后到数据文件中获取数据

InnoDB

• InnoDB中，它是以主键为索引来组织数据结构的，所以索引文件和数据文件是同一个文件，都在 .ibd 文件里面
• 在Innodb的主键索引的叶子节点上，直接存储了我们的数据
• 聚集索引（聚簇索引）：就是按照 索引键值 的逻辑顺序跟 表数据行 的物理存储地址是一致的
• 在Innodb里面，它组织数据的方式叫做（聚集）索引组织表，所以主键是聚集索引，非主键都是非聚集索引
• 那么主键之外的索引，又是怎么存储和检索数据的？
• 在Innodb中，主键索引和辅助索引是有一个主次之分的
• 辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终获得数据。
• 如果一张表没有主键怎么办？
  • 如果我们定义了主键（Primary key），那么Innodb会选择主键作为聚集索引
  • 如果没有显示定义主键，则Innodb会选择第一个不包含有null值得唯一索引作为主键索引
  • 如果上面的索引都没有，那么Innodb会选择内置6字节长度的ROWID作为隐藏的聚集索引，他会随着行记录的写入而主键递增

索引的使用原则

• 此部分在之前的两篇 MySQL - 进阶篇 - 第1篇 - MySQL索引基础篇 和 MySQL - 进阶篇 - 第2篇 - MySQL索引高级篇 已经详细讲解到

• 不要再离散度低的列上建立索引

• 联合索引的最左匹配

• 覆盖索引

  • 回表
  • 非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查出索引里面没有的数据，它是基于主键索引的查询多扫描了一颗索引树，这个过程就是回表

• 索引的创建规则和索引失效的情况，不再重复列举，详情请看：之前的两篇 MySQL - 进阶篇 - 第1篇 - MySQL索引基础篇 和 MySQL - 进阶篇 - 第2篇 - MySQL索引高级篇