数据库索引

default

数据库索引

数据结构与算法--索引 https://url.wx-coder.cn/O07eI 一节中,我们讨论了 B+Tree, LSM-Tree 这样的文件索引以及全文索引的基础算法,本文则会针对文件索引在关系型数据库中的实际应用进行探讨。

索引(Index)是帮助数据库系统高效获取数据的数据结构,而数据库索引本质上是以增加额外的写操作,与用于维护索引数据结构的存储空间为代价的,用于提升数据库中数据检索效率的数据结构。索引可以帮助我们快速地定位到数据而不需要每次搜索的时候都遍历数据库中的每一行。当然,索引不是建立的越多、越长越好,因为索引除了占用空间之外,对后续数据库的增加、删除、修改都有额外的操作来更新索引。一般来说,小表使用全表扫描更快,中大表才使用索引,而超级大表索引基本无效,我们可能需要借助独立的全文索引系统;MySQL 自带的全文索引只能用于 InnoDB、MyISAM ,并且只能对英文进行全文检索,一般使用 ES,Solr 这样的全文索引引擎。

索引类型

从索引的实现上,我们可以将其分为聚集索引与非聚集索引,或称辅助索引或二级索引,这两大类;从索引的实际应用中,又可以细分为普通索引、唯一索引、主键索引、联合索引、外键索引、全文索引这几种。

InnoDB 可以看做是聚集索引,因为它的 B+ 树的叶结点包含了完整的数据记录。InnoDB 的数据文件本身就是索引文件,表数据文件本身就是按 B+Tree 组织的一个索引结构,这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键,因此 InnoDB 表数据文件本身就是主索引。InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说,InnoDB 的所有辅助索引都引用主键作为 data 域。

而 MyISAM 方式 B+ 树的叶结点只是存储了数据的地址,故称为非聚集索引。MyISAM 引擎使用 B+Tree 作为索引结构,叶节点的 data 域存放的是数据记录的地址;在 MyISAM 中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求 key 是唯一的,而辅助索引的 key 可以重复。

在 InnoDB 中,又有聚簇索引和普通索引之分,聚簇索引根据主键来构建,叶子节点存放的是该主键对应的这一行记录,根据主键查询可以直接利用聚簇索引定位到所在记录。而普通索引根据申明这个索引时候的列来构建,叶子节点存放的是这一行记录对应的主键的值,根据普通索引查询需要先在普通索引上找到对应的主键的值,然后根据主键值去聚簇索引上查找记录,俗称回表。如果我们查询一整行记录的话,一定要去聚簇索引上查找,而如果我们只需要根据普通索引查询主键的值,由于这些值在普通索引上已经存在,所以并不需要回表,这个称为索引覆盖,在一定程度上可以提高查询效率。

普通索引中还有唯一索引和联合索引两个特例,唯一索引在插入和修改的时候会校验该索引对应的列的值是否已经存在,联合索引将两个列的值按照申明时候的顺序进行拼接后在构建索引。

数据行并不是存储引擎管理的最小存储单位,索引只能够帮助我们定位到某个数据页,每一次磁盘读写的最小单位为也是数据页,而一个数据页内存储了多个数据行,我们需要了解数据页的内部结构才能知道存储引擎怎么定位到某一个数据行,可以参考 MySQL 存储管理 https://url.wx-coder.cn/IF5HH 系列。

索引选择性

对索引列和字符串前缀长度,都参考选择性(Selectivity)这个指标来确定:选择性定义为不重复的索引值和数据总记录条数的比值,其选择性越高,那么索引的查询效率也越高,譬如对于性别这种参数,建立索引根本没有意义。

Index Selectivity = Cardinality / #T

显然选择性的取值范围为 (0, 1],选择性越高的索引价值越大,这是由 B+Tree 的性质决定的。在实际的数据库中,我们可以通过以下语句来计算某列的选择性:

SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM titles;

主键

在 InnoDB 内部,表数据是优化主键快速查询而排列分布的,其查找速度是最快的,该索引中键值的逻辑顺序决定了表中相应行的物理顺序。即使表中没有适合做主键的列,也推荐采用一个自动增长的整数主键(代理键),那么这个表在增加数据的时候是顺序存放的,而且后续在别的表参考该外键查询的时候也会得到优化。

如果在创建表时没有显式地定义主键(Primary Key),则 InnoDB 存储引擎会按如下方式选择或创建主键:

  • 首先表中是否有非空的唯一索引(Unique NOT NULL),如果有,则该列即为主键。

  • 不符合上述条件,InnoDB 存储引擎自动创建一个 6 个字节大小的指针,用户不能查看或访问。

主键的选择

分布式 ID https://url.wx-coder.cn/tQ5eH 一文中我们讨论过分布式场景下的分布式 ID 的选择策略,而在数据库中,我们同样会有这样的考量。首先,MySQL 官方有明确的建议主键要尽量越短越好,36 个字符长度的 UUID 不符合要求;如果主键是一个很长的字符串并且建了很多普通索引,将造成普通索引占有很大的物理空间。并且主键最好是顺序递增的,否则在 InnoDB 引擎下,UUID 的无序性可能会引起数据位置频繁变动,严重影响性能。

自增 ID 在插入的时候可以保证相邻的两条记录可能在同一个数据块,而订单号这样的业务相关的连续性设计上可能没有自增 ID 好,导致连续插入可能在多个数据块,增加了磁盘读写次数。

  • 唯一性:自增 ID 很容易会被暴力破解,数据迁移的时候,特别是发生表格合并这种操作的时候,会不可避免地存在冲突。UUID 则能够保证唯一性,彻底避免冲突。

  • 键长度:自增字段的长度较 UUID 小很多,这会对检索的性能有较大影响。Innodb 引擎进行数据检索时,也是先根据索引找到主键,然后根据主键找到记录;这样在主键长度短的情况下,会有较好的读性能。

  • 并发性:自增 ID 并且高并发的情况下,竞争自增锁会降低数据库的吞吐能力。UUID 则能够在应用层生成 UUID,提高数据库的吞吐能力。

  • 数据库索引:InnoDB 中表数据是按照主键顺序存放的,在写入数据时候如果发生了随机 IO,那么就会频繁地移动磁盘块。当数据量大的时候,写的短板将非常明显。自增 ID 中新增的数据可以默认按序排列,对于性能有很大的提升;UUID 则主键之间没有顺序规律。

主键与唯一索引

主键就是唯一索引,但是唯一索引不一定是主键,唯一索引可以为空,但是空值只能有一个,主键不能为空。对于单列索引,要求该列所有数据都不相同,但允许有 NULL 值;对于多列的联合索引,要求这些列的组合是唯一的。唯一索引其本身既可以作为索引,实际中也可以用以产生数据约束,防止增加或者修改后产生相同数据,从而保证数据的完整性。

对于字符串类型,可以指定索引前缀长度(且对于 BLOB/TEXT 前缀长度参数是必须的),在 InnoDB 表中其前缀长度最长是 767 bytes,且参数 M 是用 bytes 计量的。所以太长的字符串,建立 B+Tree 索引浪费比较大,这时候用手动模拟 HASH 索引是个方法,不过这种方式对字符串无法灵活的使用前缀方式查询(例如 LIKE 这类的操作)。

联合索引

单列索引指的是在表上为某一个字段建立的索引,一般索引的创建选择整型或者较小的定长字符串将更有利于效率的提升。联合索引指的是多个字段按照一定顺序组织的索引。以索引 (name, city, gender) 为例,其首先是按照 name 字段顺序组织的,当 name 字段的值相同时(如 Bush),其按照 city 字段顺序组织,当 city 字段值相同时,其按照 gender 字段组织。由于联合索引上通过多个列构建索引,有时候我们可以将需要频繁查询的字段加到联合索引里面,譬如经常需要根据 name 查找 age 我们可以建一个 name 和 age 的联合索引。

常见的条件联合包括了 WHERE 条件联合与 ORDER BY 条件联合;所谓 WHERE 条件联合指的是,对于 WHERE 条件中的等值条件,其字段使用与联合索引的字段一致(顺序可以不一致)。

ORDER BY 联合指的是如果 ORDER BY 后面的字段是联合索引覆盖 where 条件之后的一个字段,由于索引已经处于有序状态,MySQL 就会直接从索引上读取有序的数据,然后在磁盘上读取数据之后按照该顺序组织数据,从而减少了对磁盘数据进行排序的操作。即对于未覆盖 ORDER BY 的查询,其有一项 Creating sort index,即为磁盘数据进行排序的耗时最高;对于覆盖 ORDER BY 的查询,其就不需要进行排序,而其耗时主要体现在从磁盘上拉取数据的过程。

前缀索引

MySQL 的前缀索引可以分为三类:联合索引前缀,like 前缀和字符串前缀。

联合索引前缀与最左匹配(Leftmost Prefix)

联合索引前缀指的是在建立多列索引的时候,必须按照从左到右的顺序使用全部或部分的索引列,才能充分的使用联合索引,比如:(col1, col2, col3) 使用 (col1)、(col1, col2)、(col1, col2, col3) 有效。在查询语句中会一直向右匹配直到遇到范围查询 (>,<,BETWEEN,LIKE) 就停止匹配,其后的索引列将不会使用索引来优化查找了。

(name, city, interest) 三个字段联合的索引为例,如果查询条件为 where name='Bush'; 那么就只需要根据 B+树定位到 name 字段第一个 Bush 所在的值,然后顺序扫描后续数据,直到找到第一个不为 Bush 的数据即可,扫描过程中将该索引片的数据 id 记录下来,最后根据 id 查询聚簇索引获取结果集。同理对于查询条件为 where name='Bush' and city='Chicago'; 的查询,MySQL 可以根据联合索引直接定位到中间灰色部分的索引片,然后获取该索引片的数据 id,最后根据 id 查询聚簇索引获取结果集。

由此我们可以得出联合索引前缀的注意点:

  • 无法跨越字段使用联合索引,如 where name='Bush' and interest='baseball';,对于该查询,name 字段是可以使用联合索引的第一个字段过滤大部分数据的,但是对于 interest 字段,其无法通过 B+ 树的特性直接定位第三个字段的索引片数据,比如这里的 baseball 可能分散在了第二条和第七条数据之中。最终,interest 字段其实进行的是覆盖索引扫描。

  • 对于非等值条件,如 >、<、!= 等,联合索引前缀对于索引片的过滤只能到第一个使用非等值条件的字段为止,后续字段虽然在联合索引上也无法参与索引片的过滤。这里比如 where name='Bush' and city>'Chicago' and interest='baseball';,对于该查询条件,首先可以根据 name 字段过滤索引片中第一个字段的非 Bush 的数据,然后根据联合索引的第二个字段定位到索引片的 Chicago 位置,由于其是非等值条件,这里 MySQL 就会从定位的 Chicago 往下顺序扫描,由于 interest 字段是可能分散在索引第三个字段的任何位置的,因而第三个字段无法参与索引片的过滤。

因此 B-Tree 的列顺序非常重要,上述使用规则都和列顺序有关。对于实际的应用,一般要根据具体的需求,创建不同列和不同列顺序的索引。假设有索引 Index(A,B,C):

# 使用索引
A>5 AND A<10 - 最左前缀匹配
A=5 AND B>6 - 最左前缀匹配
A=5 AND B=6 AND C=7 - 全列匹配
A=5 AND B IN (2,3) AND C>5 - 最左前缀匹配,填坑
# 不能使用索引
B>5 - 没有包含最左前缀
B=6 AND C=7 - 没有包含最左前缀
# 使用部分索引
A>5 AND B=2 - 使用索引 A 列
A=5 AND B>6 AND C=2 - 使用索引的 A 和 B 列

使用索引对结果进行排序,需要索引的顺序和 ORDER BY 子句中的顺序一致,并且所有列的升降序一致(ASC/DESC)。如果查询连接了多个表,只有在 ORDER BY 的列引用的是第一个表才可以(需要按序 JOIN)。

# 使用索引排序
ORDER BY A - 最左前缀匹配
WHERE A=5 ORDER BY B,C - 最左前缀匹配
WHERE A=5 ORDER BY B DESC - 最左前缀匹配
WHERE A>5 ORDER BY A,B - 最左前缀匹配
# 不能使用索引排序
WHERE A=5 ORDER BY B DESC,C ASC - 升降序不一致
WHERE A=5 ORDER BY B,D - D 不在索引中
WHERE A=5 ORDER BY C - 没有包含最左前缀
WHERE A>5 ORDER BY B,C - 第一列是范围条件,无法使用 BC 排序
WHERE A=5 AND B IN(1, 2) ORDER BY C - B 也是范围条件,无法用 C 排序

like 前缀

对于 like 前缀,其是指在使用 like 查询时,如果使用的表达式为 first_name like 'rMq%';那么其是可以用到 first_name 字段的索引的。但是对于 first_name like '%Chu%';,其就无法使用 first_name 的索引。对于 like 前缀,MySQL 底层实际上是使用了一个补全策略来使用索引的,比如这里 first_name like 'rMq%';,MySQL 会将其补全为两条数据:rMqAAAAA 和 rMqzzzzz,后面补全部分的长度为当前字段的最大长度。在使用索引查询时,MySQL 就使用这两条数据进行索引定位,最后需要的结果集就是这两个定位点的中间部分的数据。如下是使用 like 前缀的一个示意图:

字符串前缀

字符串前缀索引指的是只取字符串前几个字符建立的索引。在进行查询时,如果一个字段值较长,那么为其建立索引的成本将非常高,并且查询效率也比较低,字符串前缀索引就是为了解决这一问题而存在的。字符串前缀索引主要应用在两个方面:

  • 字段前缀部分的选择性比较高;

  • 字段整体的选择性不太大(如果字段整体选择性比较大则可以使用哈希索引)。

譬如为 first_name 字段建立了长度为 4 的前缀索引,可以看到,如果查询使用的是 where first_name='qWhNIZqxcbD';,那么 MySQL 首先会截取等值条件的前四个字符,然后将其与字符串前缀索引进行比较,从而定位到前缀为"qWhN"的索引片,然后获取该索引片对应的磁盘数据,最后将获取的磁盘数据的 first_name 字段与查询的等值条件的值进行比较,从而得到结果集。

字符串前缀索引最需要注意的一个问题是如何选择前缀的长度,长度选择合适时,前缀索引的过滤性将和对整个字段建立索引的选择性几乎相等。这里我们就需要用到前面讲解的关于字段选择性的概念,即字段选择性为对该字段分组之后,数据量最大的组的数据量占总数据量的比例。这里选择前缀长度时,可以理解为,前缀的选择性为按照前缀分组之后,数据量最大的组占总数据量的比例。如下表所示为计算前缀长度的 SQL 公式:

select count(*) as cnt, first_name as perf from actor group by perf ORDER BY cnt desc limit 10; -- 0
select count(*) as cnt, left(first_name, 2) as perf from actor group by perf ORDER BY cnt desc limit 10; -- 2
select count(*) as cnt, left(first_name, 3) as perf from actor group by perf ORDER BY cnt desc limit 10; -- 3
select count(*) as cnt, left(first_name, 4) as perf from actor group by perf ORDER BY cnt desc limit 10; -- 4

其他索引

覆盖索引

覆盖索引指的是对于查询中使用的除去参与索引过滤扫描的所有字段将其加入到该查询所使用的索引尾部的索引。覆盖索引扫描的优点在于由于查询中所使用的所有字段都在同一索引的字段,因而在进行查询时只需要在索引中获取相关数据即可,而不需要回磁盘扫描相应的数据,从而避免了查询中最耗时的磁盘 I/O 读取。对于如下查询:

select a, b, c from t where a='a' and b='b';

该查询中如果建立联合索引(a, b, c),那么这就是使用了覆盖扫描的索引,因为对于该查询,可以使用索引的前两个字段 a 和 b 根据 where 条件进行索引片的过滤,对过滤后的索引片直接在索引中读取 a, b, c 三个字段的值即可,而无需回表扫描。

三星索引

三星索引指的是对于一个查询,设立了三个通用的索引条件满足的条件,建立的索引对于特定的查询每满足一个条件就表示该索引得到一颗星,当该索引得到三颗星时就表示该索引对于该查询是一个三星索引。三星索引是对于特定查询的最优索引,建立三星索引的条件如下:

  • 取出所有的等值谓词的列 (WHERE COL=…) 作为索引开头的列;

  • 将 ORDER BY 中的列加入到索引中;

  • 将查询语句中剩余的列加入到索引中,将易变得列放到最后以降低更新成本。

譬如对于如下的查询,索引 (first_name, last_name, email) 就是一个三星索引:

SELECT first_name, last_name, email FROM user WHERE first_name = 'aa' ORDER BY last_name;

三星索引的创建过程可以发现如下规律:

  • 覆盖等值谓词条件,如 first_name,可以过滤大部分的索引片数据;

  • 覆盖 order by 字段可以避免对结果集的排序,如 last_name;

  • 覆盖其余字段可以避免回磁盘读取数据,即使用了覆盖索引扫描,如 email。

链接