你需要知道的MySQL索引

591 阅读13分钟

什么是索引

索引是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。这里需要记住一点:索引是一种数据结构。 在RDBMS系统中,数据的索引都是硬盘级索引。

索引的类型

既然索引是一种数据结构,那不同的数据结构有着不同的特性,可以为不同的场景提供更好的性能。

哈希索引

哈希索引(hash index)是基于哈希表的实现,只有在能够精确匹配索引所有列的的查询才有效。对于每一行数据,存储引擎都会先计算一个hash code(哈希码),哈希索引将所有的hash code存储在索引中,同时在哈希表中保存指向每个数据行的指针。在进行哈希查找时,根据关键字,使用相同的函数h计算哈希地址h(k),然后直接寻址相应的Hash bucket,直接到对应的链表中取出数据。因此,Hash 查找算法的数据结构由Hash Bucket数组,映射函数f和数据链表组成,通常将Bucket数组和数据链表称作Hash Table,如图,Hash Table由5个buckets和7个数据结点组成:

在这里插入图片描述
哈希查找的时间复杂度是O(n/m),n是指数据结点的数量,m是bucket的数量,在理想情况下,Hash Bucket足够多,Hash函数不产生重复的Hash Value,哈希查找的时间复杂度最优到达O(1),但是,在实际应用中,哈希函数有一定的几率出现重复的哈希地址,产生哈希冲突,时间复杂度会低于O(n/m);在最差的情况下,时间复杂度是O(n)。 在MySQL中,只有Memory引擎显式的支持hash索引,同时也是Memory的默认索引类型,同时Memory也支持非唯一哈希索引,如果存在多个列的hash code 相同,索引会以链表的方式存放多个记录指针到同一个哈希条目中,聪明的你也许就想到了HashMap的数据结构了。 因为哈希索引自身只需要存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快。然而,哈希索引也有它的限制:

  • 哈希索引只包含哈希值和指针,而不存储数据,所以不能通过使用索引中的值来规避回表操作
  • 哈希索引数据并不是按照索引值顺序存储的,所以也就无法用于排序
  • 哈希索引无法支持部分索引列匹配查找,因为哈希索引始终是使用索引列进行哈希计算获取到哈希值。例如:如果在(A,B)上建立哈希索引,如果只查询列A,则无法使用这个哈希索引。
  • 哈希索引只支持等值查询,包括 = ,in , <=> 。不支持任何范围查询。
  • 访问哈希索引的速度非常快,但是如果存在多个数据同样的hash code,则会严重影响哈希索引查找数据的速度。
  • 哈希索引中的哈希冲突严重的话,也严重影响哈希索引的维护,增,删,改。

B+Tree索引

在了解B+Tree索引之前,先了解对B+Tree索引的演进过程

二叉查找树

二叉查找树是二分查找的思想的体现,二叉查找树的一个特点事左子树的所有的节点均小于父节点,而右子树上的所有节点均大于父节点。因此,这是一个有序的链表:

在这里插入图片描述
从这个数据结构可以看出,二叉树嫩能够实现快速的查找和插入。但是同时二叉树会严重依赖于插入数据的顺序,如果插入的顺序是有序的,比如是1、2、3、4、5。则会退化成单向链表,时间复杂度为O(n)了。这种树也称为斜树,左右树深相差太多了,因此这时候就需要对这一点进行改进,演变出了平衡二叉树(Balanced binary search trees)或AVL树。

在这里插入图片描述

平衡二叉树(AVL树)

先看对平衡二叉树的定义:左右子树的相差度不会超过1。也就是说当左右子树的树高深度不会相差超过1,当超过的时候会发生左旋和右旋,自动维护树的平衡。

在这里插入图片描述
这是按照1、2、3、4、5、6的顺序插入的数据,会自动通过左旋和右旋保证树的平衡,使每个左右树的高度不会超过1。 如果平衡二叉树作为索引,它应该怎么存储数据:

  • 索引列的值,比如我们在id上建立索引,则这个节点上需要存储id的值。
  • 数据行的磁盘地址,通过索引能够查找到数据存放的位置
  • 因为是二叉树,则每个节点会存储左右节点的引用,如果没有,则存null。
    在这里插入图片描述
    比如这是一张有6条数据的表,当我们查询索引列为37的数据,需要先查询出26条数据,然后判断37大于26,走右路,然后再获取到52,走左路,才能找到37,这里一共发生了3次磁盘IO,一次IO耗时大概在10ms左右,数据量多的话将耗费大量的时间。

多路平衡查找树(B-Tree)

在引入多路平衡查找树之前,先知道为什么。在平衡二叉树的结构中,每一个树高都需要一次IO去读取,在这里,我们就需要减少树高来减少IO次数。 Balanced Tree 这个就是我们的多路平衡查找树,叫做 B Tree(B 代表平衡)。跟 AVL 树一样,B 树在枝节点和叶子节点存储键值、数据地址、节点引用。它有一个特点:分叉数(路数)永远比关键字数多 1。比如我们画的这棵树,每个节 点存储两个关键字,那么就会有三个指针指向三个子节点。

在这里插入图片描述
B Tree 的查找规则是什么样的呢?比如我们要在这张表里面查找 99。因为 99大于 35,走右边。因为 99 大于 87,走右边。在磁盘块 12中99,只用了 3 次 IO。 InnoDB在默认的情况下一次是按页存储和加载的,按页为单位进行读取加载的,页的大小是16kb,从而通过使用多路平衡树达到减少IO的目的。 B+树(加强版多路平衡查找树) B Tree 的效率已经很高了,为什么 MySQL 还要对 B Tree 进行改良,最终使用了 B+Tree 呢?总体上来说,这个 B 树的改良版本解决的问题比 B Tree 更全面。我们来看一下 InnoDB 里面的 B+树的存储结构:
在这里插入图片描述

B+Tree的特点

它的关键字的数量是跟路数相等的; B+Tree 的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。搜索 到关键字不会直接返回,会到最后一层的叶子节点。比如我们搜索 id=28,虽然在第一 层直接命中了,但是全部的数据在叶子节点上面,所以我还要继续往下搜索,一直到叶 子节点。 举个例子:假设一条记录是 1K,一个叶子节点(一页)可以存储 16 条记录。非叶 子节点可以存储多少个指针? 假设索引字段是 bigint 类型,长度为 8 字节。指针大小在 InnoDB 源码中设置为 6 字节,这样一共 14 字节。非叶子节点(一页)可以存储 16384 / 14 = 1170 个这样的 单元(键值+指针),代表有 1170 个指针。 树深度为 2 的时候, 有 1170^2 个叶子节点 ,可以存储的数据为 1170 * 1170 * 16 = 21902400。 在查找数据时一次页的查找代表一次 IO,也就是说,一张 2000 万左右的表,查询数据最多需要访问 3 次磁盘。所以在 InnoDB 中 B+ 树深度一般为 1-3 层,它就能满足千万级的数据存储。

  • B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数 据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。
  • 它是根据左闭右开的区间 [ )来检索数据。

索引的优缺点

索引可以让服务器快速定位到表的指定位置,这不是索引的唯一有点。

  • 索引大大减少了服务器需要扫描的数据量
  • 索引可以帮助服务器避免排序和临时表
  • 索引可以将随机I/O变为顺序I/O

索引在查询上带来很大的性能提升,则在写上会带来额外的性能损耗

  • 创建索引和维护索引需要耗费时间,这种时间是随着数据量的增加而增加
  • 索引需要占用物理空间,除了数据表占数据空间之外,每一个索引还要占用一定的物理空间
  • 当对表中的数据进行增加、删除和修改的时候,索引也需要动态的维护,这就降低了数据的维护速度。

如何用好索引

既然索引存在这么多的好处,是否只要在相应的字段上创建相应的字段就可以了。答案是并没有那么简单,只有理解了索引的原理和特点,才能更好的发挥索引的优势。

独立的列

CREATE TABLE `test_2` (
  `id` int NOT NULL,
  `name` varchar(50) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB ;

创建一张如上语句的表,对该表使用如下语句进行查询:

mysql> explain select * from test_2 where id + 1 = 3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | test_2 | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    2 |   100.00 | Using where |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

在这里,并没有使用到索引,对我们来说id + 1 = 3 很容易就转成了id=2来进行查询,但是MySQL却无法做到,这里需要养成一个习惯,无论是运算还是函数计算,都需要放到符号的右侧,否则无法使用到索引。

mysql> explain select * from test_2 where id = 3 - 1;
+----+-------------+--------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
| id | select_type | table  | partitions | type  | possible_keys | key     | key_len | ref   | rows | filtered | Extra |
+----+-------------+--------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | test_2 | NULL       | const | PRIMARY       | PRIMARY | 4       | const |    1 |   100.00 | NULL  |
+----+-------------+--------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
1 row in set, 1 warning (0.01 sec)

前缀索引

有时候,可能要对一列会存储很长字符串的列进行添加索引,这种情况下会让索引变的大而且很难维护。这种情况下可能就需要使用到前缀索引。一方面能够节省索引空间,另一方面能够提高索引的效率,这里需要通过对该列的计算来得到最佳的列前缀的长度,既能节省空间,也能保证较好的可选择性。 在表中写入如下测试数据

mysql> select * from test_2;
+----+--------------+
| id | name         |
+----+--------------+
|  1 | wangyi       |
|  2 | zhoue        |
|  3 | zfsafadsds   |
|  4 | zfsafadsds   |
|  5 | zhangsan     |
|  6 | zhangli      |
|  7 | zhanghong    |
|  8 | zhangfdsafas |
|  9 | zhangfsafhs  |
| 10 | zhangflllll  |
+----+--------------+
10 rows in set (0.00 sec)

先查看最排前的数据,这里数据量比较少,仅做演示作用。

mysql> select count(*) as cnt ,name from test_2 group by name order by cnt  desc limit 10;
+-----+--------------+
| cnt | name         |
+-----+--------------+
|   2 | zfsafadsds   |
|   1 | wangyi       |
|   1 | zhoue        |
|   1 | zhangsan     |
|   1 | zhangli      |
|   1 | zhanghong    |
|   1 | zhangfdsafas |
|   1 | zhangfsafhs  |
|   1 | zhangflllll  |
+-----+--------------+
9 rows in set (0.00 sec)

我们可以发现全表查询的情况下,区分度还是很高,数据分布较均匀,现在我们先看看从三个列前缀看看情况如何:

mysql> select count(*) as cnt ,left(name,3) as pref  from test_2 group by pref order by cnt  desc limit 10;
+-----+------+
| cnt | pref |
+-----+------+
|   6 | zha  |
|   2 | zfs  |
|   1 | wan  |
|   1 | zho  |
+-----+------+
4 rows in set (0.00 sec)

情况并不好,数据都集中在 zha 前缀上。下面我们来统计不同前缀的区分度:

mysql> select count(distinct left(name,3))/count(*) as pref3,  
    -> count(distinct left(name,4))/count(*) as pref4,
    -> count(distinct left(name,5))/count(*) as pref5,
    -> count(distinct left(name,6))/count(*) as pref6,
    -> count(distinct left(name,7))/count(*) as pref7,
    -> count(distinct left(name,8))/count(*) as pref8        
    -> from test_2;
+--------+--------+--------+--------+--------+--------+
| pref3  | pref4  | pref5  | pref6  | pref7  | pref8  |
+--------+--------+--------+--------+--------+--------+
| 0.4000 | 0.4000 | 0.4000 | 0.7000 | 0.9000 | 0.9000 |
+--------+--------+--------+--------+--------+--------+
1 row in set (0.00 sec)

你会发现当索引长度选择为7的时候,已经能达到很好的区分度,因此可以建立前缀长度为7的前缀索引就能够达到不错的效果

mysql> alter table test_2 add key (name(7));
mysql> show index from test_2\G;
*************************** 1. row ***************************
        Table: test_2
   Non_unique: 0
     Key_name: PRIMARY
 Seq_in_index: 1
  Column_name: id
    Collation: A
  Cardinality: 0
     Sub_part: NULL
       Packed: NULL
         Null: 
   Index_type: BTREE
      Comment: 
Index_comment: 
      Visible: YES
   Expression: NULL
*************************** 2. row ***************************
        Table: test_2
   Non_unique: 1
     Key_name: name
 Seq_in_index: 1
  Column_name: name
    Collation: A
  Cardinality: 9
     Sub_part: 7
       Packed: NULL
         Null: 
   Index_type: BTREE
      Comment: 
Index_comment: 
      Visible: YES
   Expression: NULL
2 rows in set (0.00 sec)

多列索引

很多人在创建多列索引的时候,可能会有两个常见的错误: 为每个列建立一个单独的索引 按照错误的顺序建立多列索引 使用不同的写法有不同的表现:

mysql> explain select * from test_2 where id=1 or name='zfsafadsds'\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test_2
   partitions: NULL
         type: index_merge
possible_keys: PRIMARY,name
          key: name,PRIMARY
      key_len: 30,4
          ref: NULL
         rows: 3
     filtered: 100.00
        Extra: Using sort_union(name,PRIMARY); Using where
1 row in set, 1 warning (0.00 sec)

mysql> explain select * from test_2 where id=3 and name='zfsafadsds'\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test_2
   partitions: NULL
         type: const
possible_keys: PRIMARY,name
          key: PRIMARY
      key_len: 4
          ref: const
         rows: 1
     filtered: 100.00
        Extra: NULL
1 row in set, 1 warning (0.00 sec)

mysql> explain select * from test_2 where id=1 union select * from test_2 where name='zfsafadsds'\G;
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: test_2
   partitions: NULL
         type: const
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: const
         rows: 1
     filtered: 100.00
        Extra: NULL
*************************** 2. row ***************************
           id: 2
  select_type: UNION
        table: test_2
   partitions: NULL
         type: ref
possible_keys: name
          key: name
      key_len: 30
          ref: const
         rows: 2
     filtered: 100.00
        Extra: Using where
*************************** 3. row ***************************
           id: NULL
  select_type: UNION RESULT
        table: <union1,2>
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: NULL
     filtered: NULL
        Extra: Using temporary
3 rows in set, 1 warning (0.00 sec)

从上面的执行结果可以看出:

  • 当出现对多个索引做交互操作时(通常有多个AND条件),通常意味着需要建立一个包含所有列的多列索引;
  • 当出现对多个索引做联合操作时(通常是多个OR条件),通常需要耗费大量的CPU和内存资源在算法的缓存、排序和合并上,不然UNION的效果来的好。

如何正确的选择索引的顺序

  • 能够通过调整顺序能减少索引的维护,推荐调整顺序
  • 索引的顺序会影响索引列的排序,先按照第一列进行排序,再按照第二列... ,可以满足order by 、distinct和group by的要求。
  • 如果没有排序要求,则按照数据的区分度来调整顺序

三星索引

对查询的列进行了索引 谓之 一颗星

使用索引避免了排序 谓之 两颗星

使用索引避免了回表 谓之 三颗星

喜欢的朋友可以关注公众号

参考资料

In-Memory:哈希索引 MySQL相关(三)- 索引数据模型推演及 B+Tree 的详细介绍 《高性能MySQL》