代价度量
影响一次查询执行的代价有很多，磁盘读取，CPU执行，并行/分布式数据库系统中的通信代价等。有些代价难以度量，并且并非主要代价，这里使用磁盘搜索次数和传送磁盘块数来度量查询执行计划的代价。假设磁盘子系统传输一个磁盘块的时间为$t_s$,一次磁盘搜索的时间为$t_T$。
选择运算的代价估计
考虑所有元组都存在单一文件关系上的一个选择运算。
注意一般$B^+$树非叶节点小于总结点数的1%，$B^+$树 n的大小一般等于磁盘块大小。
| 算法 | 开销 | 原因 | |
|---|---|---|---|
| $A_1$ | 线性搜索 | $t_s+b_r\times t_T$ | 一次初始搜索，加$b_r$次块传输 |
| $A_2$ | 线性搜索,码等值比较 | 平均情形: $t_s+(b_r/2)\times t_T$ | 由于最多只有一条记录满足条件，搜索到数据就能终止搜索 |
| $A_3$ | $B^+$树主索引，码等值比较 | $(h_i+1)(t_T+t_s)$ | $h_i$是$B^+$树的高度。根据$B^+$树查找记录的算法，查找时，穿越整棵树的高度，每次穿越都需要一次搜索和传输找到结点，最后一次传输和搜索找到记录 |
| $A_4$ | $B^+$树主索引，非码等值比较 | $h_i(t_T+t_s)+b\times t_T$ | 由于数据按主索引存储不需要额外的搜索，b是存储比较值的块数 |
| $A_5$ | $B^+$树辅助索引，码等值比较 | $(h_i+1)(t_T+t_s)$ | 和主索引类似 |
| $A_6$ | $B^+$树辅助索引，非码等值比较 | $(h_i+n)(t_T+t_s)$ | n表示取到的记录数,辅助索引索引顺序于存储顺序不同，查找到n条记录，就需要n次磁盘传输和磁盘搜索，再加上$B^+$树高度的穿越 |
| $A_7$ | $B^+$树主索引，比较 | $h_i(t_T+t_s)+b\times t_T$ | 根据$B^+$树取数据的过程，符合条件的索引值是连续的，存储的位置也是连续的，不管是等值比较还是比较，过程都类似，且取数据的过程都不需要额外的磁盘搜索 |
| $A_8$ | $B^+$树辅助索引，比较 | $(h_i+n)(t_T+t_s)$ | |
从表中可以看出一些特点
- 不论是$B^+$树主索引 还是 $B^+$树辅助索引，进行非码等值比较时和比较的开销都相同，这是由$B^+$树搜索过程决定的。不同的是主索引的存储顺序和记录存储顺序相同，相较于辅助索引，取数据不需要额外的磁盘搜索操作
- 对于等值比较，码等值比较由于只有0个或一个匹配项，不管是辅助索引还是主索引，都不会存在由于数据存储顺序出现的额外的磁盘搜索，非码等值比较有0个或多个匹配项，辅助索引上的非码等值比较由于数据存储顺序和索引顺序不同，每个匹配项都需要一次磁盘搜索和磁盘传输
This is copyright.