DBMS动态哈希

动态哈希方法用于克服桶溢出等静态哈希问题。
在此方法中，随着记录的增加或减少，数据桶会增大或减小。 此方法也称为可扩展哈希方法。
该方法使哈希动态化，即，它允许插入或删除而不会导致性能不佳。

如何搜索一个键

• 首先，计算键的哈希地址。
• 检查目录中使用了多少位，这些位称为i。
• 取哈希地址的最不重要的i位。 这给出了目录的索引。
• 现在使用索引，转到目录并查找记录可能位于的存储区地址。

如何插入新记录

• 首先，必须按照相同的步骤进行检索，最后才会进入某个存储桶。
• 如果存储桶中仍有空间，则将记录放入其中。
• 如果存储桶已满，则将拆分存储桶并重新分配记录。

示例：
考虑将以下将键分组到桶中，具体取决于其哈希地址的前缀：

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

将带有哈希地址10001的键9插入上述结构中：

• 由于键9具有散列地址10001，因此它必须进入第一个桶。 但是桶B1已满，所以它要分裂。
• 分裂将从5分离5,9，因为最后三位5,9是001，所以它将进入桶B1，最后三位6是101，因此它将进入桶B5。
• 键2和键4仍在B0中。 B0中的记录由000和100条目指向，因为条目的最后两位都是00。
• 键1和键3仍在B2中。 B2中的记录由010和110条目指示，因为两个条目的最后两位都是10。
• 键7仍在B3中。 B3中的记录由111和011条目指向，因为两个条目的最后两位都是11。

动态哈希的优点

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

动态哈希的缺点

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