Index

索引建立在表上。

MySQL索引

什么是索引

  • 索引是MySQL中用于高效获取数据的数据结构。通俗的说，数据库索引好比是一本书的目录，可以直接根据页码找到对应的内容，目的就是为了加快数据库的查询速度
  • 索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息
  • 一种能帮助mysql提高了查询效率的数据结构：索引数据结构

索引的原理

  • 一句话总结：以空间换时间
  • 未添加索引的数据库，在查询时按全文进行搜索，也就是说有多少数据就进行多少次查询，然后找到相应的数据就把它们放到结果集中，直到全文扫描完毕，这样的效率很低，也体现了在大数据中索引的必要性
  • 索引本身也很大而且也有持久化存储的需求，所以其存储在硬盘文件中，一般是单独的索引文件或和数据一起存储在数据文件

索引的分类

  • 主键索引：设定主键后，数据库自动建立索引，InnoDB中为聚簇索引，主键索引列值不能为空（Null）
  • 普通索引：又称单值索引，即一个索引只包含单个列，一个表可以有多个单列索引
  • 唯一索引：指定某一列进行索引，列中的值必须唯一，允许有空值（Null），但只允许有一个空值（Null）
  • 复合索引：又称组合索引、联合索引。一个索引可以包含多个列，多个列共同构成一个复合索引
  • 全文索引：MySQL5.7之前，只有MYISAM存储引擎引擎支持全文索引，全文索引类型为FULLTEXT，在定义索引的列上支持值的全文查找允许在这些索引列中插入重复值和空值。全文索引可以在Char、VarChar 上创建
  • 前缀索引：在文本类型为char、varchar、text类列上创建索引时，可以指定索引列的长度，但是数值类型不能指定

索引的优缺点

  • 优点：
    • 提高数据查询速度
    • 降低数据库I/O成本，为建立索引前需要将记录逐条读入内存比较后加入结果集
    • 被索引的列会自动排序，提高需要排序的场景的性能
  • 缺点：
    • 索引额外占用磁盘空间
    • 索引虽然提升查询效率，但降低更新效率，因为每次更新表数据时要同时更新索引
    • 维护索引要消耗数据库资源

基本操作

  • 创建索引

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    -- 主键索引
    -- 建表时指定主键，自动以主键建立索引
    CREATE TABLE 表名(
    字段1 类型 primary key,
    字段2 类型,
    字段3 类型
    );

    -- 普通索引
    CREATE INDEX 索引名 ON 表名(字段名)

    -- 唯一索引
    CREATE UNIQUE INDEX 索引名 ON 表名(字段名)

    -- 复合索引
    CREATE INDEX 索引名 ON 表名(字段1,字段2 ...)

  • 查看索引

    1
    show INDEX FROM 表名;

  • 删除索引

    1
    DROP INDEX 索引名 ON 表名;

索引的数据结构

MySQL索引使用的数据结构主要有BTree索引和hash索引。

不同存储引擎对索引有不同的实现方式

  • MyISAM：B+Tree叶节点的data域存放的是数据记录的地址。在索引检索的时候，首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则根据data域中磁盘地址到磁盘中寻址定位到对应的磁盘块，然后读取相应的数据记录，这被称为“非聚簇索引”
  • InnoDB：其数据文件本身就是索引文件。相比MyISAM的索引文件数据文件分离，其表数据文件本身就是按照B+Tree组织的一个索引结构，树的叶节点data域保存了完整的数据记录。这个索引的Key是数据表的主键，因此InnoDB表数据文件本身就是主索引。这被称为“聚簇索引（聚集索引）”。而其余的索引都作为辅助索引，辅助索引的data域存储相应记录主键的值而不是地址，这也是和MyISAM不同的地方

Hash索引

Hash表，以键值对的形式存储数据。使用hash表存储表数据结构时，Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；但是不支持范围快速查找，范围查找时只能通过扫描全表的方式，筛选出符合条件的数据。

显然这种方式，不适合我们经常需要查找和范围查找的数据库索引使用。

B+树索引

  • 平衡二叉树

    • 平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。
    • 使用平衡二叉查找树查询的性能接近与二分查找，时间复杂度为O(log2n)
    • 然而平衡二叉树依旧存在一些问题：
      • 时间复杂度和树的高度有关。树有多高就需要I/O多少次（MySQL每次只将一个索引树节点读入内存）
      • 平衡二叉树不支持范围查询快速查找，范围查询需要从根节点多次遍历，查询效率不高

  • B树

    • B树是多叉平衡查找树，他将索引由高瘦变成矮胖，从而大大减少了检索时的I/O次数
    • 特点：
      • B树的节点中存储这多个元素，每个内节点有多个分叉
      • 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点中都存储数据
      • 父节点当中的元素不会出现在子节点中
      • 所有的叶子节点都位于同一层，叶子节点具有相同的深度，叶子节点之间没有指针连接
    • 缺陷：
      • 不支持快速范围查找，如根据上图，想查询10到35之间的数据查询到10后需要回到根节点再重新多次遍历
      • 每个节点都保存数据或数据的地址，如果节点中data块保存的是数据那么data块就会随着表中字段的增加而变大，这样节点占用的空间就要变大，又由于MySQL单此I/O具有上限，单个节点保存的索引数就要降低，就会使B树重新变得瘦高，降低了性能

  • B+树

    • B+树，作为B树的升级版，和B树最主要的区别在于B+树只在叶子节点存储数据或数据的地址，B+树也是MySQL使用的索引数据结构之一
    • B+树的非叶子节点只存储键和指针，叶子节点存储键和数据，并且在叶子节点之间使用双向指针相连，形成了一个双向有序链表
    • B+树的最底层叶子节点包含了所有的索引项。从上图可以看出，B+树在查找数据的时候，由于数据都存放在最底层的叶子节点上，所以每次查找都需要检索到叶子节点才能查询到数据。所以在查询数据的情况下每次的磁盘IO次数跟树的高度有直接的关系；但是从另一方面来说，由于数据都被存放到了叶子节点，所以存放索引的磁盘块，所存放的的索引数量会随之增加，所以相对于B树来说，B+树的树高理论情况下是比B树树高要矮的。
    • B+树的范围查询也有更好的性能，由于叶子节点组成了双向有序链表，所以只需查找到范围两端对应的叶子节点即可找到整个范围包含的所有记录

MySQL的索引实现

不同存储引擎实现索引的方式不同。下面分别对两个引擎举例说明MySQL索引实现过程

MyISAM

以一个简单的user表为例，user表存在两个索引，id列为主键索引，age列为普通索引。

1
2
3
4
5
6
7
8
9
10
CREATE TABLE `user`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = MyISAM
  AUTO_INCREMENT = 1
  DEFAULT CHARSET = utf8;

MyISAM的数据文件和索引文件是分开存储的，MyISAM使用B+树构建索引树时，叶子节点中键值key存储的是索引列的值，数据data存储的是索引所在行的磁盘地址。

根据主键等值查询数据

1
select * from user where id = 28

根据主键范围查询数据

1
select * from user where 28<=id<=47;

根据辅助索引查找

在MyIASM中，辅助索引建立起一个以age为索引的新B+树，其他过程与主键索引基本相同，只有一点需要注意MyIASM的辅助索引键可能不唯一，可能存在多个拥有相同键的记录，所以即使是等值查询，也需要按照范围查询的方式在辅助索引树种检索数据

InnoDB

InnoDB在建表时默认就会根据主键建立索引，并且在索引树中直接存储记录数据（成为聚簇索引），而非像MyIASM一样只存储记录数据的地址。

每个InnoDB表都有一个聚簇索引，聚簇索引使用B+树构建，叶子节点的data阈存储的是整行记录。具体创建规则如下：

  1. InnoDB创建索引的具体规则如下：
  2. 如果表没有定义主键，InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。
  3. 如果以上两个都没有，InnoDB会自动使用一个长度为6字节的ROWID字段来构建聚簇索引，该ROWID字段会在插入新的行记录时自动递增。

除聚簇索引之外的所有索引都被称为辅助索引。在InnoDB中，辅助索引中的叶子节点键值存储的是该行的主键值。在检索时，InnoDB最终还是要使用主键在聚簇索引中搜索行记录，这个过程称之为回表。

以user_innodb表为例，user_innodb的id列为主键，age列为普通索引。

1
2
3
4
5
6
7
8
CREATE TABLE `user_innodb`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = InnoDB;

主键索引（聚簇索引）

1
select * from user_innodb where id = 28;

单值辅助索引

1
select * from t_user_innodb where age=19;


磁盘IO数（从根节点开始）：辅助索引3次 + 回表过程3次。

组合索引

以表中多个字段组合形成索引的key，也是一种辅助索引。

1
select * from abc_innodb where a = 13 and b = 16 and c = 4;

覆盖索引

覆盖索引并不是一种索引结构，覆盖索引是一种很常用的优化手段。因为在使用辅助索引的时候，我们只可以拿到相应的主键值，想要获取最终的数据记录，还需要根据主键通过主键索引再去检索，最终获取到符合条件的数据记录。而如果我们使用的是组合索引，而要查询的值恰好包含在组合索引的key中，则不需要回表查询操作