锐客网

  1. 首页 > 睿知 > it技术 > >

DBMS动态散列原理

DBMSDBMS动态散列

本文概述

  • 如何搜寻钥匙
  • 如何插入新记录
  • 例如
  • 将具有哈希地址10001的密钥9插入上述结构
  • 动态哈希的优点
  • 动态哈希的缺点
  • 动态散列方法用于克服静态散列（例如存储桶溢出）的问题。
  • 在这种方法中, 数据桶随着记录的增加或减少而增长或收缩。此方法也称为可扩展哈希方法。
  • 该方法使散列动态化, 即, 它允许插入或删除而不会导致性能下降。
如何搜寻钥匙
  • 首先, 计算密钥的哈希地址。
  • 检查目录中使用了多少位, 这些位称为i。
  • 取哈希地址的最低有效i位。这给出了目录的索引。
  • 现在使用索引, 进入目录并找到记录可能所在的存储桶地址。
如何插入新记录
  • 首先, 你必须遵循相同的过程进行检索, 最终要花一些时间。
  • 如果该存储桶中仍有空间, 则将记录放入其中。
  • 如果存储桶已满, 那么我们将拆分存储桶并重新分配记录。
例如 根据其哈希地址的前缀, 考虑将以下密钥分组到存储桶中：
DBMS动态散列原理

文章图片
【DBMS动态散列原理】2和4的最后两位是00。因此它将进入存储区B0。 5和6的最后两位是01, 因此它将进入存储区B1。 1和3的最后两位是10, 因此它将进入存储区B2。 7的最后两位是11, 因此它将进入B3。
DBMS动态散列原理

文章图片
将具有哈希地址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数据模型架构和实例

    下一篇：DBMS ER模型概念