DBMS动态散列原理

2022-04-20 DBMS DBMS动态散列

本文概述

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

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

如何搜寻钥匙

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

如何插入新记录

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

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

文章图片
【DBMS动态散列原理】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。

文章图片
动态哈希的优点

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

动态哈希的缺点

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

推荐阅读

上一篇：DBMS数据模型架构和实例

下一篇：DBMS ER模型概念