搜索
《数据库系统实现》复习资料2.2.2..................................................................................................................................................12.7.3..................................................................................................................................................13.1.7..................................................................................................................................................23.2.6..................................................................................................................................................33.3.5..................................................................................................................................................33.3.7..................................................................................................................................................43.5.2..................................................................................................................................................43.6.2..................................................................................................................................................56.1.2..................................................................................................................................................66.2.3..................................................................................................................................................76.2.4..................................................................................................................................................86.3.2..................................................................................................................................................86.4.2..................................................................................................................................................97.2.5..................................................................................................................................................97.4.2................................................................................................................................................107.7.1................................................................................................................................................112.2.2习题2.2.2假设Megatron747磁道的磁头位于磁道4096，即跨越磁道的1/16距离处。假设下一个请求是对一随机磁道上一个块。计算读这个块的平均时间。答案2平均移动的磁道：（1+2+…+4096）+（1+2+…+(65536-4096)）/65536=28928;存道时间：1+28928/4000=8.232ms;传输时间=0.13ms；旋转等待时间=4.17ms；所以总的平均时间为8.232+0.13+4.17=12.532ms；2.7.3假设在习题2.7.1的病人记录上添加另外的可重复字段，表示胆固醇化验，每一次胆固醇化验需要一个24字节的日期和化验的整数结果。如果a）重复化验保存在记录中。b）化验存储在另外一个块中，记录中存储指向化验的指针。分别给出病人记录的格式。1其他首部信息指向住址指向病史记录长度指向化验（化验记录）出生日期社会保险号码病人ID姓名住址病史2记录首部信息姓名的长度住址的长度病史的长度指向姓名指向住址指向病史指向化验出生日期社会保险号码病人ID（化验记录）姓名住址病史3.1.7如果我们使用一个扩充的倒排索引，如图3-10所示，那我们就能执行许多其他类型的查询。说明如何使用这种索引去找到：a)“cat”和“dog”彼此相距不超过5个位置并且出现在同一类元素（如标题、正文或锚）中的文档。b)“cat”后刚好隔一个位置就跟有“dog”的文档。c)题目中同时出现“dog”和“cat”的文档。A.获得所有的桶条目“猫”和“狗”。通过类型分类这些条目,在类型中通过位置进行分类。扫描记录,保持一个“窗口”,记录当前的类型。在当前类型上延长到五个位置之前。拿所有的新记录和当前窗口中的记录作比较。如果我们找到一个条目:(1)有相反的词,比如“狗”，如果当前记录为“猫”,和(2)有相同的文档条目。那么这个文档就是我们想要检索的。B.获得所有的桶条目“狗”。通过位置分类这些条目。扫描记录,保持一个“窗口”,记录一个位置之前的当前位置。拿新记录和当前窗口中的记录作比较。如果我们找到一个:记录(1)有相反的词“猫”,和(2)有相同的文档条目。那么这个文档是我们想要检索的。C.我们沿着指针与“猫”来找到这个词的出现。选择从与猫有关的桶文件指针开始找，“猫”的类型是“标题”。然后同样我们找出桶条目“狗”的指针。如果这两套指针相交,这个文档就是满足我们条件的。答案23.1.7A找到所有包含“cat”和“dog”的文档的指针集，然后按类型分类，然后按位置分类。选择其中相距不超过5个位置且键值相反的记录，即满足条件。B找到所有包含“dog”的文档指针列表，然后再按位置分类，找出所有指示位置信息的指针列表，记录所有指针往前移动两个位置的位置信息。然后求得所有包含“cat”的文档的位置指针列表，与刚才的位置信息的交集即满足条件。C从桶文件中选择有“cat”出现且类型为“标题”的文档指针。接着，找到“dog”的桶中项目，并从中选择类型为“标题”的文档指针。求两个指针集相交，就得到满足条件的文档。3.2.6在例3.17中我们提出，如果我们使用更复杂的维护内部结点键的算法，那么可以从右（或左）边的非兄弟结点中借键。描述一个合适的算法，它可以通过从同层相邻结点中借键来重新达到平衡，而不管这些相邻结点是否是键-指针对太多或太少的结点的兄弟结点。1、如果node的节点数大于等于min+1，删除key,到52、如果node相邻左节点的节点数大于等于min+1，从node左节点借值key，将node的root值改为key，到53、如果node相邻右节点的节点数大于等于min+1，从node右节点借值key，将node的root值改为key，到54、删除key，与其左节点合并，node=root到15、结束3.3.5假定键散列为4位序列，就像这一部分中可扩展散列表和线性散列表的例子一样。但是，假定块中可存放三个记录而非两个记录。如果开始时散列表中有两个空存储块（对应于0和1），请给出插入键值如下的记录后的结构：a)1111，1110，……0000，且散列方法是可扩展散列b）1111，1110，……0000，且散列方法是线性散列，其充满度阈值为75%。c)0000，0001，……1111，且散列方法是可扩展散列。d)0000，0001，……1111，且散列方法是线性散列，其充满度阈值为100%。(a)i=3(c)、与(a)的结构相同，当然顺序可以升序也可以降序(d)、与(b)的相同，顺序也可以反过来。3.3.7实际中有些散列函数并不像理论上那样好。假定我们在整数键值i上定义一个散列函数h(i)=i2modB，其中B表示桶数。a)如果B=10，该散列函数会出现什么问题？b)如果B=16，该散列函数又有什么好处？c)该散列函数对哪些B值有用？答案1（1）B=10时散列函数值=0,1,4,5,6,9，其中桶2,3,7,8的空间就被浪费掉了，没有键值存进去，然后桶1,4,6,9这四个桶要记录双倍的键值（2）B=16时散列函数值=0,1,4,9所有的键值均匀分布在这四个桶中，方便集中管理（3）B=2幂或其开方仍为整数3.5.2选择一个分段散列函数，且速度、内存和硬盘大小三属性各为一位二进制数，使它能很好地划分图3-36中的数据。3.6.2把图3-36的数据放到一棵kd-树中。假定每块能存放两个记录，给每一层挑选一个使数据划分尽可能均匀的划分值。分裂属性的顺序选择：a)速度，然后内存，再交替;b)速度，然后内存，最后硬盘，再交替;c)不论什么属性，只要它在每个结点产生最均匀的分裂。第三问不会，需要讨论6.1.2对习题6.1.1中的每个事务，在计算中加入读写动作，并给出各步骤对主存和磁盘产生的影响。假设最初A=50且B=25.此外，请说明当OUTPUT动作顺序恰当时，是否可能即使在事务的执行过程中发生了故障，一致性仍能得到保持。6.1.1事务：a)B:=A+B;A:=A+B;b)A:=B+1;B:=A+1;c)A:=A+B;B:=A+B;a)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(B,t1)25255025READ(A,t2)