本文整理了《数据库系统概论（第6版）》第九章“关系数据库存储管理”的课后习题答案，便于学习者参考学习。

习题1

题目：试分析每个数据库对象对应一个操作系统文件与整个数据库对应一个或若干个文件，这两种存储关系数据库的策略各有什么优缺点？
答案：

• 每个数据库对象对应一个操作系统文件：本质是将存储管理交由操作系统完成，优势是方便DBMS实现，缺点是不能利用数据库的特点来优化存储管理。
• 整个数据库对应一个或若干个文件：本质是由DBMS自己负责存储管理，优势是能利用数据库特点优化存储管理，缺点是DBMS实现难度更高。

习题2

题目：假设Course表以定长记录方式存储。请描述Course表的记录存储在以下情况中一条记录占多少字节。
①字段可以在任何字节处开始。
②字段必须在4的倍数的字节处开始。
③字段必须在8的倍数的字节处开始。
答案：
① 字段可以在任何字节处开始：一条记录占52字节。
② 字段必须在4的倍数的字节处开始：一条记录占60字节。
③ 字段必须在8的倍数的字节处开始：一条记录占64字节。

习题3

题目：试述关系表有哪些组织方式，并分析各自的优缺点。
答案：
关系表常见组织方式及优缺点如下：

1. 堆存储：
   • 优点：插入操作高效，只需找到合适空闲空间即可插入记录。
   • 缺点：搜索、更新、删除操作代价高，需扫描全表找到满足条件的记录。
2. 顺序存储：
   • 优点：能高效处理按排序属性（组）的查询请求。
   • 缺点：维护代价高，插入、更新、删除记录时可能需迁移已有记录以保持顺序。
3. 多表聚簇存储：
   • 优点：减少连接操作的开销。
   • 缺点：一是降低单表查询效率，同一表记录分散在更多块中；二是增加更新操作代价，插入新记录时可能需频繁迁移记录腾出空间。
4. B+树存储：
   • 优点：能在保持较高记录访问效率的同时降低数据维护开销。
   • 缺点：按不等于某个值的条件搜索时效率很低。
5. 哈希存储：
   • 优点：按哈希属性进行等值条件查询时，可通过计算哈希值快速定位记录，提升查询效率。
   • 缺点：不适合数据分布严重倾斜的情况，无法快速完成非等值查询（如范围查询、大于/小于某值的查询）。

习题4

题目：试述数据库索引机制的优点。
答案：
数据库索引机制的主要优点：

1. 一个表的索引块数量通常远少于数据块数量，搜索速度更快。
2. 索引采用易于检索的数据结构，可通过高效方法快速查找。
3. 对于经常访问的表，若索引文件足够小，可长期驻留在内存缓冲区，减少I/O操作。

习题5

题目：试述稠密索引和稀疏索引的优缺点。
答案：

1. 稠密索引：
   • 优点：仅扫描索引即可准确定位记录。
   • 缺点：表记录数较多时索引体积大，查找耗时；对基本表增删改时，维护代价较高。
2. 稀疏索引：
   • 优点：索引尺寸小，维护成本低；增删改基本表时，仅当修改的是存储块第一条记录的索引属性时才需维护索引。
   • 缺点：查询效率低于稠密索引，无法精确定位记录，需在数据块中顺序查找。

习题6

题目：分别描述利用稠密索引、稀疏索引、多级索引、B+树索引、哈希索引，是如何对Student表进行如下查询的。
①查询学号为20180013的记录。
②查询学号为20180014的记录。
③查询学号为20180016的记录。
④查询学号大于或等于20180009的记录。
答案：

① 查询学号为20180013的记录

• 稠密索引：依次读入索引块，利用顺序/二分查找法在索引块中找到Sno为20180013的索引项（第3个索引块），根据指针读取存储块，取出对应记录。
• 稀疏索引：依次读入索引块，查找属性值≤20180013的最大索引项（第2个索引块的20180013），根据指针读取存储块，在块中顺序搜索取出对应记录。
• 多级索引：在二级索引中按稀疏索引方法定位一级索引块位置，找到Sno≤20180013的最大索引项（第一个索引块的20180013），读取一级索引块并找到对应索引项，根据指针读取存储块，在块中顺序查找取出对应记录。
• B+树索引：根结点判断20180013>20180008，沿右子树搜索；中间结点判断20180013>20180012，沿其右侧指针向下；叶结点找到20180013后，通过左侧指针取出对应记录。
• 哈希索引：哈希函数计算桶号为1号，在1号桶找到对应索引项，根据指针读取存储块取出记录。

② 查询学号为20180014的记录

• 稠密索引：依次读入索引块，利用顺序/二分查找法在第3个索引块找到Sno为20180014的索引项，根据指针读取存储块取出对应记录。
• 稀疏索引：依次读入索引块，查找属性值≤20180014的最大索引项（第2个索引块的20180013），根据指针读取存储块，在块中顺序搜索取出对应记录。
• 多级索引：在二级索引中按稀疏索引方法定位一级索引块位置，找到Sno≤20180014的最大索引项（第一个索引块的20180013），读取一级索引块并找到对应索引项，根据指针读取存储块，在块中顺序查找取出对应记录。
• B+树索引：根结点判断20180014>20180008，沿右子树搜索；中间结点判断20180014>20180012，沿其右侧指针向下；叶结点找到20180014后，通过左侧指针取出对应记录。
• 哈希索引：哈希函数计算桶号为2号，在2号桶找到对应索引项，根据指针读取存储块取出记录。

③ 查询学号为20180016的记录

• 稠密索引：依次读入索引块，因稠密索引有序且最后一个索引块最大索引项为20180015<20180016，判断无该记录。
• 稀疏索引：依次读入索引块，查找属性值≤20180016的最大索引项（第2个索引块的20180015），根据指针读取存储块，块中最后一条记录为20180015<20180016，判断无该记录。
• 多级索引：读取二级索引块，找到Sno≤20180016的最大索引项（20180013），读取一级索引块，因一级索引稠密且最大索引项为20180015，判断无该记录。
• B+树索引：根结点判断20180016>20180008，沿右子树搜索；中间结点判断20180016>20180012，沿其右侧指针向下；叶结点未找到20180016，判断无该记录。
• 哈希索引：哈希函数计算桶号为1号，1号桶未找到对应索引项，判断无该记录。

④ 查询学号大于或等于20180009的记录

• 稠密索引：依次读入索引块，找到Sno为20180009的索引项，根据指针读取存储块取出对应记录；因文件顺序存放，依次读取后续所有存储块并取出记录。
• 稀疏索引：依次读入索引块，找到≤20180009的最大索引项（20180009），根据指针读取存储块取出对应记录；因文件顺序存放，依次读取后续所有存储块并取出记录。
• 多级索引：读入二级索引块，找到≤20180009的最大索引项（20180007），读取一级索引块找到Sno≥20180009的索引项，根据指针读取存储块取出第一条满足条件的记录；因表顺序存放，遍历当前块及后续所有存储块取出记录。
• B+树索引：从根结点逐层向下搜索，叶结点找到20180009的索引项，其后叶结点索引项均≥20180009；根据指针读取存储块取出记录，遍历当前叶结点后沿指针遍历后续叶结点直至最后。
• 哈希索引：哈希索引无法保证记录顺序，无法用于范围查询；需依次读取每个存储块，遍历记录取出所有Sno≥20180009的记录。

习题7

题目：描述当依次用下列方式更新Student表中的记录时，稠密索引、稀疏索引、多级索引、辅助索引、B+树索引、哈希索引分别是如何进行维护的。
①插入记录(20180016,张婧,女,2002-1-2,信息安全)。
②删除学号为20180004的记录。
③删除学号为20180005的记录。
④将学号为20180008的记录修改为计算机科学与技术专业。
答案：

① 插入记录(20180016,张婧,女,2002-1-2,信息安全)

• 稠密索引：读入索引块找到Sno≤20180016的最大索引项（20180015），存储块有空闲空间，将记录插入存储块第一个空位，在索引块增加对应索引项。
• 稀疏索引：找到Sno≤20180016的最大索引项（20180015），存储块有空闲空间，直接插入记录；因新记录非存储块开头，无需更新索引。
• 多级索引：找到Sno≤20180016的最大索引项（20180015），存储块有空闲空间，插入记录；在一级索引块增加对应索引项，因新记录非存储块开头，无需更新二级索引。
• B+树索引：插入记录后，找到索引项插入位置；叶结点索引项数达最大充满度，分裂叶结点（一个存20180012/20180013/20180014，新叶结点存20180015/20180016），新叶结点指针指向新记录；中间结点插入20180015并指向新叶结点。
• 哈希索引：插入记录后，哈希函数计算桶号为1号（16%3=1），1号桶有空闲空间，插入索引项，指针指向新记录位置。

② 删除学号为20180004的记录

• 稠密索引：找到对应记录并删除，删除索引块中对应索引项，将该索引块中20180004后的索引项向起始方向迁移。
• 稀疏索引：找到对应记录并删除；因该记录非存储块第一条数据，无需更新索引。
• 多级索引：找到对应记录并删除；删除一级索引中对应索引项，将同块后续索引项向起始方向迁移；因删除的非一级索引块第一条索引项，无需更新二级索引。
• B+树索引：找到叶结点中20180004索引项并删除；删除后叶结点索引项数小于最小充满度，左兄弟结点有3个索引项，将20180005索引项并入左叶结点；删除父结点中20180004及其右指针，父结点剩余一个属性值，与右兄弟结点重新分配属性值并修改根结点属性值。
• 哈希索引：哈希函数计算桶号为1号，找到对应索引项并删除，同时删除存储块中对应记录。

③ 删除学号为20180005的记录

• 稠密索引：找到对应记录并删除（空闲空间管理不同，后续数据可迁移或维持现状）；删除索引块中对应索引项，将该索引块中20180005后的索引项向起始方向迁移。
• 稀疏索引：找到对应记录并删除；因该记录是存储块第一条数据，将后续数据向块起始方向迁移，更新稀疏索引项（20180005改为20180006）。
• 多级索引：找到对应记录并删除；删除一级索引中对应索引项，将同块后续索引项向起始方向迁移；因删除的非一级索引块第一条索引项，无需更新二级索引。
• B+树索引：找到叶结点中20180005索引项并删除；删除后叶结点仍有3个索引项（大于最小充满度），直接删除索引项及对应指针。
• 哈希索引：哈希函数计算桶号为2号，找到对应索引项并删除，同时删除存储块中对应记录。

④ 将学号为20180008的记录修改为计算机科学与技术专业

找到20180008的记录，取出后修改专业为计算机科学与技术；因索引建立在学号上，无需更新任何索引。