《数据库原理与应用》PPT课件.ppt

数据库原理与应用 第六章数据存储与查询优化 数据库原理与应用 6 2 第六章数据存储与查询优化 物理存储索引结构查询处理过程代数优化物理优化 数据库原理与应用 6 3 物理存储介质 现代计算机体系结构中存在着多种存储介质 按照容量 访问速度等技术指标又可分为三级 组成一个典型的金字塔结构 数据库原理与应用 6 4 挥发性和持久性介质 内存等一级存储介质只在系统运行时保存数据 一旦断电 数据全部丢失 称为挥发性介质磁盘 磁带等二 三级存储介质则在断电之后仍能保持数据的有效性 称为持久性介质数据库中的数据必须长时间的保存 即使系统关闭也不应该影响数据库中数据的有效性 因此 数据库中的数据必须存储在二 三级持久性介质中 数据库原理与应用 6 5 磁盘 磁盘又称为硬盘 磁盘属于第二级存储 为持久性介质 是数据库的典型存储介质一个磁盘中包含一个或多个盘片 这些盘片由金属或玻璃等刚性介质制成 表面涂有磁性介质用来记录数据一个盘片有上下两个盘面 可以都用来记录数据 也可以只用一个面来记录数据对每一个用来记录数据的盘面都有一个磁盘臂 其末端的读写头通过感应或改变盘片的局部磁性来读取或写入磁盘中的数据 数据库原理与应用 6 6 磁盘 续 一个盘面被划分为多个间距很小的同心圆 这些同心圆被称为磁道 track 不同盘面上有相同直径的磁道构成一个柱面 cylinder 磁道又可以进一步分为多个扇区 sector 现有的磁盘中一个扇区的典型容量是512字节在工作状态时 磁盘轴带动盘片以恒定的速度旋转磁盘与操作系统之间的交互是通过磁盘控制器完成的 数据库原理与应用 6 7 磁盘结构 数据库原理与应用 6 8 磁盘I O的性能 读写磁盘数据时 磁盘内部需要进行以下的一系列动作移动磁盘臂 直到读写头位于数据所在磁道的正上方通过盘片旋转 使得读写头位于所读写数据的正上方读写头读取或写入数据磁盘进行一次数据读写操作的时间由三部分组成第一部分是移动磁盘臂所用的时间 称为寻道时间 典型值为几毫秒第二部分是旋转盘片所用的时间 称为旋转时间 典型值为5 10毫秒第三部分是读写数据所用的时间 称为传输时间 典型值为几到几十MB每秒 数据库原理与应用 6 9 磁盘读写的优化 磁盘臂调度的目的是通过规划多个数据读写请求的服务顺序来减少读写头的总移动距离 从而缩短读写磁盘的平均寻道时间 一种常用的磁盘臂调度算法是电梯算法无论读写的数据量多大 由寻道时间和旋转时间带来的额外消耗都是一定的 因此读写少量数据时的效率就比读写大量数据时的效率低得多基于计算机系统中的局部性原理 在磁盘与操作系统之间的数据交互过程中广泛使用数据预取技术 即在读取指定数据的同时也预先读取与其相邻的一定范围内的数据典型的数据预取技术是数据的按块传输 块是一个逻辑单位 即一个磁盘从逻辑上被划分多个连续的块 目前典型的块大小在1KB 8KB之间 数据库原理与应用 6 10 缓冲管理 在系统内存中开辟一块专用空间 称为缓冲区 用来缓存经常需要访问数据DBMS中用来对缓冲区进行管理的模块就称为缓冲区管理器当DBMS的其它模块需要读取数据时 它们向缓冲区管理器发出请求缓冲区管理器首先查看需要读取的数据是否在缓冲区中 如果在 则缓冲区管理器直接返回缓冲区中的数据 从而免除了进行磁盘I O的代价如果在缓冲区中找不到指定数据时 则缓冲区管理器先从磁盘将数据读入缓冲区 然后返回给请求者 数据库原理与应用 6 11 缓冲区管理器 缓冲区中的内容被划分为多个块 块大小与磁盘块一致 为了对缓冲区进行有效管理 需要为每个缓冲块记录以下内容 空闲位脏位 在读入之后被修改过的缓冲块称为脏块pin值 pin值有两个功能 一是防止缓冲区管理器替换出正在处理的块 二是可以指定某些块常驻内存 缓冲区在选择被替换的块时 如果发现某缓冲块的pin值不为0 则不会将它替换出去 提供强制写出脏的缓冲块的功能 这是为了保证数据的持久化存储 一种典型情况是系统关闭时需要强制写出所有脏的缓冲块 另外为了数据库恢复的需要也要强制写出脏的缓冲块 数据库原理与应用 6 12 缓冲区替换策略 缓冲区通常不足以容纳数据库中的所有数据 在需要读入新的数据时 可能出现缓冲区已满的情况 这时缓冲区管理器就要选择一个缓冲块替换出去如何选择被替换的缓冲块将影响到数据库运行过程中进行磁盘I O的频率 一个好的缓冲区替换策略应该能够减少磁盘I O 提高数据库的性能LRU LeastRecentlyUsed 替换策略的基本思想是 系统未来对数据的访问情况可由系统过去的访问情况预期 即如果一个数据块在过去很少被访问 则将来也不太可能被访问 因此在缓冲区满时可考虑将其替换出去 反之 如果一个数据块在过去经常被访问 则将来也很有可能会被再次访问 因此不应将其替换出去 数据库原理与应用 6 13 LRU替换策略 设有一个4块的缓冲区 初始为空 以后依次访问了块1 4 8 1 5 2 3 2 4 则根据LRU替换策略缓冲区的内容如下图所示 其间共发生了三次缓冲区替换 数据库原理与应用 6 14 记录的存储 数据库的数据通常按记录的形式加以组织 记录又由一到多个字段组成有些类型 如整型 浮点型 定长字符串和日期类型等 无论具体的值是什么 占用的存储空间都是一样的 称为定长类型另一些类型 如变长字符串和文本等 占用的存储空间由实际的值决定 称为变长类型如果一条记录中只包含定长类型的字段 则该记录称为定长记录 否则称为变长记录 数据库原理与应用 6 15 定长记录 定长记录中所有的字段都是定长的 只需将所有字段按既定的顺序连续存放 所有字段的地址相对于记录首地址的偏移都可以计算得到 数据库原理与应用 6 16 变长记录 变长记录中每个字段相对于记录首地址的偏移是不固定的 因此除了记录所有字段的值之外 在记录中还需要包含一些附加信息 以使得在访问时可以计算出记录中各个字段的偏移量 变长记录的内部格式通常有两种 一种是用特殊的分隔符将记录中的各字段隔开 这种方法有两个缺点不能保证分隔符永远不会在字段的值中出现即使只访问记录中的某个字段 也必须从记录首部开始搜索 否则无法确定该字段的位置 数据库原理与应用 6 17 变长记录 续 另一种方法是在记录首部存储各个字段的偏移量 这种方法解决了特殊字符分隔法的缺点 因此在实际的系统中更为常用 数据库原理与应用 6 18 块格式 块是内外存交互的单位 记录必须存储在块中 一般来说 记录的长度小于块大小 因此在一个块中可以存放多条记录 每个块中可以存放多条记录 其中f称为该数据文件的块因子 如果记录跨块存储 在访问该记录时就会导致多次磁盘I O操作 数据库原理与应用 6 19 数据文件的重整 在DBMS运行过程中 每删除一条记录 就在数据文件中产生一块小的空闲空间 这些小的空闲空间难以被有效利用 随着DBMS的不断运行 就会使数据文件中产生越来越多的 碎片 从而导致DBMS性能的降低 为解决这一问题 需要定期对数据文件进行重整数据文件的重整可以在文件范围进行 能够完全消除数据文件中的 碎片 但文件范围的重整会导致记录在文件范围内移动 使得整个数据文件在重整过程中无法使用 也必然会影响到建立在该数据文件上的索引结构更为常用的重整方法是块内重整 块内重整按序处理数据文件中的每个块 将该块内的记录集中存储到块尾 数据库原理与应用 6 20 超长记录和记录的跨块存储 为了利用空间 可以考虑允许记录跨块存储 即当块中存不下一条完整的记录时 可以把记录的前一部分存在该块中 而把余下的部分存在后续的块中除了为了防止空间浪费而进行跨块存储外 当记录的长度超过块的大小时 也必须进行跨块存储 数据库原理与应用 6 21 文件组织方式 堆文件 记录间没有次序关系 新加入的记录可以存储在文件中任何有空间的地方 顺序文件 记录按某些字段的值进行排序 哈希文件 对记录的某些字段进行哈希运算 运算的结果决定记录存储在文件中的哪一块 聚集文件 将同种类或相关的来自于不同关系的记录存放在同一块中 以减少同时获取这些记录的I O操作 数据库原理与应用 6 22 顺序文件 数据库原理与应用 6 23 顺序文件的特点 优点按搜索键的值顺序读取记录的效率很高如果选择条件基于搜索键的值 就可以在磁盘上进行二分查找但顺序文件在处理记录的插入上却有较大的困难 当插入一条记录时 首先要根据待插入记录的搜索键值找到记录的插入点 然后要将插入点之后的所有记录向后移动 以便为待插入记录留出空间 这样平均插入一条记录就要移动文件中一半的记录 为改善顺序文件中记录插入操作的性能 可以在每个块中都为新记录预留出一定的存储空间 数据库原理与应用 6 24 聚集文件 但对于大型或超大型的数据库 性能是最重要的因素 为提高数据库的性能 大型数据库中通常采用更复杂的文件组织方式 允许多个表中的相关记录存储在一个数据文件中 这种文件组织方式就称为聚集文件但采用聚集文件也会使某些查询的执行效率降低 因此 是否采用聚集文件及如何进行聚集应该由在数据库运行过程中各类查询的频率决定 数据库原理与应用 6 25 索引 从理论上来说 只要记录被正确地存储于数据文件中 DBMS就可以正常工作 但实际上 单纯依赖数据文件处理查询有时候效率是非常低的DBMS中索引的工作方式与书后面关键词索引的工作方式是相似的DBMS索引中与关键词相对应的概念称为索引键 或索引字段 由一个或多个字段组成 DBMS可以借助于索引找到包含指定键值的记录的位置B 树索引和哈希索引 数据库原理与应用 6 26 B 树的结构 B 树属于多级多叉平衡树 从根到每个叶节点的路径长度相等B 树中每个节点大小相同 且拥有相似的内部结构对于n阶的B 树 每个B 树节点最多可以包含n 1个排列有序的索引键值和n个指针 对一个节点中的键值编号为K1 K2 Kn 1 节点的键值递增排列 即K1又称为一个入口项 数据库原理与应用 6 27 B 树的结构 续 B 树节点的大小与缓冲块大小相同 因此 具有不同索引键的B 树的阶数是不同的 可由以下公式计算得到阶数 缓冲块大小 索引键大小 索引键大小 指针大小 在B 树中存在两种节点 叶节点和非叶节点 不同类型的节点具有不同的性质 数据库原理与应用 6 28 叶节点 对于i 1 2 n 1 指针Pi指向包含键值Ki的记录的位置 如果索引键是主键 则每个索引键值只对应一条记录 指针Pi指向的是含有索引键Ki的记录 如是索引键不是主键 则可能有多条记录具有相同的索引键值 指针Pi指向的是一个包含所有具有索引键值Ki记录位置的指针桶 叶节点的最后一个指针Pn指向该它的右兄弟节点 如果该节点已经是最右的叶节点 则Pn为NULLB 树的每个叶节点中最少需要包含个索引键值所有叶节点中的索引键值也递增排列 且不同叶节点中的索引键值间不重合 即若Li和Lj为叶节点 且i j 则Li中的所有索引键值都小于Lj中的所有索引键值 叶节点构成B 树中所有键值的一个划分 数据库原理与应用 6 29 非叶节点 所有的指针指向它的子节点 除根节点之外的所有非叶节点最少需要包含个指针 根节点最少可以包含2个指针 除非B 树中只有一个节点 此时根节点是叶节点 设一个非叶节点中包含m个指针 此时m称为该节点的扇出度 则对于i 2 3 m 1 指针Pi指向的子树中所有索引键值都大于或等于Ki 1且小于Ki 指针Pm指向的子树中所有索引键值都大于或等于Km 1 指针P1指向的子树中所有索引键值都小于K1 数据库原理与应用 6 30 一个3阶的B 树 数据库原理与应用 6 31 B 树检索 检索过程从B 树的根节点开始 系统首先找出根节点中比V大的最小索引键值 设为Ki 然后系统下溯到指针Pi指向的子节点 若V比根节点中所有索引键都大 则下溯到Pm指向的子节点 系统循环执行上述过程 直到到达叶节点 在该叶节点上 如果存在与V相等的Ki 则Pi指向所需的记录或指针桶 本次检索操作成功 如果不存在与V相等的索引键 则检索失败 返回空 数据库原理与应用 6 32 B 树检索的效率 B 树的每次检索操作访问的节点构成了从根节点到某个叶节点的路径 由于B 树是平衡树 因此每次检索操作访问的节点数相同 都为B 树的树高设B 树中的索引键值为K 则B 树的高不会超过 在实际应用中 n的值通常在几十到几百之间 因此B 树的高相对于索引键值数来说是很小的 设n为100 则在B 树中拥有100万个索引键值时 进行一次B 树检索操作只需访问4个节点 由此可见 通过B 树进行数据检索的效率是相当高的 数据库原理与应用 6 33 B 树更新 索引结构必须与对应的基本表中的数据相一致 当用户插入 删除基本表中的记录或更新记录中索引字段的值时 必须同时更新相应的索引结构B 树索引支持两种基本的更新操作 插入和删除一个入口项 数据库原理与应用 6 34 插入操作 首先用B 树检索算法找到用于插入该键值的叶节点 若该叶节点中已经包含待插入的键值 则将记录的位置添加到相应的指针桶中 否则 将键值插入到该叶节点的合适位置 使得在插入后节点中的键值仍保持递增排列 当索引为unique时 同时插入记录的位置 当索引不为unique时 创建一个只包含新插入记录位置的指针桶 同时插入指针桶的位置B 树插入操作的复杂性在于在特定情况下必须进行节点分裂操作 当用于插入新索引键值的叶节点原已满时 叶节点分裂为两个节点 原节点中的n 1个入口项加上新插入的入口项共n个入口项中索引键值最小的个入口项保留在原节点中 其余的移到新创建的节点中 新节点中最小的索引键值和新节点的位置构成的入口项继续插入到原节点的父节点中 数据库原理与应用 6 35 在前图所示B 树中插入30和50 数据库原理与应用 6 36 再插入25后的B 树 数据库原理与应用 6 37 删除操作 根据检索算法找到该入口项所处的叶节点 然后将其从该叶节点中删除 如果在删除后使得该叶节点中余下的入口项不足个 即产生一次向下溢出 underflow 则需要尽量找到一个兄弟节点以进行节点合并或入口项重新分配 通常是向该节点 借用 一个入口项 如果两个节点中的入口项之和不大于n个 则将两个节点合并为一个节点 并将被删除节点在父节点中的入口项删除 否则 将两个节点间的入口项重新分配 并相应地更新在父节点中的索引键值 由于节点的合并需要在父节点中删除入口项 因此又可能导致父节点向下溢出 节点的合并操作可能一直上传到根节点 如果根节点的两个子节点合并为一个节点 则将原根节点删除 而将合并后的子节点设为新的根节点 数据库原理与应用 6 38 删除60后的B 树 数据库原理与应用 6 39 继续删除10后的B 树 数据库原理与应用 6 40 哈希索引 哈希索引的基本思想是用一个哈希函数将索引键值映射到记录所处的位置 通常称为桶根据索引中桶的数目变化与否 哈希索引又分为静态哈希和动态哈希两种若要查找哈希索引中的入口项 首先对指定的索引键值进行同样的哈希计算 根据计算的结果找到该入口项所处的桶 然后在其主块和溢出块链表中进行顺序查找即可若要向哈希索引中插入一个入口项 首先对其键值进行哈希计算 然后将其插入到哈希结果所示的桶中 如果桶中没有中够的空间 则为该桶开辟一个新的溢出块然后将该入口项插入到新开辟的块中若要删除哈希索引中的入口项 首先根据查找算法找到该项 然后将其从所处的块中删除 若删除后该块为空且为溢出块 则将该块从所处桶的溢出块链表中删除 数据库原理与应用 6 41 静态哈希 哈希函数 一个好的哈希函数能够将索引键值比较平均的分配到各个桶中去桶的数量 为了不产生溢出现象 桶的数量nB需要满足nB nr fr 其中nr为预期的索引键值数 fr为每个块中所能存储的索引键值数 但在实际情况下通常无法达到完全平均分配 因此 在计算桶的数量时应适量放宽20 到30 数据库原理与应用 6 42 动态哈希 一般说来 数据库中的数据总是随着数据库运行时间的增长而增长 这样在使用静态哈希时选择桶的数量就成了一个大问题 如果桶的数量过小 则随着数据库的运行 索引中将会产生大量溢出块 从而导致性能降低 反之 如果一开始就将桶的数量设得很大 则在很长一段时间内又会造成空间的浪费动态哈希技术弥补了静态哈希的上述缺陷 动态哈希技术允许文件中的桶数动态增长 同时又不需要重整 有两种常用的动态哈希 可扩展哈希和线性哈希 数据库原理与应用 6 43 查询处理 数据库原理与应用 6 44 查询优化的两种主要途径 代数优化 根据等价变换规则将初始查询树转换成另一种形式 代数优化的输入和输出都是关系代数表达式 但输出比输入更有利于于执行 代数优化一般是基于规则的优化 在代数优化过程中一般较少使用统计信息 不进行代价估计 由代数优化产生的查询树又称为最终查询树 物理优化 为代数优化产生的最终查询树生成不同的物理执行计划 并利用统计信息对计划的执行代价进行估计 最后选择其中代价最小的计划作为输出 因此 物理优化是基于代价的优化 数据库原理与应用 6 45 代数优化 数据库原理与应用 6 46 代数优化的等价变换 数据库原理与应用 6 47 代数优化的等价变换 续 数据库原理与应用 6 48 物理优化 物理优化在代数优化之后进行 其过程可以概括为 枚举策略 估算代价 生成计划 三步物理优化是基于代价进行的 物理优化的思想是为每个操作考虑多种可行的执行策略 并对每种执行策略的代价进行估计 然后选择其中代价最小的作为最终的执行策略代价估算是物理优化的基础 在DBMS中 执行代价通常是用读写磁盘块的次数来衡量的为了对各种操作的代价进行估算 需要在数据库记录一些附加的数据 这些数据称为统计信息 通常记录在系统的数据字典中 数据库原理与应用 6 49 辅助信息 nr 关系r中的元组数 br 关系r的数据文件中包含的数据