以下内容是读《MySQL技术内幕:InnoDB存储引擎》,笔记摘要。

1. 介绍

B+树索引的本质就是B+树在数据库中的实现,而B+树索引在数据库中的一个特点就是高扇出性。例如在InnoDB存储引擎中,每个页的大小为16KB。

在数据库中,B+树的高度一般都在2~4层,这意味着查找某一键值最多只需要2到4次IO操作,这还不错。因为现在一般的磁盘每秒至少可以做100次IO操作,2~4次的IO操作意味着查询时间只需0.02~0.04秒

2. InnoDB B+树索引

在MySQL数据库中,索引是在存储引擎层实现的,这意味着每个引擎的B+树索引的实现方式可能是不同的,取决于存储引擎实现的本身。

InnoDB存储引擎中,数据文件本身就是按照B+树方式存放数据的。其中,B+树的键值为主键,若在建立时没有显式地指定主键,**则InnoDB存储引擎会自动创建一个6字节的列作为主键(rowId)**。因此在InnoDB存储引擎中,可以将B+树索引分为聚集索引和辅助索引(非聚集索引)。无论是何种索引,每个页的大小都为16KB,且不能更改。

2.1 聚集索引和辅助索引的区别

聚集索引与辅助索引,底层数据结构都是B+树,区别仅在于所存放数据的内容:

  • 聚集索引是根据主键创建的一棵B+树,聚集索引的叶子节点存放了表中的所有记录。
  • 辅助索引是根据索引键创建的一棵B+树,与聚集索引不同的是,其叶子节点仅存放索引键值,以及该索引键值指向的主键。

如果通过辅助索引来查找数据,那么当找到辅助索引的叶子节点后,很有可能还需要根据主键值查找聚集索引来得到数据,这种查找方式又被称为回表。因为辅助索引不包含行记录的所有数据,这就意味着每页可以存放更多的键值,因此其高度一般都要小于聚集索引。

2.2 聚集索引和辅助索引B+树图

非聚集索引

image-20211018223002438

3. MyISAM B+树索引

MyISAM存储引擎其实更像一张堆表,其特点整理如下:

  • 所有的行数据都存放于MYD文件中,
  • 其B+树索引都是辅助索引,存放于MYI文件中。
  • 主键索引和其他索引不同之处在于其必须是唯一的,并且不可为NULL值。
  • 其索引页的大小默认为1KB,同样不可以进行调整。

与InnoDB存储引擎不同的是,因为没有聚集索引,其索引叶节点存放的键值不是主键值,而是在MYD文件中的物理位置。

MyISAM存储引擎MYD与MYI之间的关系

4. 索引添加规则

4.1 高选择性和低选择性

并不是所有在查询条件中出现的列都需要添加索引。对于什么时候添加B+树索引,一般的经验是,在访问表中很少一部分行时使用B+树索引才有意义,对于性别字段、地区字段、类型字段,它们可取值的范围很小,称为低选择性。例如下面这条SQL:

select * from student where sex='M'

按性别进行查询时,可取值的范围一般只有“M”和“F”,因此上述SQL语句得到的结果可能是该表50%的数据(我们假设男女比例1:1),这时添加B+树索引是完全没有必要的。

如果某个字段的取值范围很广,几乎没有重复,即是高选择性的,那么此时使用B+树索引是最适合的。例如手机号字段。

4.2 查看索引是否高选择性(Cardinality)

怎样查看索引是否是高选择性的呢?

# 通过SHOW INDEX语句中的`Cardinality`列来观察
show index from tableName

示例图

Cardinality/总条数 应该尽可能接近1,如果非常小,那么需要考虑是否还要建这个索引。需要注意的是, Cardinality是一个预估值,而不是一个准确值。

4.3 InnoDB存储引擎怎样统计Cardinality

在生产环境中,索引的更新操作可能非常频繁。如果在每次索引发生更新操作时就对其进行Cardinality的统计,那么将会给数据库带来很大的负担。另外需要考虑的是,如果一张表的数据量非常大,比如一张表有50GB的数据,那么统计一次Cardinality信息所需要的时间可能非常长。这在生产环境的应用中也是不能接受的。因此,数据库对于Cardinality的统计都是通过采样的方法来完成的。

a. 更新Cardinality信息的策略

在InnoDB存储引擎中,Cardinality统计信息的更新发生在两个操作中:INSERT和UPDATE。

根据前面的叙述,不可能在每次发生INSERT和UPDATE时都去更新Cardinality的信息,这会增加数据库系统的负荷,同时对大表进行统计时,时间上也不允许。因此InnoDB存储引擎对于更新Cardinality信息的策略为:

  • 表中1/16的数据已发生变化。
  • 发生变化的次数stat_modified_counter > 2000000000。

b. 更新Cardinality信息的策略

InnoDB存储引擎内部通过采样的方法,只对8个叶节点进行采样。采样的过程为:

  • 取得B+树索引中叶节点的数量,即为A
  • 随机取B+树索引中的8个叶节点。统计每个页不同记录的个数,即为P1,P2,…,P8。
  • 根据采样信息给出Cardinality的预估值:Cardinality=(P1+P2+…+P8)*A/8

通过上述的说明可以发现,在InnoDB存储引擎中,Cardinality的值是通过对8个叶节点预估而得到的,不是一个精确的值。再者,每次对于Cardinality值的统计都是通过随机读取8个叶子节点得到的,这又暗示了另一个Cardinality的现象,即每次得到的Cardinality值可能是不同的。