DBMS 中的散列：静态和动态散列技术
菲奥娜·布朗
DBMS 中的散列是什么？
在数据库管理系统（DBMS）中，哈希是一种无需索引结构即可直接在磁盘上查找所需数据位置的技术。哈希方法用于索引和检索数据库中的数据项，因为使用较短的哈希键值查找特定数据项比使用原始值查找速度更快。数据以数据块的形式存储，其地址由应用哈希函数生成；存储这些记录的内存位置称为数据块。 数据块或数据桶.
为什么我们需要哈希？
在数据库管理系统中，以下情况需要应用哈希方法：
- 对于庞大的数据库结构，要搜索所有层级的所有索引值，然后找到目标数据块以获取所需数据，是非常困难的。
- 哈希用于对数据库中的项目进行索引和检索，因为使用较短的哈希键搜索特定项目比使用原始值搜索要快得多。
- 哈希是一种无需使用索引结构即可计算磁盘上数据记录直接位置的理想方法。
- 这也是实现字典的一个有用技术。
哈希中的重要术语
以下是哈希算法中使用的一些重要术语：
- 数据桶： 数据桶是存储记录的内存位置，也称为存储单元。
- 重点： a DBMS 密钥 是用于识别关系（表）中的行（元组）的属性或属性集。
- 哈希函数： 一张地图ping 将所有搜索键映射到实际记录所在地址的函数。
- 线性探测： 探测间隔固定。在这种方法中，使用下一个可用的数据块来写入新记录，而不是覆盖旧记录。
- 二次探测： 通过将二次多项式的连续输出添加到原始计算给出的起始值，来帮助确定新的存储桶地址。
- 哈希索引： 数据块的地址。哈希函数可以是简单的数学函数，也可以是复杂的数学函数。
- Double 哈希： 哈希表中用于解决冲突的一种方法，即应用第二个哈希函数。
- 桶溢出： 桶溢出的情况称为碰撞。对于任何静态哈希函数来说，这都是致命的。
哈希技术的类型
数据库管理系统中主要有两种哈希技术：
- 静态哈希
- 动态散列
两者的主要区别在于桶的数量是否固定，接下来的两节将对此进行解释。
静态哈希
在静态哈希中，生成的数据桶地址始终保持不变。
因此，如果您生成一个地址，例如， 学生 ID = 10 使用哈希函数 修改(3)，最终的存储桶地址将始终是 1因此，您不会看到存储桶地址有任何变化。
因此，在静态哈希方法中，内存中的数据桶数量始终保持不变。
静态哈希函数
- 插入记录： 当需要向表中插入新记录时，您需要使用其哈希键为其生成一个地址。地址生成后，记录就会存储在该地址处。
- 搜索： 当您需要检索记录时，使用相同的哈希函数来检索存储数据的桶的地址。
- 删除记录： 使用哈希函数，首先获取要删除的记录，然后从内存中的该地址删除该记录。
静态哈希进一步细分为：
- 打开哈希
- 封闭哈希
开放哈希
在开放式哈希方法中，新记录不是覆盖旧记录，而是使用下一个可用的数据块。这种方法也称为线性探测。
例如，A2 是您想要插入的新记录。哈希函数生成的地址是 222，但该地址已被其他值占用。因此，系统会查找下一个数据桶 501，并将 A2 分配给它。
封闭哈希
在封闭式哈希方法中，当桶已满时，会为同一个哈希分配一个新的桶，并将结果链接到前一个结果之后。
动态散列
动态哈希提供了一种机制，可以根据需要动态地添加和删除数据桶。在这种哈希方法中，哈希函数可以帮助您创建大量值，并且结构会随着数据量的增长或缩小而增长或缩小。这使得它非常适合那些大小无法预先预测的表，因为静态哈希要么会浪费空间，要么会导致溢出。
有序索引和哈希的区别
以下是索引和哈希的主要区别：
| 参数 | 有序索引 | 哈希 |
|---|---|---|
| 地址存储 | 内存中的地址是根据称为主键的键值进行排序的。 | 地址总是使用键值上的哈希函数生成。 |
| 性能 | 随着数据量的增加，它可能会减少，因为数据是按顺序存储的，每次插入、删除或更新都会重新排序。 | 数据不断增删时性能最佳。但对于大型数据库而言，哈希文件的维护成本会越来越高。 |
| 用于 | 适用于范围检索，即检索特定范围的数据。 | 非常适合根据搜索键检索特定记录，但只有当哈希函数作用于搜索键时才能发挥良好性能。 |
| 内存管理 | 删除和更新操作会产生许多未使用的数据块，这些数据块无法释放以供重新使用，因此需要定期维护。 | 在静态和动态哈希中，内存始终得到管理，并且通过处理桶溢出来扩展静态哈希。 |
简而言之，选择排序方式。 索引 用于范围查询和哈希，用于键的精确匹配查找。
什么是碰撞？
哈希冲突是指数据集中两个或多个项的哈希值错误地映射到同一位置的一种状态。 哈希表.
如何处理哈希冲突
有两种方法可以避免哈希冲突：
- 重提旧事： 该方法会调用辅助哈希函数，并持续应用该函数，直到找到可以放置记录的空槽为止。
- 链接： 链式方法构建一个链表，链表中的键哈希值相同。此方法需要在每个表位置添加一个额外的链接字段。
