6.2 扫描算法
在查询处理中，表的扫描是最基本的操作，扫描算子位于查询计划树的叶子结点。简单而言，扫描算法的作用是寻找一张或多张表中满足查询条件的记录的位置，并将这些记录提取出来。
以下我们假设一张表的所有记录存储在单个文件中，则最直接的扫描算法为全表扫描：
- 全表扫描 (Sequential Scan)：数据库系统逐一将表文件的每块数据读入内存，判断每条记录是否满足查询条件。
全表扫描是最简单效率最低的扫描算法，但也是最通用的扫描算法，无论被扫描的表以什么形式存储、是否建有索引，都可以采用全表扫描算法。
如果查询条件涉及的列上建有索引，我们可以利用索引来加速扫描，而根据索引是簇集索引或非簇集索引，索引扫描分为两种策略：
-
簇集索引扫描：如果索引为簇集索引，则表的数据按照索引列顺序排列，可利用索引加速扫描过程。
-
非簇集索引扫描：非簇集索引的索引列有序排列，但其对应的记录的其他列却是随机存储的，因此通过索引文件找到满足条件的记录的位置后，还需要一系列随机访问从表文件取出原始记录数据。
选择全表扫描还是索引扫描，并不是一个显而易见的问题。如果仅仅根据查询条件涉及的列上是否有索引来选择扫描算法，对于某些查询并不会达到理想的效果。特别是非簇集索引扫描，其中包含的随机访问操作会带来很大的开销。在选择索引扫描算法时，还需要考虑查询的选择率（满足查询条件的记录数 / 记录总数），在选择率较高的情况下，非簇集索引扫描可能产生更大的开销。
Authors: