《数据库系统实现》复习资料
2.2.2 2
2.7.3 2
3.1.7 3
3.2.6 5
3.3.5 5
3.3.7 7
3.5.2 8
3.6.2 9
6.1.2 10
6.2.3 11
6.2.4 13
6.3.2 14
6.4.2 15
7.2.5 16
7.4.2 18
7.7.1 18
2.2.2
习题2.2.2假设Megatron 747磁道的磁头位于磁道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
其他首部信息 指向住址 指向病史
记录长度 指向化验
（化验记录）
2
记录首部信息 姓名的长度 住址的长度 病史的长度
指向姓名 指向住址 指向病史 指向化验
（化验记录）
3.1.7
如果我们使用一个扩充的倒排索引，如图3-10所示，那我们就能执行许多其他类型的查询。说明如何使用这种索引去找到：
a)“cat”和“dog”彼此相距不超过5个位置并且出现在同一类元素（如标题、正文或锚）中的文档。
b)“cat”后刚好隔一个位置就跟有“dog”的文档。
c)题目中同时出现“dog”和“cat”的文档。
A.获得所有的桶条目“猫”和“狗”。通过类型分类这些条目,在类型中通过位置进行分类。扫描记录,保持一个“窗口”,记录当前的类型。在当前类型上延长到五个位置之前。拿所有的新记录和当前窗口中的记录作比较。如果我们找到一个条目:(1)有相反的词,比如“狗”，如果当前记录为“猫”,和(2)有相同的文档条目。那么这个文档就是我们想要检索的。
B.获得所有的桶条目“狗”。通过位置分类这些条目。扫描记录,保持一个“窗口”,记录一个位
置之前的当前位置。拿新记录和当前窗口中的记录作比较。如果我们找到一个:记录(1)有相反的词“猫”,和(2)有相同的文档条目。那么这个文档是我们想要检索的。
C.我们沿着指针与“猫”毛发干枯来找到这个词的出现。选择从与猫有关的桶文件指针开始找，“猫”的类型是“标题”。然后同样我们找出桶条目“狗”的指针。如果这两套指针相交,这个文档就是满足我们条件的。
答案2
3.1.7
A>找到所有包含“cat”和“dog”的文档的指针集，然后按类型分类，然后按位置分类。选择其中相距不超过5个位置且键值相反的记录，即满足条件。
B>找到所有包含“dog”的文档指针列表，然后再按位置分类，找出所有指示位置信息的指针列表，记录所有指针往前移动两个位置的位置信息。然后求得所有包含“cat”的文档的位置指针列表，与刚才的位置信息的交集即满足条件。
C>从桶文件中选择有“cat”出现且类型为“标题”的文档指针。接着，找到“dog”的桶中项目，并从中选择类型为“标题”的文档指针。求两个指针集相交，就得到满足条件的文档。
3.2.6
在例3.17中我们提出，如果我们使用更复杂的维护内部结点键的算法，那么可以从右（或左）边的非兄弟结点中借键。描述一个合适的算法，它可以通过从同层相邻结点中借键来重新达到平衡，而不管这些相邻结点是否是键-指针对太多或太少的结点的兄弟结点。
1、如果node的节点数大于等于min+1，删除key,到5
2、如果node相邻左节点的节点数大于等于min+1，从node左节点借值key，将node的root值改为key，到5
3、如果node相邻右节点的节点数大于等于min+1，从node右节点借值key，将node的root值改为key，到5
4、删除key，与其左节点合并，node=root到1
5、结束
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)=i2mod B，其中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 | 磁盘中的B |
READ(B,t1) | 25 | | 25 | 50 | 25 |
READ(A,t2) | 50 | 50 | 25 | 50 | 25 |
t1:=t2+t1 | 75 | 50 | 25 | 50 | 25 |
WRITE(B,t1) | 75 | 50 | 75 | 50 | 坦克绘画25 |
t2:=t2+t1 | 125 | 50 | 75 | 50 | 25 |
WRITE(A,t2) | 125 | 125 | 75 | 50 | 25 |
Output（B,t1) | 75 | 125 | 75 | 50 | 75 |
Output(A,t2) | 125 | 125 | 75 | 125 | 75 |
| | | | | |
b)
动作 | t | 内存中的A | 内存中的B | 磁盘中的A | 磁盘中的B |
READ(A,t1) | 50 | 50 | | 50 | 25 |
READ(B,t2) | 25 | 50 | 25 | 50 | 25 |
t1:=t2+1 | 26 | 50 | 25 | 50 | 25 |
WRITE(A,t1) | 26 | 26 | 25 | 50 | 25 |
t2:=t1+1 | 27 | 26 | 25 | 50 | 25 |
WRITE(B,t2) | 27 | 26 | 27 | 50 | 25 |
Output（A,t1) | 26 | 26 | 27 | 26 | 25 |
Output(B,t2) | 27 | 26 | 27 | 26 | 27 |
| | | | | |
c)
动作 | t | 内存中的A | 内存中的B | 磁盘中的A | 磁盘中的B |
READ(A,t1) | 50 | 50 | | 50 | 25 |
READ(B,t2) | 25 | 50 | 25 | 50 | 25 |
t1:=t1+t2 | 75 | 50 | 25 | 50 | 25 |
WRITE(A,t1) | 75 | 75 | 25 | 50 | 25 |
t2:=t1+t2 | 100 | 75 | 25 李家同 | 50 | 25 |
WRITE(B,t2) | 100 | 75 | 100 | 50 | 25 |
Output（A,t1) | 75 | 75 | 100 | 75 | 25 |
Output(B,t2) | 100 | 75 | 100 | 75 | 100 |
| | | | 患难与共 | |
如果OUTPUT动作顺序恰当，即使在事务执行过程中发生故障，一致性仍能得到保持。
6.2.3
下面是两个事务T和U的一系列日志记录：<START U>;<U,A,10>;<START T>;<T,B,20>;<U,C,30>;<T,D,40>;<COMMIT T>;<U,E,50>;<COMMIT U>。请描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：
a)<START T> b)<COMMIT T> c)<U,E,50> d)<COMMIT U>
