Scott's world.

MySQL-索引笔记(上)

Word count: 2.6kReading time: 9 min
2019/10/19 Share

MySQL-索引笔记(上)

在MySQL中索引的地位可谓是重要之重,如果没有了索引,那么MySQL的查询效率无法想象

一句话来说为什么会出现MySQL的索引:

提高数据查询的效率

索引的概念其实非常好懂,当你查询一个东西的时候,一般是先找到这个东西的索引,通过索引查找它的位置,类似于书中的目录,城市的街道名等

索引的常见模型

实现索引的方式有非常多的方法,所以就引入了索引模型的概念

下面就介绍三种最常见的数据结构来实现索引模型

  • 哈希表
  • 有序数组
  • 搜索树

哈希表

在日常开发中用哈希表来实现索引应该是最常见的方法

哈希表结构也非常的简单,即

key-value

哈希表查找数据,只需要key,便可以找到相应的value,而key便是索引的实现

而实现哈希表也非常简单

  • 创建存储数据的数组
  • 通过散列函数把key转化成一个确定的位置
  • 最后把value放进数组中的这一个位置中

但是哈希表也有一些问题,比如key冲突,空间消耗过大

其中解决key冲突的方法,一般是通过把value用链表的结构来存储,还有的方法是也通过优化散列函数来实现

哈希表查询方面虽然优势非常明显,那就是随机查询的时间复杂度为O(1)

但劣势也非常明显,那就是除非保证key有序那么区间查询的效率是非常慢的

所以哈希表这种结构是用于只有等值查询的场景,比如Memcached及其他一些NoSQL引擎

哈希具体的数据结构介绍可以参考我写的

第十一讲-散列查找)

有序数组

上面说到哈希表的区间查询的劣势,那么有序数组的优势便是区间查询,因为是有序的,且在等值查询和范围查询效率也非常的高

有序数组结构更加的简单,只要保证数组的索引是有序就可以了

有序数组的查询可以通过二分法来快速得到,这个时间复杂度是O(log(N))

如果仅仅看查询效率,有序数组就是最好的数据结构了。但是,在需要更新数据的时候就麻烦了,你往中间插入一个记录就必须得挪动后面所有的记录,成本太高。

所以,有序数组索引只适用于静态存储引擎,即改动次数比较少的数据

搜索树

二叉搜索树是树的数据结构中比较出名的一种

  • 二叉搜索树的成立条件

    每个节点的左儿子小于父节点,父节点又小于右儿子

二叉搜索树查询的时间复杂度是O(log(N)),当然为了保持这一时间复杂度,你需要保持这棵树为平衡二叉树,为平衡二叉树的插入和删除的时间复杂度也为O(log(N))

具体搜索树的数据结构介绍可以看我写的

第四讲-树)

N叉树

虽然二叉树的搜索效率最高,但是大多数的数据库存储却并不使用二叉树,其原因是索引不止在内存中,还要写到磁盘上

你可以想象一下一棵100万节点的平衡二叉树,树高20。一次查询可能需要访问20个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要10 ms左右的寻址时间。也就是说,对于一个100万行的表,如果使用二叉树来存储,单独访问一个行可能需要20个10 ms的时间,这个查询是非常慢的

为了让一个查询尽量少地读磁盘,那么就需要使用“N叉”树。这里,“N叉”树中的“N”取决于数据块的大小

以InnoDB的一个整数字段索引为例,这个N差不多是1200。这棵树高是4的时候,就可以存1200的3次方个值,这已经17亿了。考虑到树根的数据块总是在内存中的,一个10亿行的表上一个整数字段的索引,查找一个值最多只需要访问3次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了

N叉树由于在读写上的性能优点,以及适配磁盘的访问模式,已经被广泛应用在数据库引擎中了

InnoDB的索引模型

在InnoDB中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表

前面我们提到的,InnoDB使用了B+树索引模型,所以数据都是存储在B+树中的。

每一个索引在InnoDB里面对应一棵B+树

每一个表是好几棵B+树

假设,我们有一个主键列为ID的表,表中有字段k,并且在k上有索引,即

1
2
3
4
5
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;

其这里就需要介绍索引类型,它分为

  • 主键索引(聚簇索引(clustered index))

    叶子节点存的值为整行数据

  • 非主键索引((二级索引(secondary index))

    叶子节点存的值为主键的值

那么,基于主键索引和普通索引的查询有什么区别?

  • 如果语句是

    1
    select * from T where ID=500

    即主键查询方式,则只需要搜索ID这棵B+树

  • 如果语句是

    1
    select * from T where k=5

    即普通索引查询方式,则需要先搜索k索引树,得到ID的值为500,再到ID索引树搜索一次。这个过程称为回表

我们可以看到如果用非主键索引的查询,除了查询该索引的树还需要回到主键索引树中查询数据,因此,我们在应用中应尽量使用主键查询

索引维护

B+树为了维护索引有序性,在插入新值的时候需要做必要的维护

以上面这个图为例,如果插入新的行ID值为700,则只需要在R5的记录后面插入一个新记录。如果新插入的ID值为400,就相对麻烦了,需要逻辑上挪动后面的数据,空出位置

但是更糟的情况是,R5所在的数据页已经满了,根据B+树的算法,这时候需要申请一个新的数据页,然后挪动部分数据过去

这个过程就叫页分裂

在这种情况下,性能自然会受影响。

除了性能外,页分裂操作还影响数据页的利用率。原本放在一个页的数据,现在分到两个页中,整体空间利用率降低大约50%。

当然有分裂就有合并。当相邻两个页由于删除了数据,利用率很低之后,会将数据页做合并。合并的过程,可以认为是分裂过程的逆过程。

我们可能在平常建表规范中遇到一条规定

建表语句中移动要有自增主键

那么,我们来分析一下这条规定是否适用于所有情况

定义自增主键:NOT NULL PRIMARY KEY AUTO_INCREMENT

而自增主键就是插入新记录的时候可以不指定ID的值,系统会获取当前ID最大值加1作为下一条记录的ID值

当我们遇到需要递增插入的场景时,自增主键的插入数据模式是非常符合这一场景的.即每次插入一条新纪录,都是追加操作,都不涉及挪动其他记录,也不会触发叶子节点的分裂

但是业务逻辑里面的某些字段做主键,往往不容易保证有序插入,那么这样写数据的成本相对较高

除了考虑性能外,我们还需要存储空间的角度来看

由于每个非主键索引的叶子节点上都是主键的值.

  • 若身份证号做主键,那么每个二级索引的叶子节点占用约20个字节,而如果用整型做主键,则只要4个字节,如果是长整型(bigint)则是8个字节

显然,主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。

所以,从性能和存储空间方面考量,自增主键往往是更合理的选择。

有没有什么场景适合用业务字段直接做主键的呢?还是有的。比如,有些业务的场景需求是这样的:

  1. 只有一个索引
  2. 该索引必须是唯一索引

你一定看出来了,这就是典型的KV场景。

由于没有其他索引,所以也就不用考虑其他索引的叶子节点大小的问题

这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则,直接将这个索引设置为主键,可以避免每次查询需要搜索两棵树

索引增删

索引可能因为删除,或者页分裂等原因,导致数据页有空洞,重建索引的过程会创建一个新的索引,把数据按顺序插入,这样页面的利用率最高,也就是索引更紧凑、更省空间

如果我们要重建上面提到索引k,那么我们的SQL语句是这样的

1
2
alter table T drop index k;
alter table T add index(k);

如果是主键的话,也可以这样写

1
2
alter table T drop primary key;
alter table T add primary key(id);

上面这么写是否合理呢

其实重建主键的过程不合理。不论是删除主键还是创建主键,都会将整个表重建。所以连着执行这两个语句的话,第一个语句就白做了。这两个语句,你可以用这个语句代替 : alter table T engine=InnoDB

参考

https://time.geekbang.org/column/intro/139

CATALOG
  1. 1. MySQL-索引笔记(上)
    1. 1.1. 索引的常见模型
      1. 1.1.1. 哈希表
      2. 1.1.2. 有序数组
      3. 1.1.3. 搜索树
      4. 1.1.4. N叉树
    2. 1.2. InnoDB的索引模型
    3. 1.3. 索引维护
    4. 1.4. 索引增删
    5. 1.5. 参考