chapter24 实践习题2

在本章的实践习题2中，我们探讨了高级索引技术的相关问题，涉及数据库管理和存储效率优化。以下是各题目答案及其背后的知识点解析： 24.1 题目解答：B树与LSM树（Log-Structured Merge Trees）在插入操作上的主要区别在于随机I/O与顺序I/O的使用。B树在插入时需要更多的随机I/O操作，而LSM树则倾向于执行更多的顺序I/O。在大数据集且数据存储在磁盘上的情景下，由于随机I/O的成本远高于顺序I/O，因此LSM树通常更受青睐。 24.2 题目解答：增大数组的大小可以减少添加操作的数量，但当数组大小超过缓存大小时，访问数组元素的开销会增加。因此，数组的大小应调整到与L1缓存大小匹配。对于L1缓存大小在几兆字节的情况，使用16到24字节索引的数组较为合适。 24.3 题目解答：填充因子（Fill Factor）是指在创建索引时，每个索引页中实际数据所占的空间比例。合适的填充因子能有效利用空间，同时避免过早的页面分裂。通常，填充因子设置在75%至90%之间比较合理，以平衡空间利用率和性能。 24.4 题目解答：该题讨论的是基于距离优先的搜索策略，即根据查询点与包围盒的距离来优先搜索子节点。当找到距离为0或更近的答案，以及所有距离不小于d的未探索节点时，搜索结束。这种策略常用于空间索引，如R树或kd树。 24.5 题目解答：在每一层，需要检查所有相交的边界框，并进一步探索它们的子对，除非它们是叶子节点，此时可以直接生成答案。这是空间索引遍历的基本策略。 24.6 题目解答：练习24.6给出了可扩展哈希结构的示意图，展示了如何通过动态调整哈希表大小来处理插入、删除和查找操作。 24.7 题目解答： a. 删除11：从24.1题目的答案来看，将第三个桶更新为：3193。此时，可以考虑合并第二和第三个桶。如果仅保留四个桶的地址表就足够的话，可以进行合并，但在此处我们不执行合并操作。 b. 删除31：将最后一个桶更新为：2237。 c. 插入1：将第一个桶更新为：2171。 d. 插入15：将最后一个桶更新为：215237。 24.8 题目解答：此题涉及哈希表的大小和哈希值的位数。假设哈希值在哈希表中使用的位数为n，而表的大小为2^b。若想避免哈希冲突，哈希表的大小应该至少为2^(n+b)，这样每个可能的哈希值都有一个唯一的槽位。哈希表的设计与负载因子（Load Factor）密切相关，负载因子是已存储元素数量与表容量的比值，合理的负载因子可以平衡查找效率和内存使用。 这些习题涵盖了数据库索引的各种技术和策略，包括B树、LSM树、空间索引、缓存管理、哈希表和动态扩展等。理解并熟练运用这些概念对于优化数据库性能和设计高效的数据存储解决方案至关重要。