索引与查询计划

数据页与访问代价

数据库通常按页组织表和索引。一次查询即使只需要一行，也可能需要把包含该行的数据页读入缓冲区。若页面已经缓存，访问主要消耗内存带宽与处理器时间；若页面仍在外部存储，则还需承担存储访问代价。分析查询性能时，应分别说明行数、页数、缓存状态和输出数量。

设一个数据页大小为 $4096$ 字节，其中 $96$ 字节用于页头与管理信息，每条定长记录占 $100$ 字节，暂时忽略记录跨页和变长字段。每页最多容纳

条记录。含一百万条记录的表至少需要二万五千页。顺序扫描会依次读取这些页并判断过滤条件。这个模型适合比较页面访问数量；真实页面的空闲空间、行版本和压缩方式会改变实际占用。

索引保存用于查找的键及相应记录位置。它增加一条按键访问数据的路径，同时占用空间并增加写入维护。一次插入可能同时修改表页和多个索引页；键变化可能引发索引删除与插入。评估索引时，需要同时考虑读查询节省的工作与更新增加的工作。

B 树索引与范围定位

数据库中的有序索引通常使用多路平衡树。内部节点保存分隔键与子节点位置，叶节点保存有序索引项。经典 B+ 树把数据条目集中在叶层，叶之间有顺序连接，适合范围扫描。不同产品在叶项、重复键、压缩和并发修改上的组织有所差别，下面先用固定容量模型分析高度。

索引扇出

索引内部节点的扇出是它拥有的子节点数。若每个内部节点至多有 $f$ 个子节点，每个叶页至多存放 $l$ 个索引项，三层结构最多容纳 $f^2l$ 个索引项。这里的三层分别是根、内部节点和叶节点。

一百万条记录的索引高度

设索引有一百万个键，叶页每页容纳二百项，内部节点扇出为二百，所有页面按最大容量填充。先计算叶页数，再计算上一层页数，直到只剩一个根节点。

叶层需要 $1000000/200=5000$ 页，上一层需要 $5000/200=25$ 页，再上一层只需一个根，因此索引有三层，共 $5026$ 页。一次等值查找在冷缓存下读取根、一个内部页和一个叶页，共三次索引页访问。若目标记录在独立表页中，还需读取一次表页，总共四次页面访问。

如果根与内部层已经缓存，外部存储只需承担叶页和表页读取；若查询列已在索引中，并且引擎具备相应可见性判断条件，可能避免表页访问。这个例子给出指定填充率下的数量，实际树可能因分裂和留空拥有更多页。

范围查找先定位起始叶项，再顺序访问后续叶项。即使索引项彼此相邻，它们指向的表行也可能散布在许多数据页中。数据按相近键聚集时，一千条相邻记录可能只需少量表页；若分散存放，则可能访问接近一千个表页。这解释了为什么范围查询的代价同时依赖索引结构和表数据布局。

PostgreSQL 17 的索引类型文档说明 B 树适合等值和范围条件，哈希索引针对等值查找，还有面向其他数据结构的索引类型。索引选择应根据查询运算和数据类型确定，不能把一种索引的性质直接推广到所有索引实现。

选择率与扫描方式

选择率是满足条件的记录数与总记录数之比，记为 $s\in[0,1]$。条件只匹配少量记录时，索引定位通常能减少访问；条件匹配大部分表时，逐页顺序读取可能更经济。数据库优化器需要估计满足条件的行数、每次访问代价和可用缓存，再比较不同计划。

索引扫描与顺序扫描比较

某表含二万五千页。采用简化代价模型：顺序读取一页代价为一，随机读取一页代价为四，索引定位代价固定为十二。若条件匹配一百行，且每行位于不同表页，比较两种访问方式。

顺序扫描代价为二万五千；索引扫描代价为 $12+4\times100=412$，因此在这些假设下索引扫描较省。若匹配一万行且仍分散于一万个页面，索引扫描代价变为 $40012$，超过顺序扫描。这里的代价单位是用于比较的抽象量，不能直接解释为毫秒。

临界点由 $12+4k=25000$ 得到 $k=6247$，其中 $k$ 是需要随机访问的表页数。实际优化器还会计入索引叶扫描、处理器计算、重复页面访问和输出代价，所以这个临界值仅适用于题设模型。我们可以用它检查估算方向，再通过真实执行计划观察瓶颈。

多列索引的列顺序决定有序组织方式。例如 (department, score) 先按部门，再在部门内按分数排序。查询某部门且成绩超过阈值，能在部门对应区间内定位；单独按成绩筛选，则通常缺少同样连续的区间。具体优化器可能使用额外策略，因此应查看实际版本的计划，避免把经验规则当成所有引擎的绝对限制。

索引还受表达式、排序规则和类型转换影响。若查询对列做函数变换，而索引保存原列值，数据库可能无法直接利用原顺序。建立表达式索引或改写范围条件前，应先确认两种表达式在空值、时区和边界值下等价。只为了让计划显示索引而改变查询含义，会损坏结果。

连接计划与中间结果

嵌套循环连接为外层每一行寻找内层匹配，内层有合适索引且外层很小时尤其有用。哈希连接先为一侧建立哈希表，再用另一侧的键探测，适合等值条件。归并连接利用两侧按连接键排序的顺序逐段匹配，输入已有合适顺序时能减少额外排序。

三种方式都必须正确处理重复键。如果某个键在左侧出现 $a$ 次、右侧出现 $b$ 次，它就产生 $ab$ 对结果。中间结果膨胀可能比原表读取更昂贵，所以先筛选哪一侧、选择哪个连接顺序，会显著影响执行量。逻辑上相同的连接表达式可能对应多种物理计划。

内存不足时，排序或哈希连接可能把部分数据写入临时文件，再分批处理。页面访问模型因此需要加入临时读写。仅观察总行数不足以预测性能，还应关注行宽、连接键分布、并行工作量与数据倾斜。少数高频键可能占据大部分输出和处理时间。

执行计划的阅读顺序

执行计划通常呈树状，叶节点读取数据，上层节点完成连接、聚合或排序。我们先查看扫描对象和条件，再逐层比较预计输出行数与实际行数，最后检查耗时、循环次数和缓冲区访问。最上层的总耗时包含下层工作，因此不能把各层显示的总时间简单相加。

PostgreSQL 的 EXPLAIN 显示估计计划，EXPLAIN ANALYZE 会真正执行语句并采集结果。对于会修改数据的语句，执行分析同样会产生修改；需要在受控测试数据上使用，并考虑事务回滚无法撤销的外部副作用。性能检查先保证查询正确，再确认测量所处的缓存和并发条件。

估计与实际行数差距很大时，可以检查统计信息是否陈旧、列之间是否相关、过滤值是否罕见。多个条件的选择率若被简单相乘，而列实际强相关，就可能低估输出。通过更新统计、补充适当统计类型或调整查询结构，优化器才有依据重新比较计划；强制选择某个索引会掩盖估算原因。

索引与计划练习

练习标记完成

所属知识

页容量

难度

2/5

页面大小为 $8192$ 字节，管理信息占 $192$ 字节，定长行占 $200$ 字节。计算每页容量与十万行所需的最少数据页数。

查看解答

可用空间为八千字节，每行二百字节，每页四十行。十万行至少需要二千五百页，未计入空闲和变长字段开销。

练习标记完成

所属知识

树层数

难度

2/5

二十万个索引项，每叶页一百项，内部节点扇出一百。按满页模型计算总页数、层数和一次查找的索引页访问数。

查看解答

叶页需要二千页，上一层二十页，再上一层一个根，共三层和二千零二十一页。冷缓存单键查找读取三页索引，独立数据页另计。

练习标记完成

所属知识

连接基数

难度

2/5

一个连接键在左表出现三次、右表出现四次，另一个键分别出现两次和五次。计算等值连接的输出数量。

查看解答

该键产生十二对匹配。若还有一个键在左右分别出现二次和五次，则再产生十对，总共二十二对。不能直接按两个键的数量统计输出。

练习标记完成

所属知识

测量语义

难度

2/5

某计划显示总代价为一千，能否据此判断执行时间为一秒？说明需要进一步观察的三类数据。

查看解答

计划代价用于相对比较，单位由代价参数定义。实际时间还受缓存、并发和硬件影响。应执行适当分析并比较实际行数、循环次数和缓冲区访问，不能直接把估计代价当作毫秒。

索引与优化参考资料

PostgreSQL 17 Documentation: Using EXPLAIN

PostgreSQL Global Development Group · PostgreSQL Global Development Group

打开官方来源

PostgreSQL 17 的执行计划说明解释估计代价、输出行数、实际执行统计和测量限制，可用于逐层核对查询的工作量。

PostgreSQL 17 Documentation: Index Types

PostgreSQL Global Development Group · PostgreSQL Global Development Group

打开官方来源

官方索引类型章节按运算与数据类型说明不同索引的用途，适合核对等值、范围和其他条件的支持情况。

Intro to Database Systems (Fall 2025)

Andy Pavlo · 2025 · Carnegie Mellon University

打开官方来源

CMU 课程包含页存储、索引、查询执行与优化专题。这里的容量与扫描算例使用明确给定的参数，实际实现应结合相应数据库的页面布局和执行统计。