1、设有一个职工文件，并设该文件由教材中表10-1所示的5个记录组成，其中职工号为关键码。

如下结构是什么类型的索引？

A、多分树静态索引

B、倒排索引

C、动态索引

D、线性索引

2、红黑树是一种扩充的二叉搜索树（BST）。给定一颗结点个数为n的红黑树在最坏的情况下，红黑树的删除结点操作的时间复杂度是O(log n)

3、设有一棵阶m=3的B树，如图10-9所示：

其中a, b, …, g是结点的名称，系统一块可以动态分配的结点叫h。可在说明插入过程时使用，结点内的整数为关键码。若在图中所示的B树中插入关键码55，请计算完成该插入所需要的访外次数（包括读磁盘和写磁盘）。

解析：

读磁盘：a - c - g

写磁盘：g - g' - c

​​

​答案： 6

4、假设按如下的方法修改从B树中删除元素的方式：如果一个结点既有最相邻的左兄弟也有最相邻的右兄弟，那么在合并前对两个兄弟都要作检查。从一棵高度为4的B树中删除元素时需要的最大磁盘访问次数？

注：一般而言, B树的层次都很少，查找B树路径中的结点是否能放在内存中，不必重复访问磁盘读取。

答案： 14

5、假定一个计算机系统有4 096字节的磁盘块，每个磁盘的磁盘号可以用一个四字节的整数表示。要存储的每一条记录中4个字节是关键码，64个字节是数据字段。记录已经排序，顺序地存储在磁盘文件中。我们建立一个稠密索引，该线性索引的结构为：（每个文件磁盘块的最小关键码，该块磁盘的磁盘号），通过线性索引访问磁盘文件中的记录。

如果线性索引也存储在磁盘中（这样它的大小仅受二级索引的限制），而且使用4 096个字节的二级索引，二级索引中的每个单元引用线性索引的磁盘块中最小的关键码值。文件中最多可以存储 15M 条记录。

解析

4096/68=60.24 每块磁盘上可以存60条记录。

二级索引中每一条占8字节，所以共4096/8=512条，即线性索引占了512个磁盘。

（4字节磁盘号 + 4字节关键码）

线性索引的每个磁盘上有4096/8=512条索引，所以共512*512=256K条线性索引。

每条线性索引对应一块磁盘，所以共256K*60=15M条记录。​

6、在什么情况下多分树静态索引比B+树的实现更有效率？

A、在系统数据库不稳定，并且系统没有时间进行文件再组织的情况下

B、在插入和删除操作比较少的情况下

C、在系统允许较频繁的文件再组织的情况下

D、在系统数据较稳定，并且需要支持高效的并行查找的情况下

E、在插入删除操作较多的情况下

解析：

多分树静态索引适合较稳定的数据

多分树静态索引适合允许文件再组织的数据

B+树更适合修改较多的数据

7、假定有一个B+树，它的内部结点可以存储多达100个子女，叶结点可以存储多达15条记录（本题中的B+树把所有记录存放在叶结点上）。对2层的B+树，能够存储的最小记录数和最大记录数是多少？

答案： 16,1507​

8、假定有一个B+树，它的内部结点可以存储多达100个子女，叶结点可以存储多达15条记录（本题中的B+树把所有记录存放在叶结点上）。对4层的B+树，能够存储的最小记录数和最大记录数是多少？

答案： 40000,15000000

9、假定一个计算机系统有4 096字节的磁盘块，每个磁盘的磁盘号可以用一个四字节的整数表示。要存储的每一条记录中4个字节是关键码，64个字节是数据字段。记录已经排序，顺序地存储在磁盘文件中。我们建立一个稠密索引，该线性索引的结构为：（每个文件磁盘块的最小关键码，该块磁盘的磁盘号），通过线性索引访问磁盘文件中的记录。

如果线性索引的大小是2MB。最多可以在磁盘文件中存储 15M 条记录？

解析：

4096/68=60.24 每块磁盘上可以存60条记录。

每个索引8字节，所以一共2MB/8B=0.25M条索引。

每条索引对应一块磁盘，即60条记录，所以总共最多60*0.25M=15M条记录。

​