首页 - 通讯 - DBMS 中的文件组织 | 2套

DBMS 中的文件组织 | 2套

2023-10-01 06:56

先决条件——哈希数据结构
在数据库管理系统中，当我们想要检索特定数据时，搜索所有索引值并到达所需数据就变得非常低效。在这种情况下，哈希技术应运而生。
哈希是一种无需使用索引结构即可直接搜索所需数据在磁盘上的位置的有效技术。数据存储在数据块中，数据块的地址由哈希函数生成。存储这些记录的内存位置称为数据块或桶。

哈希文件组织：

存储桶 – 存储桶是存储记录的内存位置。这些存储桶也被视为 存储单元。
哈希函数 – 哈希函数是一种映射函数，可将所有搜索键集映射到实际记录地址。通常，哈希函数使用主键（数据块的地址）生成哈希索引。哈希函数可以是简单的数学函数或任何复杂的数学函数。
哈希索引——前缀作为哈希索引。每个哈希索引都有一个深度值，指示使用多少位来计算哈希函数。这些位可以寻址 2n 个桶。所有这些位什么时候被消耗掉？然后深度值线性增加并且分配两倍的桶。
下图清楚地描述了哈希函数的工作原理：

哈希又分为两个子类别：

静态哈希 –

在静态哈希中，当提供搜索键值时，哈希函数始终计算相同的地址。例如，如果我们要使用 mod(5) 哈希函数生成 STUDENT_ID = 76 的地址，则始终会得到相同的桶地址 4。这里的桶地址不会改变。因此，用于此静态哈希的内存桶数量始终保持不变。

操作——

插入 - 当一条新记录插入表中时，哈希函数 h 根据其哈希键 K 为新记录生成存储桶地址。
存储桶地址 = h(K)
搜索 – 当需要搜索记录时，使用相同的哈希函数来检索记录的桶地址。例如，如果我们要检索 ID 76 的整个记录，并且该 ID 的哈希函数为 mod(5)，则结果存储桶地址将为 4。然后我们将直接转到地址 4 并检索整个记录ID 104。该ID充当散列密钥。
删除 –如果我们要删除一条记录，我们首先会使用哈希函数来获取要删除的记录。然后我们就删除内存中该地址的记录。
Update with -需要先使用哈希函数更新数据记录，然后再更新数据记录。

现在，如果我们想在文件中插入一些新记录，但是哈希函数生成的桶地址不为空或者该地址中已经存在数据。这成为需要处理的危急情况。静态哈希中的这种情况称为桶溢出。
在这种情况下我们将如何插入数据？
提供了多种方法来克服这种情况。下面讨论一些常用的方法：

开放哈希 –
在开放哈希方法中，下一个可用数据块用于输入新记录，而不是覆盖旧记录。这种方法也称为线性探测。
比如D3是一条需要插入的新记录，哈希函数生成的地址是105。但是已经满了。因此，系统搜索下一个可用桶123并将D3分配给它。
闭合哈希 –
在闭合哈希方法中，一个新的桶被分配相同的地址并链接在完整的桶之后。这种方法也称为溢出链接。
例如，我们要在表中插入一条新记录D3。静态哈希函数生成的桶地址是105。但是这个桶已满，无法存储新数据。在这种情况下，将在 105 个存储桶的末尾添加一个新存储桶并与其链接。然后将新记录D3插入新桶中。
- 二次探测：
  二次探测与开放散列或线性探测非常相似。在这里，新旧桶之间的唯一区别是线性的。使用二次函数来确定新的存储桶地址。
- 双重哈希：
  双重哈希是与线性探测类似的另一种方法。这里的差异与线性探测中一样是固定的，但是这个固定差异是通过使用另一个哈希函数来计算的。这就是该名称经过双重哈希处理的原因。