选择运算五种实现算法的代价梯度

从表中按条件挑出满足条件的记录（选择运算），并非只有”扫全表”一种 做法，五种实现算法按能利用的数据结构越来越丰富、代价越来越低排成 一条梯度。全表扫描是最基础的兜底方法：顺序读遍每个数据块，代价与 表的块数成正比，不依赖任何额外结构，因此适用面最广但也最慢。若数据 本身按选择条件涉及的属性有序排列，可以用二分搜索，代价从”线性”降到 “对数”级别，但要求数据物理有序这个前提不总是成立。若这张表本身就 存储在B树索引文件里（即索引和数据在同一文件），且选择条件正好是 等值查询，可以用主索引等值选择：直接沿树查到目标关键字，代价约等于 索引树的高度——比二分搜索更快，因为B树的多路结构比普通有序数组 能容纳更多层级的跳跃。若选择条件是范围查询而非等值查询，用主索引 范围选择：先用索引定位到范围起点，再顺序读取范围内的若干个文件块， 代价是索引树高度加上范围内的块数。若索引和数据不在同一文件（辅助 索引），则要先查辅助索引拿到数据物理位置指针，再回到主数据文件读取 真正的数据——多了一次跳转的开销，但通常仍比无索引扫描快。这五种 算法的选型逻辑很清晰：数据结构（是否有序、是否建了索引、索引类型） 决定了可用的最快路径，选择运算的物理优化本质上就是识别当前场景下 能用到的最优结构。

结构图：

flowchart LR
    A[选择运算实现] --> B["全表扫描<br/>无前提, O(块数)"]
    A --> C["二分搜索<br/>需数据有序, O(log块数)"]
    A --> D["主索引等值选择<br/>需B树索引+等值条件, O(索引高度)"]
    A --> E["主索引范围选择<br/>需B树索引+范围条件, O(索引高度+范围内块数)"]
    A --> F["辅助索引范围选择<br/>索引与数据不同文件, 多一次跳转"]