4-9章习题解答

第 4 章 数据存储与组织管理 要回答以下问题。 （ 1） 描述磁盘空间管理器的主要作用，并说明它与 件系统的关系。 （ 2） 解释关系数据库系统中关系表与文件的关系。 （ 3） 如果有一个大文件需要频繁执行顺序扫描，那么，为该文件选择哪种页存储方式最合适？ （ 4） 分别描述持久化指针解引用 (指针混写的这两个基本过程，它们之间有何联系？ （ 5） 说明排序文件中的记录及页的基本存储组织方式。 （ 6） 解释缓冲区管理器处理一个读页请求的过程。如果被请求页位于缓冲池但未被闩住 (那么情况会怎样？缓冲区管理器何时写一 个磁盘页？ （ 7） 一个缓存页被闩住（ be 味着什么？一般由谁负责给缓存页上闩，由谁负责给缓存页解闩 ? （ 8） 当一个页请求发生时，如果缓冲池中所有页都是脏页，将会发生什么？ （ 9） 与 存管理相比， 冲区管理器具有那些独特的重要能力？ （ 10） 什么是预取？解释为什么这种策略很重要。 （ 11） 描述两种可能的记录格式，并指明它们的优缺点。 （ 12） 描述两种可能的页格式，说明它们优缺点和适用场合。 【解答】 （ 1） 磁盘空间管理器支持以页 (单位的数据管理，隐藏了下层硬件（甚至包括 件管理）的细节，且允许高层软件认为 据是一系列以页为单位的磁盘数据集合，是 系结构中最低层的软件模块。 统的磁盘空间管理器通常按三种方式来应用 文件管理功能： 将整个 用 。 让 配给 统一个或几个大的 件，然后自己管理（读 /写）这个文件。 完全自己来管理磁盘。 （ 2） 通过磁盘空间管理器，可将 的 “关系 ”映射到 “关系数据文件 ”，这种 “文件 ”既可能是实际的 件，也可能只是一个虚拟的 件。 一些小规模的 统 实现甚至可能 将关系直接存 储在单独的 件中。 但 更多的现代大型 统，则是把所有关系都集中存储在一个或几个大文件中的复杂结构。这时，我们仍然可在概念上认为每个关系被存储在一个 “虚拟文件 ”中。 （ 3）这时选用堆文件的页存储方式最合适。当不需要检索特点的记录，而只是全文件顺序扫描时，选用堆文件的页存储方式最合适，因为这种情况不需维护顺序，插入插入与删除操作很直接，代价较小，另外，也不需要数据本身之外的额外存储空间和辅助索引文件。 （ 1） 存取数据库记录 /数据页要用到两种类型指针：内存指针与数据库地址 (持久化指针 )。 根据给定的指针或地址寻找 目标对象的过程，称为解引用。给定一个内存指针，查找对象本质上只是对内存单元的一个引用（ *指针名）。给定一个持久化指针，解引用一个对象需要额外的步骤，即需先在“转换表”中查找持久化指针所代表对象的实际内存地址。如果指针所指对象不在内存，则必须从磁盘把它载入，并在转换表中添加新映射项。与内存指针解引用相比，即使转换表中有映射项，通过转换表实现解引用仍是一个慢过程。 指针混写 是一种减少定位已在内存中持久对象所需代价的方法。其基本思想是，当一个主存中对象 /记录所含的持久指针第一次解引用时，这个持久指针所指向 的目标对象被定位如果它不存在内存中，就将它载入内存并同时在转换表中添加一个新的映射项。然后，将存放该持久指针的内存单元，直接修改为目标对象的内存位置指针。下一次同一持久化指针再次被解引用时，就可以直接使用内存引用，从而可避免重复转换内存地址的过程开销。 显然，指针混写包含了持久化指针解引用过程，但前者比后者多了一个在主存中同一位置来回修改“持久化指 针内存指针”过程。指针混写能降低持久化化对象解引用的过程。 （ 2） 排序文件是指按指定的键排序记录集的一种文件组织。虽然在辅存中严格按排序顺序先后安排文件中记录存 储，能显著提高记录集检索性能，但这样做的维护代价太大， 统一般并不这种做，通常是指针把记录按顺序链接起来。 删除记录时仅做标记并留下空位，暂不移动其它记录；而在插入时，相应位置即使没有空位，也暂时不移动其它记录来腾出位置，而是引入溢出页。 对排序文件，页内的记录索引项或目录项通常是严格按顺序的。另外，记录链接自动隐含了页间链接。 （ 3） 缓冲区管理器执行读页请求的基本过程如下： 检查 冲池中是否存在该请求页，如果该页不在 冲池中，则进一步执行以下一些操作。 基于置换策略，选择一个可被置换的 该 数加 1。 如果该 原先页被修改过（即 ），则将原先页写回磁盘。 从磁盘读入新请求页到该 ，同时置 。 返回包含请求页的 址给请求者。 如果被请求页位于缓冲池但未被闩住 (那么该页不会被替换，即没有新页可被读入该页所占据的页框。 当一个缓存页已被修改过 (置 1)，且该页未上闩，所占据页框需读入新页时，通常会触发缓冲区管理器写一个磁盘页。 （ 4） 缓存页备闩住意味着与该页对应的 ，每 次， 1。拴住一个能为高层 件保证缓冲区管理器不会将该页从缓冲池移除，即其它文件页不会被读入该被闩页所占据的页框。一般有缓冲区管理器具体执行 ，但页请求者有责任通知缓冲区管理器 个不再用的页。 （ 5） 当一个页请求发生时，如果缓冲池中所有的页都是脏页，缓冲区管理器会依据缓冲区置换策略选择要换出 并将该 原先的页写回磁盘。从磁盘读入请求页，同时将 0，返回包含请求页的地址给请求者。 （ 6） 与 存管理相比， 冲区管 理器 有以下几个特别功能特性： a) 因为与一般应用相比， 容易 准确预测磁盘页存取顺序。 所以， 冲区管理器通常能更好、更灵活地 选择合适的页置换策略，或采用一些特别的、适合于 境的特殊管理措施。 b) 因可更准确 预测引用模式， 冲区管理器可以使用一些很简单、但却非常有效的预取策略，以有效减少多个连续页的磁盘 I/O 时间。 c) 当决定一个页何时被写回磁盘时， 望或需要有更多的控制权。 （ 7） 假设 A 块、 B 块存储在磁盘相邻的位置上。系统预计或猜测到 A 和 B 两块可能会先后同时被访问，故当 A 块需要 被读入主存时，系统顺带把 B 块也读入主存缓冲区。 这种方案通常可减少 I/O 操作时间，显著提高 统性能，是 化的一个很重要策略。 （ 8） 定长记录格式和可变记录格式（详见书本 ）。 （ 9） 连续槽的页组织格式和基于目录槽的页组织格式（参见书本 ）。 虑一个磁盘：它有 5 个双面盘片，每个盘面 2,000 个磁道，每个磁道 50个扇区，每个扇区 512 字节。另外，假设它的平均寻道时间为 10 （ 1） 计算每个盘面的格式化容量和整个磁盘的格式化容量。 （ 2） 如果磁盘转速为 5,400 转 /分钟，计算磁盘的最 大旋转延迟和平均旋转延迟时间。 （ 3） 在 256、 2048 和 51,200 三个值中，那些值是可能的有效块大小？为什么？ （ 4） 如果每个磁盘块大小占 2 个扇区，试估算传输一个块的平均时间。 【解答】 （ 1） 每个盘面的 格式化 容量 磁道数 *扇区数 *字节数 =2000*50*512 B 49个磁盘的格式化容量盘面数 *每个盘面的容量 =10*49M=490 2） 最大的旋转延迟时间 磁盘 旋转一周所用的时间 1/转速 =60/5400=均旋转等待时间 最大的旋转延迟时间 /2 = = 3） 块是 际读写磁盘的基本单位 ，必须是扇区大小的整数倍；其次 ， 块大小选择要适中， 太小 会导致 I/O 数增加，太大 则 会造成磁盘读写操作浪费加大 ，都不利于管理 。因此，三个值中，只有 2048 可能是有效块大小 。 （ 4）旋转 传输 1 个块的 时间 =读两个扇区所用的时间 =（ 60/5400） *（ 2/50） 输一个块的时间 = 寻道时间旋转延迟时间传输时间 =106 对习题 磁盘，若磁盘块大小为 1,024 字节。假设有一个包含 100,000个元组、每个元组 100 字节的关系文件存储在该磁盘上，并规定记录不允许跨块存储。 （ 1） 每个块中可存放多少个元组？存储整个文件需要多少个块？ （ 2） 估算顺序扫描该关系文件需要的总时间。 （ 3） 如果该磁盘的各盘面上磁头能并行读 /写数据，且磁盘数据是按可能的最优方式安排存储，这种情况下，执行全文件顺序扫描需要多少时间？ 【解答】 （ 1） 每个块可存放元组数 磁盘块大小 /每个元组字节数 =1024/100 = 10 个 存储整个文件需要块数总的元组数 /每个块元组数 =100,000/10=10,000 块 （ 2）顺序扫描文件需总时间文 件总存储块数 *每块存取时间 10,000 *1660,000钟 （ 3）根据题意，可认为读写一个柱面时间 最大的旋转延迟时间 个柱面大小盘面数 10*扇区数 *字节数 =10*50*512 B 按柱面安排连续存储文件需要的柱面数 = 100,000*100/(10*50*512)= 40 （向上取整） 所以，这种情况下，顺序扫描文件需总时间 40* 假设某磁盘具有以下特性：有 10 个盘面，每个盘面 10,000 个磁道；每个磁道 1000 个扇区，每个扇区 512 个字节；每个磁道 20%被用于间隙；磁盘旋转速率 10,000转 /分钟；磁头移动 +回答关于该磁盘的以下问题： （ 1） 磁盘的总容量是多少？ （ 2） 最大寻道时间和最大旋转等待时间分别为多少？ （ 3） 如果一个块是 16,384 字节（即 32 扇区），那么，一个块的传输时间是多少？ 【解答】 （ 1） 磁盘总容量 盘面数 *磁道数 *扇区数 *字节数 =10*10000*1000*512B= 2）最大 寻道 时间磁头跨越所有磁道时间 =1+999 2大的旋 转等待时间磁盘旋转一周的时间 = 60/10,000s = 6 3）一个块（含 32 个扇区 & 31 个间隙 ）所占圆弧度 =32*360/1000)+ 31*360/1000)=60/1000 旋转通过这样大小弧长需时间 =(60/1000) /360 )*6均寻道时间，取 1/3 的最大寻道时间 2 = 均旋转等待时间，取 1/2 的最大旋转等待时间 6=3以，传输一个块的 时间 3 假设我们正在为某磁盘调度 I/O 请求，磁头的初始位置在磁道 4000。已知该磁盘寻道时间可按公式（ 1+移动磁道数 /500）毫秒来计算，到达磁道后访问一个块的平均时间还需要约 秒。假定调度时已经产生的请求共有 4 个，它们所在的柱面分别为 : 1000 / 6000 / 500 / 5000，它们达到的先后时序值分别为 0/1/10/20。试分别计算下列两种情况下，服务完这些请求需要的时间。 （ 1） 采用电梯算法，先从任何方向开始移动都是可能的。 （ 2） 采用 先到先服务算法。 【解答】 （ 1）由于最先到的的请求是 1000， 假设磁头向下运动，那么，电梯调度策略的块访问情况如下表所示。 块请求及被服务顺序 完成时间 1000 (1+3000/500)+00 1+500/500)+000 1+4500/500)+000 1+1000/500)+ 2）若采用先到先服务策略，则各块请求被服务并完成时间如下： 块请求及被服务顺序 完成时间 1000 (1+3000/500)+ 000 1+5000/500)+00 1+5500/500)+000 1+4500/500)+比这两种磁头调度策略，不难发现，采用电梯算法可节省约 18s 时间。 某磁盘传输速率是传送每个 4096 字节块 秒。若要实时播放一部片要求每小时至少传 1节。如果我们能以最好的方式在该磁盘上安排 片的块，能实时播放该影片吗？如 果不能，则需要多少个该型磁盘？且应如何在这些磁盘上安排块，才能使影片在播放时有最小的延迟？ 【解答】 如果我们按连续柱面方式安排存储块，这样可忽略寻道时间和旋转等待时间，那么，传送 1节至少需要时间为：（ 230/ 4096） 31s，约 2 分钟。远小于 1 小时，所以完全可到达实时播放要求。 虑基于目录槽变长记录页格式。 （ 1） 管理目录槽的一种方法是使用最大目录槽号，并在页创建时分配目录数组。给出赞成和反对该方法的理由。 （ 2） 建议该方法的一种改进，使得允许我们能在不移动记录和不改变记录 情况下，按某个字段排序记录。 （ 3） 估算顺序扫描该关系文件需要的总时间。 【解答】 （ 1） 采用最大目录槽号方法比较简单，但不灵活。因为这种方法很容易导致保留过多的槽或槽不够用情况，这是因为系统无法预测页中存储记录的长度。 （ 2）一种允许记录按指定的字段排序的改进方案是：在页首存储象 结构形式为记录槽目录项数组。 设我们使用 方案，有 4 个数据盘和一个冗余盘。假设块为单字节，如果数据盘中相应的块值如下，试给出冗余盘的块值。 （ 1） 01010110, 11000000,00111011 和 11111011。 （ 2） 11110000， 11111000， 00111111 和 00000001。 【解答】（ 1） 01010110；（ 2） 00110110 用带有 7 个磁盘的 方案 ,描述从下列故障中恢复所要采取的步骤 （ 1） 盘 1和盘 7。 （ 2） 盘 1和盘 4。 【解答】 （ 1）先用 2#、 3#、 5#号盘恢复 盘 1#的数据，再用 1#、 3#、 4#号盘恢复 盘 7#的数据。 （ 2）先用 2#、 3#、 5#号盘恢复 盘 1#的数据，再用 1#、 2#、 6#号盘恢复 盘 4#的数据。 第五章 数据库 索引技术 要回答以下问题。 （ 1） 如果要频繁进行：基于某字段值的范围搜索；执行插入和扫描操作，不关心记录顺序；基于特定的属性值搜索记录。那么，我们应分别选择基本文件组织方式中的哪一种？ （ 2） 说明索引项的三种基本形式。 （ 3） 说明顺序索引的基本概念，并指出稠密索引在哪些情况下，不需要数据文件是排序文件。说明稀疏索引的概念，稀疏索引肯定是聚集索引吗？相应的数据文件肯定是排序文件吗？请解释原因。二级或二级以上索引肯定是稀疏索引吗？为什么？ （ 4） 辨析以下概念对，说明它们之间的差异。 （ a） 聚簇文件与聚集索引； （ b） 稠密索 引与稀疏索引； （ c） 主（码）索引与辅助索引。 【解答】 （ 1）以操作代价作为依据： 要频繁作基于字段值的范围搜索：应该选用排序文件作为基本的文件组织方式。 要频繁执行插入和扫描操作，应该选用堆文件作为基本的文件组织方式。 要频繁作基于特定属性值的搜索记录，应该选用散列文件作为基本的文件组织方式。 （ 2）索引项的三种基本形式： 索引项 k*就是数据记录本身，没有另外单独的索引文件。 ，有独立的索引文件，每个索引项只能给出一个 , 有独立的索引文件，每个索引项允许包含多 个 （ 3） 顺序索引是指按索引键值顺序来组织索引项的索引文件。 如果每个索引键值都至少对应有一个索引项，则称索引为稠密索引 。在稠密索引情况下，如果每个记录都对应有一个索引项，或在 每个索引项中存储包含键值的记录指针链表 ，则可以不要求数据文件是排序的。 只为搜索键的某些值建立索引项的索引称为稀疏索引， 稀疏索引必须是聚集索引 。 聚集索引 是指一 个索引文件中索引项的排序方式和数据文件记录的排序方式一致 的索引方式 ， 所以，与稀疏索引对应的数据文件一定是排序文件。 二级或二级以上索引肯定是稀疏索引，因为如 果还是像稠密索引那样一对一地建立二级索引的话，索引项或索引文件大小没有实质减少，没有什么意义。作为索引一定是排好序的，故在低级索引基础上可建立更稀疏的上级索引。 （ 4） 区别聚簇文件与 聚集索引 聚簇文件：指数据文件，这种数据文件的每个页中，都只存放同一个关系表的记录。 聚集索引：指一种索引文件，这类 索引文件中索引项的排序方式和数据文件记录的排序方式一致时 。虽然一个数据文件可以根据不同索引键建立不同索引文件，但至多只能有一个索引文件是聚集的。 稠密索引与稀疏索引（参见前一小题说明） 区别主 (码 )索引与辅助 索引 主索引或主码索引：指 搜索键恰好是主码的索引 。因为一个关系数据文件最多只有一个主码，所有每个关系最多也只有一个主码索引。通常主码索引往往也是聚集索引。主码索引中肯定没有重复索引项，因为主码肯定是候选码，没有重复键。 辅助索引：非主索引的索引文件。辅助索引中通常会有重复索引项。 虑图 示的阶数 m=4 的 B+树索引。 （ 1） 标示插入数据项 9*之后的 B+树，并指出完成该插入需要读多少个页和写多少7 3 8 51 8 * 2 7 * 3 2 * 3 9 * 4 1 * 4 5 *9 1 * 9 9 *1 * 2 * 5 * 6 * 8 * 1 0 *8 1 8 3 2 4 05 0R O O * 5 8 * 7 3 * 8 0 *图 题 图 6 8 *9 0 9 85 1 * 5 2 * 5 6 * 6 0 *6 9 * 7 0 * 7 9 * 9 8 * 9 9 * 1 0 0 * 1 0 5 *3 0 * 3 1 *3 6 * 3 8 *3 5 4 2 5 0 6 51 0 3 0 8 0R O O 8 1 * 8 2 *4 2 * 4 3 *9 4 * 9 5 * 9 6 * 9 7 *A B I 2 I 3L 1L 2L 3L 4L 5 L 6L 7L 8图 题 图 个页。 （ 2） 给出在原树中删除数据项 8*之后的 B+树，并指出完成该操作需要读多少个页和写多少个页。 （ 3） 给出在 原树中先插入数据项 46*，然后再删除数据项 52*之后的 B+树。 （ 4） 给出在原树中，依次删除 32*、 39*、 41*、 45*和 73*之后的 B+树。 【解答】 （ 1） 由图看出插入 9*不需要分裂，直接插入即可。 由于索引项即数据文件本身，从根结点到索引项 读 3 个页。只有叶结点改过，所以 写 1 个页 。插入后的局部图如下： 5 08 1 8 3 2 4 08 * 9 * 1 0 *（ 2）删除 8*后要跟前一个索引项重组，从根结点到两个索引项要读 4 个页。操作完成后两个叶结点和一个中间结点是脏页，故要写出 3 个页。删除后的局部图： 5 06 1 8 3 2 4 06 * 1 0 *1 * 2 * 5 *(3) 可直接插入数据项 46*。删除数据项 52*则要合并重组，操作完成后的局部图： 4 08 1 8 3 29 1 * 9 9 *5 0 8 55 8 * 7 3 * 8 0 *4 1 * 4 5 * 4 6 *(4) 依次删除 32*、 39*、 41*、 45*、 73*后的图： 1 * 2 * 5 * 6 *8 1 8 5 0 7 35 2 * 5 8 *1 8 * 2 7 *8 * 1 0 * 8 0 * 9 1 * 9 9 * 虑图 示 B+树索引：内节点可容纳 4 个键值和 5 个指针；叶节点中直接存储数据记录，可容纳 4 条记录且相邻叶节点之间用双链连接在一起。回答以下问题。 （ 1） 指出回答查询“取搜索键值大于 38 的所有记录”时，需要读取的有关节点。 （ 2） 给出插入 109*后的 B+树。 （ 3） 给出从原树中删除 81*后的 B+树。 （ 4） 给出一个插入时会导致树高度增加的键值。 （ 5） 图中没有详细给出子树 A、 B 和 C。你能推测出这些子树的内容和形状吗？ 【解答】 (1) 查询大于 38*的所有记录，要读取的节点有： 2,3,5,7,2) 插入 109*后，原 点需要分裂，完成操作后的局部图： (3) 删除 81*后， 7 两个节点要重组，操作完成后的局部图如下： (4) 插入任何 65,79之间的搜索键值，都会分裂 点，而 是满的，向上分裂到根结点，根结点也是满的，就会导致高度增加一层。 (5) 关于子树 A、 B、 C，我们可推出以下几件事： 1） 它们都是树高为 1 的子树，因为它们的相邻子树，即以 根节点的子树树高都是 1； 2）子树 A 包含的键值树肯定少于 10 个，子树 B 所包含的键值在范围 10,20）之间，子树 C 所包含的键值在范围 20,30）之间； 3）每个中间节点至少会含有 3 个键值和 3 个指针。 定我们有一个排序文件，希望在该排序文件基础上构造一个稠密 B+树聚集索引。 （ 1） 最简单的方案是：扫描文件，并利用 B+树插入算法将记录逐个插入到树中。指出该方案在性能和存储利用率方面存在的问题。 （ 2） 说明如何用批量加载算法来改进以上方案。 【解答】 （ 1） 利用标准的 B+树插入算法，逐项插入，这种方法可能代价非常昂贵，因为每个项加入都需要从根开始到达合适的叶节点。尽管在连续请求时索引层次的页，可能仍保持在缓冲池中，但这样的开销可能仍然非常可观 ，在树构建过程中会经历大量叶节点及相关内节点的分裂调整 。 （ 3）而采用批量加载方法的效率则要高得多，在树的批量构建过程中可以有效避免叶节点分裂调整，只有少量内节点的顺次分裂调整，以及与树高 相对应的有限几次根节点调整。批量加载构建 B+树的基本过程步可描述如下： 第一步，从一个关系记录集创建要插入到索引的数据项 。 该步包括扫描关系记录集，并生成和写出相应的数据项。其代价为 (R+E)次 I/里， R 是包含记录集的数据文件页数， E 是包含数据项的总页数。 第二步，排序数据项；外部排序含数据项的 E 个页，保守估计需要 3E 次 I/分）。 第三步，从排序好的数据项中建立 B+树索引。因为第二步中已排序数据项的数据页，可在它们从排序步输出时，直接调用批量加载算法依次加入到新的 B+树 中，因此，第三步的代价只是写出所有（内节点）索引页的代价。 批量加载算法的总代价为： R+4E+(B 树索引节点数 ) 虑表 示的 系示例。构造以下几种情况下的 4 阶 B 树，假定简单使用溢出页处理重复键值情况。要求使用比 k*约定更清晰的方式，在B+树中标示数据项。 （ 1） 段上的稠密 B+树索引，索引项为数据项。 （ 2） 段上的稀疏 B+树索引，索引项为数据项。 （ 3） 段上的稠密 B+树索引，索引项为键值加记录指针。为便于问答这个问题，我们假定实际元组记录存储按图中给定顺序的排序文件中，每 个页可存三个元组，前三个元组存储在第 1 个页的第 1/2/3 槽中，第 4/5/6 个元组存储在第 2 个页的第 1/2/3 槽中，。 【解答】 1 1 . 5 3 8 3 1 . . . 1 2 . 5 3 8 3 2 . . . 1 8 . 5 3 6 6 6 . . . 1 9 . 5 3 6 8 8 . . . 5 3 9 0 1 . . . 1 8 . 5 3 9 0 2 . . . 1 8 . 5 3 9 0 3 . . . 1 8 . 5 3 9 0 4 . . . 5 3 9 0 5 . . . 1 8 . 5 3 9 0 6 . . . 1 8 . 5 3 9 0 2 . . . 5 3 6 5 0 . . . 1 9 . 5 4 0 0 1 . . . 1 9 . 5 3 0 0 5 . . . 1 9 . 5 4 0 0 9 . . O O 41 . 8 : 2 . 2 : 3 . 2 : 3 . 4 : 3 . 5 : 3 . 4 : 3 . 8 : 3 . 4 : 3 . 4 : 3 . 4 : 3 . 8 : 3 . 4 : 3 . 4 : 3 . 8 : 3 . 8 : 溢 出 链溢 出 链( a ) 习 题 5 . 5 题 解 附 图 - 1( c ) 习 题 5 . 5 题 解 附 图 - 31 1 . 5 3 8 3 1 . . . 1 2 . 5 3 8 3 2 . . . 1 8 . 5 3 6 6 6 . . . 1 9 . 5 3 6 8 8 . . O T( b ) 习 题 5 . 5 题 解 附 图 - 2图 题 解附图 （ 1）建立 的稠密索引，见图 a） （ 2）建立 的稀疏索引，见图 b） （ 3）建立 的稠密 B+树索引，见图 c） 注意，数据项未必按数据记录同样的顺序存储，因为它们可能按不同的顺序被插入到 B+树中。我们假设采用简单的插入算法，首先以常规方法定位叶节点，如叶节点中已经有同样键值的数据项，就将新数据项安排到与该叶节点链接的溢出页。这样 ，可保证每个叶节点中的数据项都有不同的键值。这种做法会导致的一个问题是：当叶节点满而需要分裂时，必须扫描溢出链以确保当一个键值被移动到一个新叶节点时，所有该键的重复项也能伴随移动到新叶节点的溢出页中。 另一种方案是分别维护每个键值的重复项溢出链，但考虑到每个页的容量限制，且一个给定键值的重复项数可能很少，故这个方案可能导致很差的空间利用率。 于可扩展散列，请回答以下问题。 （ 1） 解释为什么需要全局位深度和局部位深度。 （ 2） 在一个引发目录项翻倍的插入后，有多少个桶恰好只有一个目录项指向它？如果从这些桶中删除 一个项，那么目录项数是否会发生变化？请给出简要解释。 （ 3） 翻倍目录项时，我们需要检查所有局部位深度等于全局位深度的桶吗？ （ 4） 对检索一个给定键值记录，可扩展散列能否保证只用 1 次磁盘 I/O 完成？ （ 5） 如果散列函数在数据项上严重偏斜，那么，关于桶目录大小和桶空间利用率方面，你能得出什么结论？ （ 6） 对相同数据项，给出一个线性散列方法组织存储需要的总页数多于可扩展散列存储方法的具体例子。 【解答】 （ 1） 可扩展散列允许根据插入或删除而引起的数据项数目变化，动态调整目录项的大小。一旦目录项大小变化（翻倍增加或翻倍缩小），应用到搜索键 值的散列函数值需保留的有效位数也要随之变化。扩展散列中用全局位深度（ 定散列函数值需保留的有效位数。 目录大小的增加并不会导致每个新目录项创建新数据桶。目录项翻倍增加时，所有新目录项都与对应的老目录项共享相同的数据桶。当一个被两个或更多目录项所共享的数据桶需要分裂时，并不会导致目录项翻倍增加。这意味着我们需要知道每个桶是否被两个或多个目录项共享。这个信息由局部位深度 (示。 （ 2）有且只有两个桶是这种情况（只有一个指向它的目录项），这是因为导致目录翻倍哪个新插入项对应桶必须分裂为两个桶。如果恰好有一个数据项要从这两个桶中的某个桶删除，那么可能会导致两个桶合并，但是否一定进行桶合并，取决于具体的算法策略。如果算法只合并处理空桶，就不一定会发生桶合并情况；而如果算法策略是只要可能就合并桶，则就会导致插入翻倍目录的逆操作不仅会导致桶合并，而且会导致目录减半压缩。 （ 3）不需要。因为仅当一个桶需要分裂时，才需要检查该桶的局部位深度。 （ 4）可扩展散列并不保证仅用 1次磁盘存取来完成记录检索。当目录文件不在主存，或数据桶中存储的只是记录指针或记录指针列表时，都可能需要 额外的 I/O。 （ 5） 如果散列函数在数据项上严重偏斜，那么，桶目录大小和桶空间利用率都会很差。 （ 6） 对于以下键值序列： 8, 16, 24, 32, 40, 48, 56, 64, 128, 7, 15, 31, 63, 3, 1, 10, 4。 可扩展散列需要 9个页（包括目录页），而线性散列为 10个页。具体索引结构可参见习题题解附图。 虑图 示的可扩展散列索引文件。回答以下问题。 （ 1） 从图中，我们能否看出哪个是最后插入的项，为什么？ 0 0 00 0 10 1 00 1 13数 据 页 ( 桶 )目 录1 0 01 0 11 1 01 1 14 * 1 2 * 2 0 * 3 6 *桶 A 236 4 * 1 6 *桶 5 * 2 1 *桶 *桶 * 7 * 5 1 *桶 * 4 4 *9 * 2 5 * 5 *1 0 *3 1 * 1 5 * 7 * 3 *L e v e l = 0 , N = 4N e x t = 0数 据 文 件 桶 的 存 储 页h 00 00 11 01 1h 10 0 00 0 10 1 00 1 1图 题 图 图 题 0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 141 6 3 2 4 8 6 44121 2 8桶 1 02桶 43桶 A 28 2 4 4 0 5 64桶 A 37 1 5 3 1 6 33桶 D 21 6 3 2 4 8 6 4 8 2 4 4 0 5 6 桶 811 03 7 1 5 3 146 3N e x t = 30 0 0 0 00 0 1 0 10 1 0 1 00 1 1 1 11 0 0 0 01 1 0 1 01 0 1 0 1h 1 h 0L e v e l = 1桶 桶 2桶 C 2桶 D 2（ a ) 习 题 5 . 6 题 解 附 图 - 1 ( b ) 习 题 5 . 6 题 解 附 图 - 2 图 题 解附图 （ 2） 若已知到目前为止没有删除发生，那么，从图中我们能 否看出哪个是最后插入的项？ （ 3） 若已知到目前为止没有删除发生，那么，从图中我们能否看出哪个是导致桶分裂的最后插入项？ （ 4） 给出或标示插入 68*后的索引文件结构图。 （ 5） 给出或标示插入 17*、 69*后的索引文件结构图。 （ 6） 给出或标识删除 21*后的索引文件结构图。 【解答】 （ 1） 不能，它可能是索引中的任何数据项之一。 从当前已有索引项中，我们通常总能找出多个以某个特别键作为最后插入项的插入删除序列。例如，考虑数据项 16，若先依次插入数据项 1 5 21 10 15 7 51 4 12 36 64 8 24 56 16（最后插入项） ，然后再依次删除 56、 24 和 8 就会导致图 可扩展索引结构布局。显然，对以任何一数据项做最后插入项，我们都总能找到一个或多个插入删除序列。 （ 2） 虽然我们无法断定那个是最后的插入项，但可以断定最后一个插入项肯定没有导致桶分裂，因为已分裂的桶只有 A，且 A 与 中数据项总数为 6，而不是 5。 （ 3） 首先，导致桶分裂的最后插入项不可能在桶 C 中，因为 C 只能与跟它局部位深度也是 2 的 B 或 D 构成分裂映象对，且 C 与 B，或 C 与 D 的数据项数和都为 4，少于最少要求的项数 5。 如果开始时全局位深度为 1，且还没有桶 情况下，那么，导致 桶分裂的最后插入项应在 B 与 D 桶中，因为 D 是 B 位深度相同（均为 2），且 D 与 B 桶的总数据项数为 6（超过 5）。 综合以上分析，我们可得出结论：如果开始时全局位深度位 2，且没有发生过删除操作，那么导致桶分裂的最后插入项肯定在 A 与 中。 （ 4） 插入 68*后的索引文件结构图见：图 a） 桶 桶 桶 A 2桶 A 3（ a） 习题 解附图 桶 桶 A 2桶 B 2（ b）习题 解附图 题 解附图 （ 5） 插入 17*、 69*后的索引文件结构图图见：图 b） （ 6） 删除 21*后的索引文件结构图见：图 c） 桶 桶 桶 A 2图 c）习题 解附图 于可线性散列，请回答以下问题。 （ 1） 如果允许使用溢出页，线性散列如何保证提供只比 1 多一点（比如 等值搜索平均代价。 （ 2） 对共包含有 N 个数据项（即 N 个记录）、每页可存储 P 个记录的情况，如果采用线性散列方法来组织存储，且假设页的平均利用率为 80%，那么，等值搜索的最坏代价是多少？ （ 3） 如果散列函数在数据项上 严重偏斜，那么，在数据页的空间利用率方面，你能得出什么结论？ （ 4） 对相同数据项，给出一个线性散列方法组织存储需要的总页数少于可扩展散列方法的具体例子。 【解答】 （ 1） 在一个轮中，线性散列所有的桶将按顺序依次分裂一次。如果 散列函数对散列键分布均匀 ，那么，这种在一个轮中的轮流分裂方式，一般都能导致键值在所有桶中的重新分配。即使一个桶有溢出页，经这样的一轮分裂下来，每个桶增加的溢出页长度一般不会超过 1（如果散列函数分布很好的话）。 （ 2） N / (这是当散列函数极度偏斜，所有键都被映射到同一个桶的情况。另外，这里占 有率，会影响需要的存储页数。 （ 3） 参考习题 )附图。如果系列数据的键值为 2i, ik，那么，通过选择适当的 k 值，会导致所有的数据项都被映射到桶 0 中。若规定每次当需要增加一个溢出页到桶 0 时，都会导致桶分裂。那么，这是空间利用率，还不到 50。 （ 4） 考虑如下键值序列： 0, 4, 1, 5, 2, 6, 3, 7。且两者的散列函数相同，且每个页都可容纳 4 个记录。在这种情况下，可扩展散列需要 4 个数据页和 1 个目录页，而线性散列只需要正好 4 个页。 虑一个包含有 1,000,000 个元组的关系 R(a, b, c, d)。已知：每页可容纳 10个元组； R 按堆文件组织、记录无序。假设属性 a 是 R 的一个候选键，取值范围 0 999,999。若有三种可能的存取路径： 1）扫描堆文件 R； 2) 利用 的 B+树索引； 3）利用 的散列索引。那么，对以下给定的每个查询，指明具有最小查询处理代价应选用的存取方法。 （ 1） 检索 R 的所有元组； （ 2） 检索满足 a(T)1/2以保证可按两阶段完成排序，相应算法代价都为 M+2T 次 I/基于散列算法要求可用缓存页数 B 足够容纳最大的划分 (子桶 )，在划分均匀情况下，也是要求B (T)1/2。但若散列划分不均匀，则可能需要比 (T)1/2 更大一些的 B 值 。散列算法代价也是 M+2T 次 I/虑到 统有优化得很好的排序工具 (函数 )、排序方法的投影结果集是排序的、散列可能存在偏斜和 代价等因素，选用排序方法似乎更好些。 （ 6） 对等值连接，散列索引 通常 能提供很好的性能 。假 设两个待连接关系的大小分别为 M、 N 个页。当缓存较大 B (f*,N)1/2（这里， f 为主存散列因子）时，散列连接代价只有（ M+N） *3 次 I/果还有更大的缓存可能，除了实现正常散列算法需要的主存页数外，还有额外缓存能驻留存储 1 个甚至更多个桶，那么，采用混合散列连接还可以大幅度地改善性能。 B (,N)1/2 时，改进的排序 M+N） *3 次 I/排序 一个额外的优势可产生 按连接键 排序的 输出 结果 。当主存很大时，用散列连接效果通常会更好，但当需要 基于连接属性的排序输出，也可能选择排序 当可用主存很少，排序需要多个阶段，散列需要递归进行多次子桶划分时，排序 另外，对非等值连接，不能用散列连接算法，我们 只能选用排序 索引嵌入循环等连接实现方法。 （ 7） 混合索引连接能显著改善性能 。例如， 通过在划分阶段（而不是将它留到探测阶段）就完成首个桶的元组匹配比较， 这能节省掉第一个分区的读 /写代价。 （ 8） 全关系算法指操作施加于整个关系上而非施加于单个元组上，关系中的多个不同元组可能会共同影响一个结果元组，或已处理过 的元组对随后的元组处理有影响。如果希望一趟完成全关系算法，那么要求主存比较大。对于消除重复或分组聚合等一元操作，要求能容纳得下整个运算结果。对集合并交差，或连接等 二元操作符 ，要求能至少能容纳整个较小输入关系 。 （ 9） 略。 （ 10） 缓冲区置换策略 影响 连接性能的一个典型例子是：在简单的嵌入循环连接时，使用 当 关系表不能全部载入主存 时 ，缓冲池置换策略是非常关键的。不妨假设我们有 M 个缓存页，而其中 N 个已被第一个关系占用，若第二个关系大小为 ，这样， 除了 P 个页外，第二个关系的所有页都能被读入缓冲池。由于我们必 须多次扫描第二个关系，这 时， 若使用 当我们重新需要某个页时，这个页因为很长时间没有使用，可能早已被替换 移出 了，因此，可能每个页都需要重新读 磁 盘。而若是采用 总先替换最近用过的页，长时间未用的那些老页可能一直留在缓冲 池 ，这样第二次扫表内层关系时，开始的 哪些 页大都能在缓冲池中找到。每次扫描内层关系（第二关系），可能只需要重复读 页。 考虑一个每页 10 个记录、共有 5,000,000 条记录的关系 R(a,b,c,d)。假设 值从 0 4999,999，且 R 数据文件基于 序。若对 R 的元组，有三种可用存取方法： a) 直接扫描排序文件 R； b)利用 的聚集B+树索引； c)利用 的线性散列索引。试对每个以下关系代数查询： （ 1） 00 00 +树索引，则该索引是否能为排序提供更便宜的代价？如果索引是非聚集的，或是一个散列索引，则结果又如何？ 【解答】 （ 1） B=10, 初始阶段将产生 5000个排序子表，每个子表长度为 10个页； 读入 10， 000个页，投影后写出 5000个页，需要总代价 =10000 5000 15000。 （ 2） 为合并 1000 个子表，我们还需另 外 3个 归并 阶段，代价为 2*3*5000=30000I/ 3） 可 合理假设每页可存储 10*4 个 性， B+树至少会有 100,000/(10*4)=2500个叶节点。因此，扫描 B+树本身至少需要 2500I/价。利用 的聚集 B+树索引扫描关系的代价为 12500（超过简单堆文件扫描的 10000次）。利用 能会超过 2500 100000,达到 2500 100000*10次 （假定每页元组数 10)。如果散列索引是聚集的且散列桶中直接存储元组，则使用散列索引 检索并完成排序代价可能会很好。 （ 4） 利用 +树索引，扫描代价为 12500。因为 描 B+树检索出的 对不会有重复，不需要在进行排序消除重复，因此，产生查询结果的总估计代价也是 12500,代价远远低于简单排序归并的 (15000+30000)次I/非聚集 B+树检索所有目标元组的代价