哈希文件组织和哈希索引组织有什么区别？

Question

来自数据库系统概念

\n\n

\n

散列可以用于两个不同的目的。

\n\n

\n

• 在哈希文件组织中，我们通过计算记录的搜索键值的函数直接获得包含所需记录的磁盘块的地址。

\n

• 在哈希索引组织中，我们将搜索键及其关联的指针组织到哈希文件结构中。

\n

\n

\n\n

“哈希文件结构”是什么意思？

\n\n

我对此不太确定，所以我不确定散列 \xef\xac\x81le 组织和散列索引组织之间有什么区别。\n您能分别显示或改写它们是什么吗？

\n

Answer 1

想象一下，您有两条记录，一条带有键“foo”，另一条带有键“bar”。假设记录的长度固定为 64 字节，“foo”哈希为 0x4000，“bar”哈希为 0x0100。

在“哈希文件组织”中，您有一个函数可以获取搜索键并直接计算地址。因此，如果将“foo”和“bar”添加到文件中，“foo”的记录将从文件中的地址0x4000开始，而“bar”记录将从文件中的地址0x0100开始。

该文件看起来像这样：

Address Range         Contents
-------------         --------
0x0000 - 0x00FF       empty space
0x0100 - 0x013F       "bar" record
0x0140 - 0x3FFF       empty space
0x0400 - 0x403F       "foo" record

在“哈希索引组织”中，您有一个辅助数据结构（索引），它告诉您特定记录的开始位置。假设该文件为空并添加“foo”。您的哈希函数计算出的值为 0x4000。您将其添加到索引（哈希映射或类似的内容）中，并且由于文件为空，因此分配的值为 0。当您添加第二条记录“bar”时，会添加哈希键 0x0100，并分配的值是 0x0040。你有一个索引：

Key     Value
-------------
0x0100  0x0040
0x4000  0x0000

该文件如下所示：

Address Range        Contents
-----------------------------
0x0000 - 0x003F      "foo" record
0x0040 - 0x007F      "bar" record

当然，您必须将索引存储在某个地方。它可以位于单独的文件中，或者可能位于数据文件的前面或后面，或者分散在整个文件中。有很多不同的可能性。

在第一种情况下，文件中浪费了很多空间，但您可以直接查找记录的位置：对键进行哈希处理，结果就是记录的地址。

在第二种情况下，您对键进行哈希处理，然后在索引中查找结果以获得记录的键。这里的主要优点是它可能节省文件中的大量空间，但是您会遇到在哪里存储索引的麻烦。

无论哪种情况，您都必须有某种方法来解决哈希冲突。