《物理模式设计》PPT课件.ppt

* 1 第5章: 物理模式设计 l主要内容 5.1物理模式设计简介 5.2索引的原理与设计原则 * 2 数据库系统概念-导论 5.1数据库的三级模式 l物理模式 数据的存储结构，研究数据如何存储 也称作称存储模式、内模式 l逻辑模式 全体数据的逻辑结构 又称作全局模式 l外模式 具体用户看到的数据的逻辑结构 又称作子模式、用户模式 * 3 数据库系统概念-导论 5.1数据库的三级模式关系示意图 App1App2 外模式1外模式2外模式 逻辑模式 物理模式 HD App3App . 三级模式及两级映像示意图 物理映像 逻辑映像 5.1物理模式设计的目标 l物理模式设计目标 在硬件及系统环境限制下，为逻辑模式的实 现提供最理想的支持 主要是性能支持 * 4 5.1物理模式设计在工程中的位置 l数据的物理独立性 当物理模式发生变化时，通过调整物理/逻 辑模式映像，可以保持逻辑模式不变，进而 应用程序不需改变；这种数据和程序的独立 性，称为数据的物理独立性。 l物理模式设计在工程中的位置 在逻辑模式设计完成后、程序开发之前进行 可以在系统上线实施调整 在系统运行期间，根据实际情况继续调整 * 5 5.2索引的原理与设计原则 l本节要点 5.2.1数据访问类型分析 5.2.2索引的基本工作原理介绍 5.2.3顺序文件与主索引 5.2.4辅助索引 5.2.5常见的索引结构 5.2.6索引的相关说明 5.2.7索引设计的原则 * 6 * 7 5.2.1:数据访问类型分析 l数据访问的类型 查询 修改 据调查：数据查询的访问数量远大于数据修改的数量 l数据查询的类型 特定值查询 例如：select * from s where sno=2009012689 值范围查询 例如：select * from sc where score=60 and score70 * 8 5.2.2索引的基本工作原理 l许多查询只涉及文件中的少量记录 找出计算机系的所有女学生 找出学号为s01的学生姓名 l只涉及少量记录查询的实现 读取所有记录并一一检查：非常低效 理想目标：快速甚至直接定位查询记录 l索引 为了实现快速数据定位，对数据文件设计的附加结构 与图书馆中图书索引的原理相同 * 9 5.2.2:索引设计基本原理示意 S9999 S0002 S0001 B5826 T1T2T5 T9997T9998T9999 B1 B5555 Select * from S where Sno=S4567; 全表扫描，O(n)，n=10,000，平 均读入1700磁盘块 索引扫描，O (logn) ，n=10,000, 除去索引块，只需读入1磁盘块 ，而索引所占空间小的多 S:SnoSnameDept T1S0001甲计计 T2S0002乙软软 S9999丁文 索引 5.2.3:顺序文件与主索引 l数据块 可用的磁盘空间被划分为很多块 块是磁盘空间输入和输出的最小单位 l索引记录（索引项） 由一个搜索码值和指向具有该搜索码值的一个或多个记录的 指针构成 指向记录的指针包括磁盘块的标识和标识磁盘块内记录的块 内偏移量 l顺序文件 元组在块中按照搜索码的升序存储 l主索引（聚集索引） 顺序文件中搜索码对应的索引 有主索引的顺序文件称作索引顺序文件 * 10 * 11 5.2.3:顺序文件与主索引示意 l顺序文件与主索引示意 主索引可以采用稀疏索引 稀疏索引只为搜索码的某些值建立索引 l主索引一般可以驻留内存 特定值查询、值范围查询：非常高效 l一个表至多有一个主索引 * 12 5.2.4:辅助索引 l辅助索引（非聚集索引） 文件中元组物理存储顺序与搜索码顺序不同的索引 一个表可以有多个辅助索引 辅助索引必须采用稠密索引 * 13 5.2.5常见的索引结构 l索引文件的主要组织类型 散列索引 顺序索引 l散列索引 将值平均分布到若干散列桶中 能很好地支持特定值查询 不能有效支持值范围查询 l顺序索引 基于值的大小顺序组织的索引 能很好地支持特定值查询、值范围查询 典型代表：B+树索引，是目前主流的索引结构 5.2.5:B树简介 l一棵 m 序B树是一颗满足下列条件的树 ： 1、每个结点至多有m个孩子； 2、除根结点和叶结点外，其它每个结点至少有 m/2个孩子； 3、根结点至少有两个孩子； 4、所有叶结点在同一层，叶结点不包含任何关 键字信息； 5、有K个孩子的非叶结点恰好包含K-1个关键字 。 * 14 5.2.5:B树示意 l一个3序B树示意 * 15 5.2.5:B树查询的高效性分析 1.每个结点包含1000个关键字，故在第三层上有100 多万个叶结点，这些叶节点可容纳10亿多个关键字 。 2.通常根结点可始终置于内存中，因此在这棵B树中查 找任一关键字至多只需二次访问外存。 * 16 5.2.5:B+树简介 lB+树是一种B树的变形 一棵m阶的B+树和B树的差异在于： 1. 所有的叶子结点中包含了全部关键字的 信息，及指向含这些关键字记录的指针， 且叶结点依关键字的大小从小到大顺序链 接。 2. 非叶结点仅具有索引作用，结点中仅含 有其子树中最小关键字。(B树键值只出现 一次) 3. 叶结点的关键字可以多于m，也可以少于 m。 * 17 5.2.5:一个B+树示意 l一个3序B+树示意 * 18 * 19 5.2.6:索引 的相关说明 l索引的有关说明 可以动态地定义索引，即可以随时建立和删除索引 不允许用户在数据操作中引用索引，索引是否使用 、如何使用、如何维护完全由系统决定； 一个表上可建多个索引。索引可以提高查询效率， 但索引过多耗费空间，且降低了插入、删除、更新 的效率，并且会增加系统选择索引的时间代价 有些DBMS自动建立以下列上的索引 l PRIMARY KEY l UNIQUE * 20 5.2.6:索引 的相关说明 l索引的定义 格式 create unique/distinct cluster index 索引名 on 表名 (列名 asc/desc , 列名asc/desc) unique（distinct）：唯一性索引，不允许表中不同 的行在索引列上取相同值。若已有相同值存在，则 系统给出相关信息，不建此索引。系统并拒绝违背 唯一性的插入、更新 cluster：聚集索引，表中元组按索引项的值排序并 物理地聚集在一起。一个基本表上只能建一个聚集 索引 asc/desc：索引表中索引值的排序次序，缺省为asc * 21 5.2.6:索引 的相关说明 示例： create cluster index s-index on S（SN） l索引的删除 格式 drop index 索引名 l索引连接(INDEX-JOIN) 对表2按连接字段建立索引 对表1中的每个元组，依次根据其连接字段值查询 表2的索引，从中找到满足条件的元组，找到后就 将表1中的第一个元组与该元组拼接起来，形成结 果表中一个元组 * 22 5.2.7:索引设计的原则 l索引建立原则： 不必为小表创建索引 为表的主码建立索引 为检索数据时大量使用的列建立辅助索引（如 name ） 若经常基于外码访问数据，则为该外码建立辅助索引 为经常有如下情况的列建立辅助索引： 选择或连接条件; ORDER BY; GROUP BY; 其他含有 排序的操作 (如 UNION 或 DISTINCT) 慎重为经常被更新的列或表建立索引 如果查询将检索表中记录的大部分（如25%)，即使表 很大，也不建立索引。这时查询整表要比用索引查询 更有效（选择率） * 23 5.2.7:索引设计的原则 l索引与查询优 化 有些DBMS允许检查优 化器的策略，从而可以分析 改善查询的性能；Oracle EXPLAIN PLAN，DB2 EXPLAIN，ACCESS性能分析器 查询优 化器依赖于存储在系统目录中的数据库统计 来选择最佳策略，每当创建索引时，DBMS自动将 此索引增加到系统目录中。但是，系统目录中与表 和索引相关的统计信息的更新，需要数据库用户自 己使用DBMS提供的工具完成 l索引的删除 如果维护索引可能会降低重要的更新事务，就考虑 删除索引 如果大量的记录被插入到有索引的表中，可以先删 除索引，再执行插入，然后重建索引（若增加表大小 超过10%） * 24 数据库系统概念-E-R 练习 l思考与练习： 对下述关