本文内容来自 YashanDB 官网，原文内容请见 https://doc.yashandb.com/yashandb/23.3/zh/%E6%A6%82%E5%BF%B5%E6%89%8B%E5%86%8C/%E5%85%B3%E7%B3%BB%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%A8%A1%E5%BC%8F%E5%AF%B9%E8%B1%A1/%E7%B4%A2%E5%BC%95.html

索引概述

在一个数据库系统中，索引是一个独立对象，是表的一个可选结构，是表数据的子集（只包含部分列数据）。

索引数据是有序的，给表创建合适的索引相当于给表创建了一个目录，可以提高该表关于索引列的访问效率。适合创建索引的列的特征如下：

• 列会被频繁查询

• 列经常作为查询条件

• 外键列（在外键列上创建索引，可以避免操作父表带来的子表的排他锁，而是改为共享锁）

• 需要保持唯一的列（可以创建唯一索引）

优点

• 减少 I/O 开销

• 表的数据是随机存储的，如果表上没有索引，查询需要执行全表扫描才能获取结果，这意味着数据库需要访问这个表的每个数据块，从而带来大量的 I/O 开销。

• 提高查询速度

• 若在表的某一列或某几列上创建了索引，执行关于该索引列或包含索引列过滤的查询时，只需基于索引在随机分布的表中检索小部分数据块（甚至可能不需要检索数据块）便可快速获得查询结果。

缺点

• 额外的空间开销

• 索引是一个独立对象，创建索引会带来额外的空间开销。

• 增加 DML 语句的执行开销

• 可能的性能损失

• 创建合适的索引可以带来业务的极大性能提升，但如果滥用索引，则可能会导致业务性能下降。

# 索引的可用性和可见性

可用性

索引可以是可用 usable 的（默认值），也可以是不可用 unusable 的。

YashanDB 在 DML 操作中不维护不可用索引，且优化器也不会选择不可用索引执行查询操作。

当一个索引从可用状态变更为不可用状态时，YashanDB 会把这个索引对应的 segment 删除，即不可用索引不会占用物理空间。

不可用索引或索引分区可以通过 rebuild 语句调整状态为可用。

通常，在导入大表时，先将索引设置为不可用状态待导入完成后再 rebuild 使其可用，可以提高导入性能。

ALTER INDEX idxtest UNUSABLE;ALTER INDEX idxtest REBUILD;

Copied!

可见性

索引可以是可见 visible 的（默认值），也可以是不可见 invisible 的。

YashanDB 在 DML 操作中依然维护不可见索引，但优化器不会选择不可见索引执行查询操作。

在调整业务时，可以通过设置索引的可见性来测试索引对业务性能的影响。

ALTER INDEX idxtest INVISIBLE;ALTER INDEX idxtest VISIBLE;

Copied!

# 唯一索引和非唯一索引

创建索引时可以设置索引的唯一性。

唯一索引：要求索引列的每个值唯一，即不允许重复值（NULL 除外，YashanDB 会将索引列全 NULL 的行也存入索引），通常按照索引列排序，如果唯一索引列全 NULL 则按照 RowId 排序。

非唯一索引：不要求值的唯一性，在索引值不同时按照索引列排序，索引列值相同时则按照 RowId 排序。

# 索引的存储

索引是一个独立对象，有单独的 segment。索引 segment 的表空间默认是索引所有者的默认表空间，在创建索引或重建索引时，可以自定义指定索引的表空间。

索引中的行与表一一对应，用于存储索引列的值以及对应表中的行 RowId，索引严格按照索引列的值（值相同时按照 RowId 的值）有序存储。

# 索引的维护

索引是表的一个可选结构，跟随表的变动而变动：

• 当表插入一行数据，索引也在合适位置插入一行数据（只存储索引列）。

• 当表删除一行数据，索引也删除对应行数据。

• 当表没有更新索引列时，索引不需要维护。

• 当表更新索引列时，为了保持索引的有序性，索引不能像表那样在原位更新，而是先删除老数据构造的索引行然后在合适的位置插入新值构造的索引行。

BTree 索引

BTree 索引通过维护一个 B 树数据结构来保持索引的有序性。

在 YashanDB 中，数据块是物理存储的最小单元，BTree 索引在单个数据块中存储的索引行是有序的，不同的数据块之间也是有序的，从而确保了整个 BTree 索引是有序的。

# 分支块和叶子块

BTree 索引存在两种数据块：存储索引列数据的叶子块和存储路由信息（用户查找）的分支块。

• 叶子块：存储索引列的值以及对应表中的 RowId，叶子块之间使用双向链表串联。

• 分支块：存储指向其下层数据块的指针，以及对应下层数据块的数据大小信息。最顶层的分支块又称根分支块。

BTree 索引是一个平衡树，所有叶子块都处在同一深度（通常，叶子块所处的层级称为 level 0，比叶子块高一层的分支块为 level 1，以此类推）。从根分支块访问任意叶子块需经历的块的个数（称为 BTree 索引的高度）是相等的，即根分支块的层级 = B 树高度 - 1。同时，也意味着查找任意索引列数据需要消耗的时间几乎相同。

# 索引扫描

假设某个 YashanDB 数据库中 BTree 索引的高度是 h，通过 B 树的结构可知，对于任意索引列数据，最多只需访问 h 个数据块便可检索到所需数据。如需获取该数据所在行的非索引列数据（即采用索引列作为查询的过滤条件），则再额外访问 1 个数据块。

当采用索引列作为查询的过滤条件时，YashanDB 可以通过索引来加速查找。如果待查询的数据本身就是索引列时，则只需在索引数据块中查询即可快速获取数据。

# 全索引扫描（Index Full Scan）

当一个查询需要扫描一个表的所有数据，同时需要使用索引列的前导列排序，YashanDB 会执行全索引扫描。全索引扫描相当于从索引的最左侧叶子块扫描到最右边叶子块（或从最右边叶子块扫描到最左边叶子块）。

假设有表 idxtest，其上建有 a 列的索引，如下的查询会执行全索引扫描。

SELECT a FROM idxtest ORDER BY a;

Copied!

全索引扫描利用索引的有序性，可直接跳过排序的过程。

# 索引快速全扫描（Index Fast Full Scan）

在全索引扫描的基础上，如果扫描结果不需要有序，则 YashanDB 执行索引快速全扫描，例如 count(*)，sum()等与顺序无关的扫描。

索引快速全扫描的特点是需要访问全表所有行，但只访问索引列数据，且不要求排序。

假设有表 idxtest，其上建有 a 列的索引，如下的查询会执行索引快速全扫描。

SELECT SUM(a) FROM idxtest；

Copied!

索引快速全扫描会根据索引数据块在物理存储的存储顺序去扫描数据（预读会加速索引快速全扫描）。

# 索引范围扫描（Index Range Scan）

当索引的前导列参与查询并且返回结果可能不止一条时，YashanDB 执行索引范围扫描。索引范围扫描会根据扫描设置的左边界，从根分支块定位到叶子块满足第一个条件的索引行，然后依次向右扫描，直到扫描出右边界。如果是降序扫描，则先定位右边界，然后向左扫描，直到扫描出左边界。

假设有表 idxtest，其上建有 a 列的索引，如下的查询会执行索引范围扫描。

SELECT * FROM idxtest WHERE a > 50 AND a < 1020;

Copied!

上述查询，YashanDB 会先定位 50（扫描左边界）在索引块的位置，然后依次向右扫描，直到索引列值超过 1020（扫描右边界）。

如果表 idxtest 上仅有 a 列，则上述扫描不需要额外的 IO 回表查询。如果表 idxtest 上不止 a 列一列，则上述扫描还需要对满足条件的每一行数据产生额外的依次 IO 回表查询。

# 索引唯一扫描（Index Unique Scan）

当过滤条件使用相等运算符，并且包含了唯一索引的所有列时，YashanDB 执行索引唯一扫描。索引唯一扫描要么扫描出一行数据，要么一行数据都扫描不到。

假设有表 idxtest，其上建有 a 列的唯一索引，如下的查询会执行索引唯一扫描。

SELECT * FROM idxtest WHERE a = 1000;

Copied!

执行上述扫描，YashanDB 在扫描到第一条 1000 后就会终止扫描（唯一索引保证了最多只可能存在一个 1000）。

# 索引跳跃扫描（Index Skip Scan）

当索引的前导列基数非常小（前导列的 distinct 值相比于全表行数非常小），如果查询的条件在索引前导列后面的索引列上，此时 YashanDB 执行索引跳跃扫描。

例如表 person 里有 gender 和 age 两列，并且有一个索引建在（gender，age）上，则select * from person where age = 30就会执行索引跳跃扫描。YashanDB 会先找到第一个（男，30），然后扫描直到扫描出 age = 30 这个条件，再重新定位边界到第一个（女，30），然后扫描直到扫描出 age = 30。

索引跳跃扫描相当于把扫描拆分成若干个索引范围扫描。

# 索引聚集因子

索引聚集因子描述了索引对应表数据块的有序程度，表数据越有序，索引聚集因子越小，扫描的代价越小。如果表数据完全按照索引的顺序分布，则索引聚集因子最小，值为表数据块的个数。

• 如果索引聚集因子比较高，则说明在大型索引范围扫描过程中，YashanDB 可能会需要执行较高数量的 I/O。

• 如果索引聚集因子比较低，则说明在大型索引范围扫描过程中，YashanDB 只需要执行较低数量的 I/O。

# 反向索引

反向索引也是 BTree 索引的一种，但是反向索引在存储值时，会按照字节序逆转后的结果存储（索引列顺序不变）。

按照字节序逆转后的值存储，索引分布的会更加离散。例如当使用自增列作为索引列时，业务总是插入更大的索引列值到索引中，删除的则都是较小的索引列值。如果使用正常的 BTree 索引，随着业务的进行，就会导致整个索引倾斜。但如果索引是反向索引，由于索引列值被按照字节序逆转，新插入的值就可以分散到整个 B 树的叶子块。

同时反向索引由于存储结构的变化，也丧失了普通 BTree 索引范围查询的能力。

# 升序索引和降序索引

默认情况下，YashanDB 创建索引会按照索引列值从小到大来进行存储，即默认为升序索引。例如create index ageIdx on teachers(age)，创建的索引会按照教师的年龄，从小到大进行存储。

YashanDB 还支持降序索引，通过指定索引列desc可创建降序索引。例如create index ageIdx on teachers(age desc)，创建的索引会按照教师的年龄，从大到小进行存储。

YashanDB 支持对组合索引的索引列分别设置升序或降序，例如create index nameAgeIdx on teachers(name asc, age desc)。创建的索引首先按照教师名字按照字典序升序存储，当教师名字相同时，按照教师年龄从大到小进行存储。

# 函数索引

YashanDB 支持用户基于函数，或者与基表相关某个或多个列的表达式来创建索引，此类索引称为函数索引。函数索引根据某一行上的数据以及计算函数或者表达式，计算出一个值存储到索引中。

# 函数索引的使用

如果定义一张表存储教师信息，包含基础工资，教师职称等，而教师的实际工资是基于基础工资和教师职称的一个表达式，此时可以创建一个基于基础工资列和教师职称列的函数索引，当查询教师实际工资时，可以使用该函数索引加速查询。

CREATE TABLE teachers(id INT, teachingAge INT, salary INT, title INT);CREATE INDEX payment ON teachers(salary * title);
SELECT * FROM teachers WHERE salary * title > 8000;

Copied!

当查询中包含了函数索引的表达式时，YashanDB 会在查询中使用函数索引。

# 函数索引的执行优化

当函数索引的表达式出现在 WHERE 语句中时，优化器就可以选择函数索引执行索引扫描算子（全索引扫描/索引快速扫描/索引范围扫描/索引唯一扫描/索引跳跃扫描）。此时函数索引的表达式就相当于表的一个虚拟列，优化器对该虚拟列索引的处理和对普通列索引的处理相同。