DBMS - 哈希

对于庞大的数据库结构，遍历所有索引值并到达目标数据块以检索所需数据几乎是不可能的。哈希是一种有效的技术，可以计算磁盘上数据记录的直接位置，而无需使用索引结构。

哈希使用哈希函数，并将搜索键作为参数来生成数据记录的地址。

哈希组织

• 桶 - 哈希文件以桶格式存储数据。桶被认为是存储单元。一个桶通常存储一个完整磁盘块，而一个磁盘块又可以存储一个或多个记录。

• 哈希函数 - 哈希函数 h 是一个映射函数，它将所有搜索键集 K 映射到放置实际记录的地址。它是一个从搜索键到桶地址的函数。

静态哈希

在静态哈希中，当提供搜索键值时，哈希函数始终计算相同的地址。例如，如果使用 mod-4 哈希函数，则它只会生成 5 个值。对于该函数，输出地址始终相同。提供的桶数始终保持不变。

操作

• 插入 - 当需要使用静态哈希输入记录时，哈希函数 h 计算搜索键 K 的桶地址，记录将存储在该地址中。

  桶地址 = h(K)

• 搜索 - 当需要检索记录时，可以使用相同的哈希函数来检索存储数据的桶的地址。

• 删除 - 这只是一个搜索然后是删除操作。

桶溢出

桶溢出的情况称为冲突。这对任何静态哈希函数来说都是致命的状态。在这种情况下，可以使用溢出链。

• 溢出链 - 当桶已满时，为相同的哈希结果分配一个新桶，并将其链接到前一个桶之后。这种机制称为闭合哈希。

• 线性探测 - 当哈希函数生成一个已经存储数据的地址时，将为其分配下一个空闲桶。这种机制称为开放哈希。

动态哈希

静态哈希的问题在于，它不会随着数据库大小的增长或缩小而动态扩展或收缩。动态哈希提供了一种机制，可以通过该机制动态地按需添加和删除数据桶。动态哈希也称为扩展哈希。

在动态哈希中，哈希函数被设计为生成大量值，并且最初只使用其中一部分。

组织

整个哈希值的开头作为哈希索引。只有一部分哈希值用于计算桶地址。每个哈希索引都有一个深度值，表示用于计算哈希函数的位数。这些位可以寻址 2n 个桶。当所有这些位都被使用时 - 即所有桶都满了 - 则深度值线性增加，并分配两倍的桶。

操作

• 查询 - 查看哈希索引的深度值，并使用这些位计算桶地址。

• 更新 - 如上执行查询并更新数据。

• 删除 - 执行查询以找到所需数据并删除。

• 插入 - 计算桶的地址

  • 如果桶已满。
    • 添加更多桶。
    • 向哈希值添加其他位。
    • 重新计算哈希函数。
  • 否则
    • 将数据添加到桶中，
  • 如果所有桶都满了，则执行静态哈希的补救措施。

当数据以某种顺序组织并且查询需要一定范围的数据时，哈希是不利的。当数据是离散且随机时，哈希的性能最佳。

哈希算法的复杂度高于索引。所有哈希操作都在恒定时间内完成。