DBMS动态散列原理

本文概述

• 如何搜寻钥匙
• 如何插入新记录
• 例如
• 将具有哈希地址10001的密钥9插入上述结构
• 动态哈希的优点
• 动态哈希的缺点

• 动态散列方法用于克服静态散列（例如存储桶溢出）的问题。
• 在这种方法中, 数据桶随着记录的增加或减少而增长或收缩。此方法也称为可扩展哈希方法。
• 该方法使散列动态化, 即, 它允许插入或删除而不会导致性能下降。

如何搜寻钥匙

• 首先, 计算密钥的哈希地址。
• 检查目录中使用了多少位, 这些位称为i。
• 取哈希地址的最低有效i位。这给出了目录的索引。
• 现在使用索引, 进入目录并找到记录可能所在的存储桶地址。

如何插入新记录

• 首先, 你必须遵循相同的过程进行检索, 最终要花一些时间。
• 如果该存储桶中仍有空间, 则将记录放入其中。
• 如果存储桶已满, 那么我们将拆分存储桶并重新分配记录。

例如

根据其哈希地址的前缀, 考虑将以下密钥分组到存储桶中：

2和4的最后两位是00。因此它将进入存储区B0。 5和6的最后两位是01, 因此它将进入存储区B1。 1和3的最后两位是10, 因此它将进入存储区B2。 7的最后两位是11, 因此它将进入B3。

将具有哈希地址10001的密钥9插入上述结构

• 由于键9的哈希地址为10001, 因此它必须进入第一个存储桶。但是存储桶B1已满, 因此它将被拆分。
• 由于5、9的最后三位为001, 因此拆分会将5、9与6分开, 因此它将进入存储区B1, 6的最后三位为101, 因此它将进入存储区B5。
• 键2和4仍在B0中。 B0中的记录由000和100条目指向, 因为两个条目的最后两位均为00。
• 键1和3仍在B2中。 B2中的记录由010和110指向, 因为两个条目的最后两位均为10。
• 键7仍在B3中。 B3中的记录由111和011条目指向, 因为两个条目的最后两位均为11。

动态哈希的优点

• 在这种方法中, 性能不会随着系统中数据的增长而降低。它只是增加了存储空间以容纳数据。
• 在这种方法中, 随着数据的增长和缩小, 内存得到了很好的利用。不会有任何未使用的内存在说谎。
• 此方法适用于数据频繁增长和收缩的动态数据库。

动态哈希的缺点

• 在这种方法中, 如果数据大小增加, 则存储桶大小也会增加。这些数据地址将保留在存储区地址表中。这是因为数据存储区会随着存储桶的增长和收缩而不断变化。如果数据大量增加, 则维护存储区地址表将变得很繁琐。
• 在这种情况下, 也会发生铲斗溢出的情况。但是, 与静态哈希相比, 达到这种情况可能需要很少的时间。