DBMS - 哈希

上一个

测验

下一个

对于一个庞大的数据库结构，通过所有层级搜索所有索引值然后到达目标数据块来检索所需数据几乎是不可能的。哈希是一种有效的技术，可以在不使用索引结构的情况下直接计算磁盘上数据记录的位置。

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

哈希组织

Bucket − 哈希文件以 bucket 格式存储数据。Bucket 被视为一个存储单元。一个 bucket 通常存储一个完整的磁盘块，该块可以存储一条或多条记录。
Hash Function − 哈希函数 h 是一种映射函数，将所有搜索键集 K 映射到实际记录放置的地址。它是从搜索键到 bucket 地址的函数。

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

Insertion − 当需要使用静态哈希插入记录时，哈希函数 h 为搜索键 K 计算 bucket 地址，该记录将存储在那里。

Bucket address = h(K)
Search − 当需要检索记录时，可以使用相同的哈希函数来检索存储数据的 bucket 地址。
Delete − 这只是搜索后进行删除操作。

Bucket 溢出的状况被称为 collision。这是任何静态哈希函数的致命状态。在这种情况下，可以使用溢出链式处理。

Overflow Chaining − 当 bucket 满时，为相同的哈希结果分配一个新的 bucket，并将其链接到前一个 bucket 之后。这种机制称为 Closed Hashing。

Linear Probing − 当哈希函数生成的地址处已经存储数据时，为其分配下一个空闲 bucket。这种机制称为 Open Hashing。

静态哈希的问题在于，随着数据库大小的增长或缩小，它不会动态扩展或收缩。动态哈希提供了一种机制，可以按需动态添加和移除数据 bucket。动态哈希也被称为 extended hashing。

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

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

Querying − 查看哈希索引的深度值，并使用这些位来计算 bucket 地址。
Update − 如上执行查询并更新数据。
Deletion − 执行查询以定位所需数据并删除。
Insertion − 计算 bucket 的地址
- 如果 bucket 已满。
  - 添加更多 bucket。
  - 向哈希值添加额外位。
  - 重新计算哈希函数。
- 否则
  - 将数据添加到 bucket 中，
- 如果所有 bucket 都满，则执行静态哈希的补救措施。

当数据按某种顺序组织且查询需要数据范围时，哈希并不有利。当数据是离散且随机的时，哈希表现最佳。

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