49章习题解答.docx
- 文档编号:18178305
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:73
- 大小:365.46KB
49章习题解答.docx
《49章习题解答.docx》由会员分享,可在线阅读,更多相关《49章习题解答.docx(73页珍藏版)》请在冰点文库上搜索。
49章习题解答
第4章数据存储与组织管理
4.1简要回答以下问题。
(1)描述磁盘空间管理器的主要作用,并说明它与OS文件系统的关系。
(2)解释关系数据库系统中关系表与文件的关系。
(3)如果有一个大文件需要频繁执行顺序扫描,那么,为该文件选择哪种页存储方式最合适?
(4)分别描述持久化指针解引用(dereference)和指针混写的这两个基本过程,它们之间有何联系?
(5)说明排序文件中的记录及页的基本存储组织方式。
(6)解释缓冲区管理器处理一个读页请求的过程。
如果被请求页位于缓冲池但未被闩住(pinned),那么情况会怎样?
缓冲区管理器何时写一个磁盘页?
(7)一个缓存页被闩住(bepinned)意味着什么?
一般由谁负责给缓存页上闩,由谁负责给缓存页解闩?
(8)当一个页请求发生时,如果缓冲池中所有页都是脏页,将会发生什么?
(9)与OS缓存管理相比,DBMS缓冲区管理器具有那些独特的重要能力?
(10)什么是预取?
解释为什么这种策略很重要。
(11)描述两种可能的记录格式,并指明它们的优缺点。
(12)描述两种可能的页格式,说明它们优缺点和适用场合。
【解答】
(1)磁盘空间管理器支持以页(page)为单位的数据管理,隐藏了下层硬件(甚至包括OS文件管理)的细节,且允许高层软件认为DB数据是一系列以页为单位的磁盘数据集合,是DBMS体系结构中最低层的软件模块。
DB系统的磁盘空间管理器通常按三种方式来应用OS的文件管理功能:
⏹将整个DB存储在一个或几个磁盘文件中,调用OS功能实现流式文件的磁盘R/W。
⏹让OS分配给DB系统一个或几个大的OS文件,然后自己管理(读/写)这个文件。
⏹完全自己来管理磁盘。
(2)通过磁盘空间管理器,可将DB中的“关系”映射到“关系数据文件”,这种“文件”既可能是实际的OS文件,也可能只是一个虚拟的OS文件。
一些小规模的DB系统实现甚至可能将关系直接存储在单独的OS文件中。
但更多的现代大型DB系统,则是把所有关系都集中存储在一个或几个大文件中的复杂结构。
这时,我们仍然可在概念上认为每个关系被存储在一个“虚拟文件”中。
(3)这时选用堆文件的页存储方式最合适。
当不需要检索特点的记录,而只是全文件顺序扫描时,选用堆文件的页存储方式最合适,因为这种情况不需维护顺序,插入插入与删除操作很直接,代价较小,另外,也不需要数据本身之外的额外存储空间和辅助索引文件。
(1)存取数据库记录/数据页要用到两种类型指针:
内存指针与数据库地址(持久化指针)。
根据给定的指针或地址寻找目标对象的过程,称为解引用。
给定一个内存指针,查找对象本质上只是对内存单元的一个引用(C语法:
*指针名)。
给定一个持久化指针,解引用一个对象需要额外的步骤,即需先在“转换表”中查找持久化指针所代表对象的实际内存地址。
如果指针所指对象不在内存,则必须从磁盘把它载入,并在转换表中添加新映射项。
与内存指针解引用相比,即使转换表中有映射项,通过转换表实现解引用仍是一个慢过程。
指针混写是一种减少定位已在内存中持久对象所需代价的方法。
其基本思想是,当一个主存中对象/记录所含的持久指针第一次解引用时,这个持久指针所指向的目标对象被定位――如果它不存在内存中,就将它载入内存并同时在转换表中添加一个新的映射项。
然后,将存放该持久指针的内存单元,直接修改为目标对象的内存位置指针。
下一次同一持久化指针再次被解引用时,就可以直接使用内存引用,从而可避免重复转换内存地址的过程开销。
显然,指针混写包含了持久化指针解引用过程,但前者比后者多了一个在主存中同一位置来回修改“持久化指⇔针内存指针”过程。
指针混写能降低持久化化对象解引用的过程。
(2)排序文件是指按指定的键排序记录集的一种文件组织。
虽然在辅存中严格按排序顺序先后安排文件中记录存储,能显著提高记录集检索性能,但这样做的维护代价太大,DB系统一般并不这种做,通常是指针把记录按顺序链接起来。
删除记录时仅做标记并留下空位,暂不移动其它记录;而在插入时,相应位置即使没有空位,也暂时不移动其它记录来腾出位置,而是引入溢出页。
对排序文件,页内的记录索引项或目录项通常是严格按顺序的。
另外,记录链接自动隐含了页间链接。
(3)缓冲区管理器执行读页请求的基本过程如下:
⏹检查DB缓冲池中是否存在该请求页,如果该页不在DB缓冲池中,则进一步执行以下一些操作。
⏹基于置换策略,选择一个可被置换的frame,将该frame的pin_count计数加1。
⏹如果该frame中原先页被修改过(即dirty=1),则将原先页写回磁盘。
⏹从磁盘读入新请求页到该frame中,同时置dirty=0。
⏹返回包含请求页的frame地址给请求者。
如果被请求页位于缓冲池但未被闩住(pinned),那么该页不会被替换,即没有新页可被读入该页所占据的页框。
当一个缓存页已被修改过(dirty位置1),且该页未上闩,所占据页框需读入新页时,通常会触发缓冲区管理器写一个磁盘页。
(4)缓存页备闩住意味着与该页对应的pincount>0,每pin一次,pincount加1。
拴住一个能为高层DBMS软件保证缓冲区管理器不会将该页从缓冲池移除,即其它文件页不会被读入该被闩页所占据的页框。
一般有缓冲区管理器具体执行pin/unpin页,但页请求者有责任通知缓冲区管理器unpin一个不再用的页。
(5)当一个页请求发生时,如果缓冲池中所有的页都是脏页,缓冲区管理器会依据缓冲区置换策略选择要换出frame,并将该frame中原先的页写回磁盘。
从磁盘读入请求页,同时将dirty置0,返回包含请求页的地址给请求者。
(6)与OS缓存管理相比,DBMS缓冲区管理器有以下几个特别功能特性:
a)因为与一般应用相比,DMBS更容易准确预测磁盘页存取顺序。
所以,DBMS缓冲区管理器通常能更好、更灵活地选择合适的页置换策略,或采用一些特别的、适合于DB环境的特殊管理措施。
b)因可更准确预测引用模式,DBMS缓冲区管理器可以使用一些很简单、但却非常有效的预取策略,以有效减少多个连续页的磁盘I/O时间。
c)当决定一个页何时被写回磁盘时,DBMS希望或需要有更多的控制权。
(7)假设A块、B块存储在磁盘相邻的位置上。
系统预计或猜测到A和B两块可能会先后同时被访问,故当A块需要被读入主存时,系统顺带把B块也读入主存缓冲区。
这种方案通常可减少I/O操作时间,显著提高DBMS系统性能,是DBMS优化的一个很重要策略。
(8)定长记录格式和可变记录格式(详见书本4.5节)。
(9)连续槽的页组织格式和基于目录槽的页组织格式(参见书本4.4节)。
4.2考虑一个磁盘:
它有5个双面盘片,每个盘面2,000个磁道,每个磁道50个扇区,每个扇区512字节。
另外,假设它的平均寻道时间为10msec。
(1)计算每个盘面的格式化容量和整个磁盘的格式化容量。
(2)如果磁盘转速为5,400转/分钟,计算磁盘的最大旋转延迟和平均旋转延迟时间。
(3)在256、2048和51,200三个值中,那些值是可能的有效块大小?
为什么?
(4)如果每个磁盘块大小占2个扇区,试估算传输一个块的平均时间。
【解答】
(1)每个盘面的格式化容量=磁道数*扇区数*字节数=2000*50*512B≈49MB
整个磁盘的格式化容量=盘面数*每个盘面的容量=10*49M=490MB
(2)最大的旋转延迟时间=磁盘旋转一周所用的时间=1/转速=60/5400=0.011s
平均旋转等待时间=最大的旋转延迟时间/2=0.011s/2=0.0055s
(3)块是DBMS与OS实际读写磁盘的基本单位,必须是扇区大小的整数倍;其次,块大小选择要适中,太小会导致I/O数增加,太大则会造成磁盘读写操作浪费加大,都不利于管理。
因此,三个值中,只有2048可能是有效块大小。
(4)旋转传输1个块的时间=读两个扇区所用的时间=(60/5400)*(2/50)≈0.44ms
传输一个块的时间=寻道时间+旋转延迟时间+传输时间=10ms+5.5ms+0.5ms=16ms
4.3对习题4.2中磁盘,若磁盘块大小为1,024字节。
假设有一个包含100,000个元组、每个元组100字节的关系文件存储在该磁盘上,并规定记录不允许跨块存储。
(1)每个块中可存放多少个元组?
存储整个文件需要多少个块?
(2)估算顺序扫描该关系文件需要的总时间。
(3)如果该磁盘的各盘面上磁头能并行读/写数据,且磁盘数据是按可能的最优方式安排存储,这种情况下,执行全文件顺序扫描需要多少时间?
【解答】
(1)每个块可存放元组数=磁盘块大小/每个元组字节数=1024/100=10个
存储整个文件需要块数=总的元组数/每个块元组数=100,000/10=10,000块
(2)顺序扫描文件需总时间=文件总存储块数*每块存取时间
≈10,000*16ms=160,000ms=2.7分钟
(3)根据题意,可认为读写一个柱面时间=最大的旋转延迟时间=0.011s
一个柱面大小=盘面数[10]*扇区数*字节数=10*50*512B
按柱面安排连续存储文件需要的柱面数=100,000*100/(10*50*512)=40(向上取整)
所以,这种情况下,顺序扫描文件需总时间=40*0.011s≈0.5s
4.4假设某磁盘具有以下特性:
有10个盘面,每个盘面10,000个磁道;每个磁道1000个扇区,每个扇区512个字节;每个磁道20%被用于间隙;磁盘旋转速率10,000转/分钟;磁头移动n个磁道所需时间为1+0.0001n毫秒。
请回答关于该磁盘的以下问题:
(1)磁盘的总容量是多少?
(2)最大寻道时间和最大旋转等待时间分别为多少?
(3)如果一个块是16,384字节(即32扇区),那么,一个块的传输时间是多少?
【解答】
(1)磁盘总容量=盘面数*磁道数*扇区数*字节数=10*10000*1000*512B=47.7GB
(2)最大寻道时间=磁头跨越所有磁道时间=1+0.0001*9999≈2ms
最大的旋转等待时间=磁盘旋转一周的时间=60/10,000s=6ms
(3)一个块(含32个扇区&31个间隙)所占圆弧度
=32*0.8*(360/1000)+31*0.2*(360/1000)=31.8*360/1000
旋转通过这样大小弧长需时间=((31.8*360/1000)/360)*6ms≈0.19ms
平均寻道时间,取1/3的最大寻道时间=2ms/3=0.67ms
平均旋转等待时间,取1/2的最大旋转等待时间=6ms/2=3ms
所以,传输一个块的时间=0.67ms+3ms+0.19ms≈3.86ms
4.5假设我们正在为某磁盘调度I/O请求,磁头的初始位置在磁道4000。
已知该磁盘寻道时间可按公式(1+移动磁道数/500)毫秒来计算,到达磁道后访问一个块的平均时间还需要约8.3毫秒。
假定调度时已经产生的请求共有4个,它们所在的柱面分别为:
1000/6000/500/5000,它们达到的先后时序值分别为0/1/10/20。
试分别计算下列两种情况下,服务完这些请求需要的时间。
(1)采用电梯算法,先从任何方向开始移动都是可能的。
(2)采用先到先服务算法。
【解答】
(1)由于最先到的的请求是1000,假设磁头向下运动,那么,电梯调度策略的块访问情况如下表所示。
块请求及被服务顺序
完成时间
1000
(1+3000/500)+8.3=15.3
500
15.3+(1+500/500)+8.3=25.6
5000
25.6+(1+4500/500)+8.3=43.9
6000
43.9+(1+1000/500)+8.3=55.2
(2)若采用先到先服务策略,则各块请求被服务并完成时间如下:
块请求及被服务顺序
完成时间
1000
(1+3000/500)+8.3=15.3
6000
15.3+(1+5000/500)+8.3=34.6
500
34.6+(1+5500/500)+8.3=54.9
5000
54.9+(1+4500/500)+8.3=73.2
对比这两种磁头调度策略,不难发现,采用电梯算法可节省约18s时间。
4.6某磁盘传输速率是传送每个4096字节块0.5毫秒。
若要实时播放一部MPEG影片要求每小时至少传1GB字节。
如果我们能以最好的方式在该磁盘上安排MPEG影片的块,能实时播放该影片吗?
如果不能,则需要多少个该型磁盘?
且应如何在这些磁盘上安排块,才能使影片在播放时有最小的延迟?
【解答】
如果我们按连续柱面方式安排存储块,这样可忽略寻道时间和旋转等待时间,那么,传送1GB字节至少需要时间为:
(230/4096)×0.5ms=131s,约2分钟。
远小于1小时,所以完全可到达实时播放要求。
4.7考虑基于目录槽变长记录页格式。
(1)管理目录槽的一种方法是使用最大目录槽号,并在页创建时分配目录数组。
给出赞成和反对该方法的理由。
(2)建议该方法的一种改进,使得允许我们能在不移动记录和不改变记录rids的情况下,按某个字段排序记录。
(3)估算顺序扫描该关系文件需要的总时间。
【解答】
(1)采用最大目录槽号方法比较简单,但不灵活。
因为这种方法很容易导致保留过多的槽或槽不够用情况,这是因为系统无法预测页中存储记录的长度。
(2)一种允许记录按指定的字段排序的改进方案是:
在页首存储象<页内逻辑记录号,记录偏移地址>结构形式为记录槽目录项数组。
4.8假设我们使用RAID4级方案,有4个数据盘和一个冗余盘。
假设块为单字节,如果数据盘中相应的块值如下,试给出冗余盘的块值。
(1)01010110,11000000,00111011和11111011。
(2)11110000,11111000,00111111和00000001。
【解答】
(1)01010110;
(2)00110110
4.9采用带有7个磁盘的RAID6级方案,描述从下列故障中恢复所要采取的步骤
(1)盘1#和盘7#。
(2)盘1#和盘4#。
【解答】
(1)先用2#、3#、5#号盘恢复盘1#的数据,再用1#、3#、4#号盘恢复盘7#的数据。
(2)先用2#、3#、5#号盘恢复盘1#的数据,再用1#、2#、6#号盘恢复盘4#的数据。
第五章数据库索引技术
5.1简要回答以下问题。
(1)如果要频繁进行:
①基于某字段值的范围搜索;②执行插入和扫描操作,不关心记录顺序;③基于特定的属性值搜索记录。
那么,我们应分别选择基本文件组织方式中的哪一种?
(2)说明索引项的三种基本形式。
(3)①说明顺序索引的基本概念,并指出稠密索引在哪些情况下,不需要数据文件是排序文件。
②说明稀疏索引的概念,稀疏索引肯定是聚集索引吗?
相应的数据文件肯定是排序文件吗?
请解释原因。
③二级或二级以上索引肯定是稀疏索引吗?
为什么?
(4)辨析以下概念对,说明它们之间的差异。
(a)聚簇文件与聚集索引;
(b)稠密索引与稀疏索引;
(c)主(码)索引与辅助索引。
【解答】
(1)以操作代价作为依据:
要频繁作基于字段值的范围搜索:
应该选用排序文件作为基本的文件组织方式。
要频繁执行插入和扫描操作,应该选用堆文件作为基本的文件组织方式。
要频繁作基于特定属性值的搜索记录,应该选用散列文件作为基本的文件组织方式。
(2)索引项的三种基本形式:
索引项k*就是数据记录本身,没有另外单独的索引文件。
(3)
①顺序索引是指按索引键值顺序来组织索引项的索引文件。
如果每个索引键值都至少对应有一个索引项,则称索引为稠密索引。
在稠密索引情况下,如果每个记录都对应有一个索引项,或在每个索引项中存储包含键值的记录指针链表,则可以不要求数据文件是排序的。
②只为搜索键的某些值建立索引项的索引称为稀疏索引,稀疏索引必须是聚集索引。
聚集索引是指一个索引文件中索引项的排序方式和数据文件记录的排序方式一致的索引方式,所以,与稀疏索引对应的数据文件一定是排序文件。
③二级或二级以上索引肯定是稀疏索引,因为如果还是像稠密索引那样一对一地建立二级索引的话,索引项或索引文件大小没有实质减少,没有什么意义。
作为索引一定是排好序的,故在低级索引基础上可建立更稀疏的上级索引。
(4)
Ø区别聚簇文件与聚集索引
-聚簇文件:
指数据文件,这种数据文件的每个页中,都只存放同一个关系表的记录。
-聚集索引:
指一种索引文件,这类索引文件中索引项的排序方式和数据文件记录的排序方式一致时。
虽然一个数据文件可以根据不同索引键建立不同索引文件,但至多只能有一个索引文件是聚集的。
Ø稠密索引与稀疏索引(参见前一小题说明)
Ø区别主(码)索引与辅助索引
-主索引或主码索引:
指搜索键恰好是主码的索引。
因为一个关系数据文件最多只有一个主码,所有每个关系最多也只有一个主码索引。
通常主码索引往往也是聚集索引。
主码索引中肯定没有重复索引项,因为主码肯定是候选码,没有重复键。
-辅助索引:
非主索引的索引文件。
辅助索引中通常会有重复索引项。
图5.21习题5.2附图
图5.22习题5.3附图
5.2考虑图5.21所示的阶数m=4的B+树索引。
(1)标示插入数据项9*之后的B+树,并指出完成该插入需要读多少个页和写多少个页。
(2)给出在原树中删除数据项8*之后的B+树,并指出完成该操作需要读多少个页和写多少个页。
(3)给出在原树中先插入数据项46*,然后再删除数据项52*之后的B+树。
(4)给出在原树中,依次删除32*、39*、41*、45*和73*之后的B+树。
【解答】
(1)由图看出插入9*不需要分裂,直接插入即可。
由于索引项即数据文件本身,从根结点到索引项读3个页。
只有叶结点改过,所以写1个页。
插入后的局部图如下:
(2)删除8*后要跟前一个索引项重组,从根结点到两个索引项要读4个页。
操作完成后两个叶结点和一个中间结点是脏页,故要写出3个页。
删除后的局部图:
(3)可直接插入数据项46*。
删除数据项52*则要合并重组,操作完成后的局部图:
(4)依次删除32*、39*、41*、45*、73*后的图:
5.3考虑图5.22所示B+树索引:
内节点可容纳4个键值和5个指针;叶节点中直接存储数据记录,可容纳4条记录且相邻叶节点之间用双链连接在一起。
回答以下问题。
(1)指出回答查询“取搜索键值大于38的所有记录”时,需要读取的有关节点。
(2)给出插入109*后的B+树。
(3)给出从原树中删除81*后的B+树。
(4)给出一个插入时会导致树高度增加的键值。
(5)图中没有详细给出子树A、B和C。
你能推测出这些子树的内容和形状吗?
【解答】
(1)查询大于38*的所有记录,要读取的节点有:
I1,I2,L2,L3,L4,L5,L6,L7,L8
(2)插入109*后,原L8节点需要分裂,完成操作后的局部图:
(3)删除81*后,L6,L7两个节点要重组,操作完成后的局部图如下:
(4)插入任何[65,79]之间的搜索键值,都会分裂L5节点,而I2也是满的,向上分裂到根结点,根结点也是满的,就会导致高度增加一层。
(5)关于子树A、B、C,我们可推出以下几件事:
1)它们都是树高为1的子树,因为它们的相邻子树,即以I2、I3为根节点的子树树高都是1;2)子树A包含的键值树肯定少于10个,子树B所包含的键值在范围[10,20)之间,子树C所包含的键值在范围[20,30)之间;3)每个中间节点至少会含有3个键值和3个指针。
5.4假定我们有一个排序文件,希望在该排序文件基础上构造一个稠密B+树聚集索引。
(1)最简单的方案是:
扫描文件,并利用B+树插入算法将记录逐个插入到树中。
指出该方案在性能和存储利用率方面存在的问题。
(2)说明如何用批量加载算法来改进以上方案。
【解答】
(1)利用标准的B+树插入算法,逐项插入,这种方法可能代价非常昂贵,因为每个项加入都需要从根开始到达合适的叶节点。
尽管在连续请求时索引层次的页,可能仍保持在缓冲池中,但这样的开销可能仍然非常可观,在树构建过程中会经历大量叶节点及相关内节点的分裂调整。
(3)而采用批量加载方法的效率则要高得多,在树的批量构建过程中可以有效避免叶节点分裂调整,只有少量内节点的顺次分裂调整,以及与树高相对应的有限几次根节点调整。
批量加载构建B+树的基本过程步可描述如下:
⏹第一步,从一个关系记录集创建要插入到索引的数据项。
该步包括扫描关系记录集,并生成和写出相应的数据项。
其代价为(R+E)次I/Os,这里,R是包含记录集的数据文件页数,E是包含数据项的总页数。
⏹第二步,排序数据项;外部排序含数据项的E个页,保守估计需要3E次I/Os(参见6.1部分)。
⏹第三步,从排序好的数据项中建立B+树索引。
因为第二步中已排序数据项的数据页,可在它们从排序步输出时,直接调用批量加载算法依次加入到新的B+树中,因此,第三步的代价只是写出所有(内节点)索引页的代价。
批量加载算法的总代价为:
R+4E+(B树索引节点数)
5.5考虑表5.2所示的student关系示例。
构造以下几种情况下的4阶B树,假定简单使用溢出页处理重复键值情况。
要求使用比k*约定更清晰的方式,在B+树中标示数据项。
(1)age字段上的稠密B+树索引,索引项为数据项。
(2)age字段上的稀疏B+树索引,索引项为数据项。
(3)gpa字段上的稠密B+树索引,索引项为键值加记录指针。
为便于问答这个问题,我们假定实际元组记录存储按图中给定顺序的排序文件中,每个页可存三个元组,前三个元组存储在第1个页的第1/2/3槽中,第4/5/6个元组存储在第2个页的第1/2/3槽中,…。
【解答】
图5.25习题5.5题解附图
(1)建立age上的稠密索引,见图5.25(a)
(2)建立age上的稀疏索引,见图5.25(b)
(3)建立gpa上的稠密B+树索引,见图5.25(c)
注意,数据项未必按数据记录同样的顺序存储,因为它们可能按不同的顺序被插入到B+树中。
我们假设采用简单的插入算法,首先以常规方法定位叶节点,如叶节点中已经有同样键值的数据项,就将新数据项安排到与该叶节点链接的溢出页。
这样,可保证每个叶节点中的数据项都有不同的键值。
这种做法会导致的一个问题是:
当叶节点满而需要分裂时,必须扫描溢出链以确保当一个键值被移动到一个新叶节点时,所有该键的重复项也能伴随移动到新叶节点的溢出页中。
另一种方案是分别维护每个键值的重复项溢出链,但考虑到每个页的容量限制,且一个给定键值的重复项数可能很少,故这个方案可能导致很差的空间利用率。
5.6关于可扩展散列,请回答以下问题。
(1)解释为什么需要全局位深度和局部位深度。
(2)在一个引发目录项翻倍的插入后,有多少个桶恰好只有一个目录项指向它?
如果从这些桶中删除一个项,那么目录项数是否会发生变化?
请给出简要解释。
(3)翻倍目录项时,我们需要检查所有局部位深度等于全局位深度的桶吗?
(4)对检索一个给定键值记录,可扩展散列能否保证只用1次
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 49 习题 解答
![提示](https://static.bingdoc.com/images/bang_tan.gif)