数据库索引 cheatsheet

索引页和表页

表和索引都被存储在页中，页大小一般4KB。当表和索引被加载或重组时，每个页都会预留一定比例的空闲空间，满足添加新数据的需求。

索引行

• 唯一索引，一个索引行等同于叶子页中的一个索引条目，字段的值从表中复制到索引，并加上一个指向表中记录的指针。
• 非唯一索引，多数情况下，其存储方式是一个值后带多个指针。

索引结构

B树，非叶子页通常包含一个（可能被截断的）键值，以及一个指向下一级页的指针，该键值是下层级页中的最大键值。

表行

表中记录的顺序按照表中某一索引的顺序来组织，使用其他索引访问时，索引的处理有序且高效，但表的处理确实随机且低效的。

缓冲池和磁盘I/O

索引和表页在不在缓冲池中，访问成本是不同的。它的理想位置在数据库缓冲池中，其次是磁盘服务器的读缓冲区中，否则会从磁盘进行读取，其过程可能要花费很长时间等待磁盘设备空闲下来。

如果一个表的行不是特别长，那么可以考虑将所有的列负责到索引上，以加快select的执行速度，如产表就变得冗余了。有些DBMS有去除多余表的选项，其索引的叶子页用于存储表行。

• oracle中，该选项被称为索引组织表，包含表行的索引被称为主键索引。
• sql server中，选项clustered创建一个存储表行的索引。

以上两种环境中，其余索引（oracle中为次级索引，sql server为非聚集索引）都指向包含表行的那个索引。

DB2（z/OS，LUW，VM和VSE）

聚簇索引指定义了新插入的表行所在表页的索引。如果索引行的顺序和表行的顺序之间具有强关联性，那么就可以说该索引是聚集的。一张表上只能有一个聚簇索引，但可能有多个索引是聚集的。

索引的聚簇比例（clusterratio）指索引行和表行顺序之间关联度的一个量度，优化器会用此指来估算I/O时间。

DB2的表上通常都有一个聚簇索引。

sql server

存储表行的索引被称为聚集的，只有当需要一张索引组织表时才定义一个聚集索引。

oracle

聚簇一词被用于代表将多个表的行交错存储（聚簇的表）的选项。

I/O时间

顺序扫描的CPU时间

三星索引，一次查询通常只需要一次磁盘随机读取及一次窄索引片的扫描，其响应时间会比一个普通索引的响应时间少几个数量级。

星级评定的标准：

• 一个查询相关的索引行是相邻的，或者至少相距足够靠近
• 索引行的顺序与查询语句的需求一致
• 索引行包含查询语句中的所有列

第三颗星通常是最重要的，至少包含了第三颗星的索引称为对查询语句的宽索引。

• 取出对于优化器来说不过分复杂的等值谓词列，将其作为索引的前导列（任意顺序皆可）。
• 如果存在，将选择性最好的范围谓词作为索引下一列。只考虑对优化器不过分复杂的范围谓词即可。
• 以正确的顺序条件order by列（注意正逆序）。忽略前面步骤中已添加的列。
• 以任意顺序将selelct语句中其余的列添加到索引中（但要以不易变的开始）。

如果候选A引起了排序操作，可以考虑候选B，其第二颗星比第一颗星更重要。

• 取出对于优化器来说不过分复杂的等值谓词列，将其作为索引的前导列（任意顺序皆可）。
• 以正确的顺序条件order by列（注意正逆序）。忽略前面步骤中已添加的列。
• 以任意顺序将selelct语句中其余的列添加到索引中（但要以不易变的开始）。

• 基本问题法（Basic Question，BQ）
• 快速上限估算法（Quick Upper-Bound Estimate，QUBE）

是否存在包含了where子句所有列（半宽索引）：

• 否，考虑将缺少的谓词列加到一个现有索引上。保证过滤条件本身不回表，只有匹配后查询数据才回表。
• 如果还是不理想，考虑索引中添加所有列，产生一个宽索引，不需要回表。
• 如果select还是很慢，使用候选A/B来设计一个新的索引。

BQ并不能最终保证足够好的性能，但是保证了最小化对表的访问。

QUBE方法是悲观的，可能会误报，但不会像BQ那样漏掉发现某些问题。其输出结果是本地响应时间（LRT），即在数据库中的耗时，包括以下：

• 服务时间
• CPU时间
• 磁盘服务时间（同步读、同步写、异步读）
• 排队时间
• CPU时间
• 磁盘排队
• 锁等待
• 其他等待

LRT = TR * 10ms + TS * 0.01ms + F * 0.1ms

LRT = 本地响应时间
TR  = 随机访问时间
TS  = 顺序访问时间
F   = 有效FETCH的数量

主键索引访问

LRT = 2 * 10ms + 0.1ms ≈ 20ms

聚簇索引访问

预设读取1000条数据，假设索引列有二级能命中，且表中1000数据相邻

LRT = 2 * 10ms + 1999 * 0.01ms + 1000 * 0.1ms ≈ 140ms

如果不是相邻的数据依旧会变成1000次随机读取，时间接近10s，如果取10条数据，耗时0.5s左右还是可以接受。

非聚簇索引访问

非聚簇索引会导致1000次回表的随机访问，时间接近10s (1000 * 10ms)，如果是三星索引不回表，还是在0.1s左右。