database - 具有相似键的可扩展散列

Question

一次插入可扩展哈希是否可能导致多个目录加倍？我能找到的所有在线资源都只展示了只需要一个双精度的情况。

考虑使用键的 MSB 的示例：

| 0 | -> 00111

| 1 | -> 11110

插入(11111)

结果会是什么？我需要将目录翻倍吗？

Answer 1

这取决于您的最大页面大小。如果您的页面只能包含多个键，那么您只需将键从 1 开始添加到条目的末尾，如下所示：

| 0 | -> 00111 | 1 | -> 11110, 11111

否则，您将不得不多次扩展 MSB 目录，在这种情况下您会得到。

如果您需要相反的情况，我相信您可以使用 LSB 来实现该解决方案。