基于哈希的索引：线性哈希与可扩展哈希的深入解析

### 基于哈希的索引：线性哈希与可扩展哈希的深入解析 #### 1. 哈希索引中的碰撞与溢出页 在哈希索引中，碰撞是一个常见的问题。当多个数据条目具有相同的哈希值时，就会发生碰撞。如果同一哈希值的数据条目数量超过了一个页面所能容纳的数量，就需要使用溢出页来处理这些额外的数据。溢出页的引入是为了确保所有数据都能被妥善存储，但它也会对性能产生一定的影响。 #### 2. 线性哈希概述 线性哈希是一种动态哈希技术，与可扩展哈希类似，它能够很好地适应数据的插入和删除操作。与可扩展哈希不同的是，线性哈希不需要目录，能够自然地处理碰撞，并且在桶分裂的时机上具有很大的灵活性。不过，如果数据分布非常不均匀，溢出链可能会导致线性哈希的性能比可扩展哈希更差。 ##### 2.1 哈希函数族 线性哈希使用一系列哈希函数 \(h_0, h_1, h_2, \cdots\)，每个函数的范围是其前一个函数的两倍。具体来说，如果 \(h_i\) 将一个数据条目映射到 \(M\) 个桶中的一个，那么 \(h_{i + 1}\) 将一个数据条目映射到 \(2M\) 个桶中的一个。通常，我们通过选择一个哈希函数 \(h\) 和初始桶的数量 \(N\) 来定义这些哈希函数，即 \(h_i(value) = h(value) \mod (2^iN)\)。 例如，如果我们将初始桶的数量 \(N\) 设置为 32，那么 \(d_0\) 为 5，\(h_0\) 就是 \(h \mod 32\)，其范围是 0 到 31。\(d_1 = d_0 + 1 = 6\)，\(h_1\) 就是 \(h \mod (2 * 32)\)，范围是 0 到 63，以此类推。 ##### 2.2 桶分裂的轮次 线性哈希的桶分裂过程可以看作是一轮一轮进行的。在第 \(Level\) 轮中，只使用哈希函数 \(h_{Level}\) 和 \(h_{Level + 1}\)。在这一轮开始时，文件中的桶会从第一个到最后一个依次进行分裂，从而使桶的数量翻倍。在每一轮的任何时刻，文件中都存在已经分裂的桶、尚未分裂的桶以及本轮分裂产生的新桶。 下面是线性哈希在一轮分裂过程中桶的状态示意图： ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(开始轮次):::process --> B(已分裂的桶):::process A --> C(未分裂的桶):::process A --> D(本轮分裂产生的新桶):::process B --> E(使用 \(h_{Level + 1}\) 确定数据位置):::process C --> F(使用 \(h_{Level}\) 确定数据位置):::process ``` ##### 2.3 数据搜索过程 当我们搜索具有给定搜索键值的数据条目时，首先应用哈希函数 \(h_{Level}\)。如果该函数将我们引导到一个未分裂的桶，我们就在这个桶中进行搜索。如果它引导我们到一个已经分裂的桶，数据条目可能仍然在这个桶中，也可能已经被移动到了本轮分裂产生的新桶中。为了确定数据条目所在的桶，我们需要应用 \(h_{Level + 1}\)。 #### 3. 线性哈希的详细操作 ##### 3.1 插入操作 在插入数据时，如果插入操作触发了桶的分裂，插入数据的桶不一定是要分裂的桶。与静态哈希类似，会添加一个溢出页来存储新插入的数据条目。桶的分裂是按照轮询的方式进行的，这意味着最终所有的桶都会被分裂，从而在溢出链变得过长之前重新分配数据条目。 我们使用一个计数器 \(Level\) 来表示当前的轮次，初始值为 0。要分裂的桶用 \(Next\) 表示，初始值为桶 0（第一个桶）。在第 \(Level\) 轮开始时，文件中的桶数量为 \(N_{Level} = N * 2^{Level}\)。 下面是一个简单的线性哈希文件示例，每个桶可以容纳四个数据条目，文件最初包含四个桶： | 桶编号 | 数据条目 | | ---- | ---- | | 0 | 44*, 36*, 32*, 25* | | 1 | 9*, 5*, 14*, 18* | | 2 | 10*, 30*, 31*, 35* | | 3 | 11*, 7* | 当插入数据条目 43* 时，触发了桶的分裂。插入完成后，文件的状态如下： | 桶编号 | 数据条目 | | ---- | ---- | | 0 | 32*, 9*, 5*, 25* | | 1 | 14*, 18*, 10*, 30* | | 2 | 31*, 35*, 7*, 11* | | 3 | 44*, 36*, 43* | ##### 3.2 分裂条件 我们可以根据不同的条件来触发桶的分裂。例如，每当添加一个新的溢出页时进行分裂，或者根据空间利用率等条件来设置额外的分裂条件。在我们的示例中，当插入一个新的数据条目导致创建溢出页时，就会触发分裂。 当分裂触发时，\(Next\) 桶会被分裂，哈希函数 \(h_{Level + 1}\) 会重新分配该桶及其分裂镜像之间的条目。分裂镜像的桶编号为 \(b + N_{Level}\)，其中 \(b\) 是被分裂的桶的编号。分裂完成后，\(Next\) 的值会增加 1。 ##### 3.3 搜索操作 在搜索数据时，如果使用 \(h_{Level}\) 得到的桶编号 \(b\) 在 \(Next\) 到 \(N_{Level}\) 的范围内，那么数据条目就属于桶 \(b\)。例如，\(h_0(18) = 2\)，由于当前 \(Next = 1\) 且 \(N_1 = 4\)，这个桶尚未分裂。 如果得到的桶编号 \(b\) 在 0 到 \(Next\) 的范围内，数据条目可能在这个桶中，也可能在其分裂镜像中。我们需要使用 \(h_{Level + 1}\) 来确定数据条目所属的桶。例如，\(h_0(32)\) 和 \(h_0(44)\) 都为 0，但由于 \(Next = 1\) 表示该桶已经分裂，