以下内容是读《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值可能是不同的。