网站建设所需的硬件设备,产品推广软文,百度推广充值必须5000吗,哈尔滨网页设计学校第九章 关系查询处理与优化
索引 索引文件是一种辅助存储结构#xff0c;其存在与否不改变存储表的物理存储结 构#xff1b;然而其存在#xff0c;可以明显提高存储表的访问速度。 索引文件组织方式有两种#xff1a;(相对照的#xff0c;主文件组织有堆文件、排序文件、…第九章 关系查询处理与优化
索引 索引文件是一种辅助存储结构其存在与否不改变存储表的物理存储结 构然而其存在可以明显提高存储表的访问速度。 索引文件组织方式有两种(相对照的主文件组织有堆文件、排序文件、散列文件、 聚簇文件等多种方式) 排序索引文件(Orderedindices):按索引字段值的某一种顺序组织存储 散列索引文件(Hash indices):依据索引字段值使用散列函数分配散列桶的 方式存储
特点 在一个表上可以针对不同的属性或属性组合建立不同的索引文件可建立 多个索引文件。索引字段的值可以是Table中的任何一个属性的值或任何多个 属性值的组合值 索引文件比主文件小很多。通过检索一个小的索引文件(可全部装载进内 存)快速定位后再有针对性的读取非常大的主文件中的有关记录 有索引时更新操作必须同步更新索引文件和主文件。 DBMS可以自动维护table改变索引也会有相应的改变 索引技术应用使检索效率大幅度提高但同时其也增加了存储空间、使维 护负担加重(不仅要维护主文件而且要维护索引文件) 衡量索引性能好坏 访问时间 插入时间 删除时间 空间负载 支持存取的有效性 比如支持的是属性的限定值(是否符合单一值) 还是支持属性的限定范围的值(是否符合一定范围)
相关概念 创建索引 对于主文件中每一个记录(形成的每一个索引字段值)都有一个索引项和它 对应指明该记录所在位置。这样的索引称稠密索引(denseindex) 候选键属性的稠密索引 先查索引然后再依据索引读主文件 候选键属性的稠密索引(三种情况) 对于主文件中部分记录(形成的索引字段值)有索引项和它对应这样的索 引称非稠密索引(undense index)或稀疏索引(sparseindex) 稀疏索引如何定位记录 定位索引字段值为 K的记录需要 首先找相邻的小于K的最大索引字段值所对应的索引项从该索引项所对应的记录开始顺序进行Table的检索 稀疏索引的使用要求—主文件必须是按对应索引字段属性排序存储相比稠密索引空间占用更少维护任务更轻但速度更慢平衡:索引项不指向记录指针而是指向记录所在存储块的指针即每一 存储块有一个索引项而不是每条记录有一索引项----主索引
比较
一个主文件仅可以有一个主索引但可以有多个辅助索引主索引通常建立于主码/排序码上面辅助索引建立于其他属性上面可以利用主索引重新组织主文件数据但辅助索引不能改变主文件数据主索引是稀疏索引辅助索引是稠密索引
聚簇索引与非聚簇索引 聚簇索引—是指索引中邻近的记录在主文件中也是临近存储的 非聚簇索引—是指索引中邻近的记录在主文件中不一定是邻近存储的
特点
如果主文件的某一排序字段不是主码则该字段上每个记录取值便不唯 一此时该字段被称为聚簇字段聚簇索引通常是定义在聚簇字段上。聚簇索引通常是对聚簇字段上的每一个不同值有一个索引项索引项的总数和 主文件中聚簇字段上不同值的数目相同索引字段即是聚簇字段的不同值由于有相同聚簇字 段值的记录可能存储于若干块中则索引项的指针指向其中的第一个块。一个主文件只能有一个聚簇索引文件但可以有多个非聚簇索引文件 主索引通常是聚簇索引(但其索引项总数不一定和主文件中聚簇字段上不同值的数目相 同其和主文件存储块数目相同)辅助索引通常是非聚簇索引。主索引/聚簇索引是能够决定记录存储位置的索引而非聚簇索引则只能用 于查询指出已存储记录的位置
其他索引类型
倒排索引 数据库查询实现算法
一趟扫描算法
数据库查询优化技术
思路 (1)尽可能地早做选择和投影可使中间 结果变小节省几个数量级的执行时间。(2)把选择与投影串接起来一元运算序 列可一起执行只需对整个关系扫描一遍。(3)把投影与其前或后的二元运算结合 起来在第一次用关系时去掉一些无关属性 可以避免多次扫描整个关系。(4)把某些选择与其前的笛卡尔积合并 成一个连接当R×S前有选择运算且其中有 条件是R、S属性间比较的运算时可将其转化 为连接运算可节省时间。(5)执行连接运算前对关系做适当预处 理文件排序、建立临时索引等可使两关系 公共值高效联接。(6)找出表达式里的公共子表达式若 公共子表达式结果不大则预先计算以后可读 入此结果节时多尤当视图情况下有用。
关系代数操作交换的等价性
关系代数 并差积选择投影
等价 关系交换定理
连接与连接积与积的交换律 通常我们选择结果集合小的表达式先装入内存 连接与连接、积和积的结合律 通常我们选择结果集合小的表达式先装入内存 投影串接律 选择串接律 选择和投影交换律 选择和积的交换律 投影和积的交换律 选择和并的交换律 选择和差的交换律 投影和并的交换律 查询优化算法及示例 物理层优化
代价估算
