查询处理与查询优化
B+树
B+树的优势:
-
单一节点存储更多的元素, 使得查询的IO次数更少.
-
所有查询都要查找到叶子节点, 查询性能稳定.
-
所有叶子节点形成有序链表, 便于范围查询.
搜索
条件表达式的几种情况 C1: 无条件 C2: Sno = ‘2011003’; (搜索主键) C3: Sdept = ‘CS’; C4: Sage > 20; C5: Sdept = ‘CS’ and Sage > 20; 假设Students关系的信息如下 Students的记录数:n1 Students所占的磁盘块数: b1
线性搜索
适用于任何文件 不要求有序 不要求构建索引 不限制选择运算的条件 选择运算的时间代价(连续存放):
1
b1 *tT + tS
tT: 磁盘传输数据的平均时间 tS: 磁盘块平均访问时间(理解为寻找磁盘块的时间, 因为是顺序查找, 只需要找到起始块即可(或许更深层次的理解是CPU寻址时间?))
二分
等值条件 文件按查询属性排序 不需要索引 针对文件的磁盘块进行 (注: 没说连续)
选择运算的时间代价: ceil(log2(b1)) * (tT + tS)
聚簇索引(S3/S4)
1
2
记录连续,一次定位,然后b组传输
h * (tT + tS) + tS + b *tT
辅助索引(S3/S4)
1
2
记录不连续,每次传输都要重新定位
h * (tT + tS) + n * (tT + tS)
合取选择查询
- 利用索引找到符合各个条件的元组指针，取指针的交集
- 找到符合第一个条件的元组指针，在此范围内检查另一条件是否满足
析取选择查询
- 每个条件属性上都有索引->利用索引找到符合各个条件的元组指针->取指针的并集
- 否则线性扫描
连接
-
嵌套循环连接
最好:(b1 + b2)tT+2tS 最坏:(b1 + n1 b2)*tT+(n1 + b1)tS
小关系作为外循环表
-
索引嵌套循环连接
最好:b1tT+tS +n1c 最坏:b1(tT+tS) +n1*c
-
归并连接
(b1 + b2) *tT + (ceil(b1/bb)+ ceil(b2/bb))tS
-
散列连接
3(b1 + b2)
-
混合散列连接
b1 + b2块传输
执行开销
第八章直播第50页
前提: 1k个 Student 1w个 SC
连接+内存到硬盘+选择操作(根据执行顺序不用, 计算的顺序也不同)
-
笛卡尔积
硬盘->内存 内存->硬盘(将笛卡尔积的中间结果按块写入硬盘) 选择操作(即载入中间结果(我的理解是遍历中间结果,耗时和内存->硬盘一样多,本质上就是又把内容读了一遍))
-
自然连接
硬盘->内存 内存->硬盘(将自然连接的中间结果按块写入硬盘) 选择操作(同上)
-
先选择后连接
硬盘->内存(实际上先只读取SC) 然后投影几乎不花时间(因为都在内存中) 然后读取Students
主要包括 集中式数据库
1
总代价 = I/O代价 + CPU代价 +内存代价
分布式数据库
1
总代价 = I/O代价 + CPU代价 + 内存代价 + 通信代价
