Skip to main content

bucket

下面专门把论文 第 5 节 PRE-PROCESSING FOR SEGRAM 里的 bucket（桶） 拿出来讲清楚。
它是 SeGraM 哈希索引的第一级结构，作用是：用很小的内存，把大量 minimizer 按哈希值分组，从而快速定位到某个 minimizer 的 seed 位置。

一、为什么需要 bucket？​

SeGraM 的索引要存很多 minimizer → seed 位置的映射。
如果直接建一张大哈希表，每个可能的哈希值都占一个条目，会出现两个问题：

  1. 表太大、太稀疏：哈希值空间可能很大，但实际出现的 minimizer 数量有限，直接开大数组会浪费内存。
  2. 指针开销大：如果每个 minimizer 都单独存一个地址，第一级表会非常庞大。

所以论文借鉴 Minimap2 的做法，用 bucket（桶） 做第一级索引：
把哈希值映射到数量有限的桶里，每个桶只记录“属于我的 minimizer 在第二级表中的起始位置和数量”。
这样第一级表可以很小，而真正的 minimizer 记录集中放在第二级。

类比：
图书馆有几十万本书，如果给每个可能的书名都做一个抽屉，抽屉会多到放不下。
于是先用少量“分类抽屉”（桶），每个抽屉里放一张纸条：“本抽屉对应的书在第二排书架第 3 层开始，共 12 本”。
你要找书时，先确定去哪个抽屉，再按纸条去第二排找。

二、bucket 在三级索引中的位置​

论文第 5 节说，哈希索引是三级结构：

第一级：Buckets（桶）
第二级：Minimizers（每个 minimizer 一条记录）
第三级：Seed Locations（每个 seed 位置一条记录）

第一级：Bucket 条目里存什么？​

论文原文：

Each entry in this first level corresponds to a single bucket, and contains the starting address of the bucket's minimizers in the second-level table, along with the number of minimizers in the second-level table that belong to the bucket.

翻译：
第一级每个条目对应一个桶，包含：

  1. 该桶的 minimizer 在第二级表中的起始地址；
  2. 该桶包含的 minimizer 数量。

注意：桶本身不存 minimizer 内容，只存“指针 + 数量”。
真正的 minimizer 记录在第二级。

第二级：Minimizer 记录​

Each second-level entry stores the hash value of the corresponding minimizer, the starting address of the minimizer's seed locations in the third-level table, and number of locations that belong to the minimizer. The minimizers are sorted based on their hash values.

翻译：
第二级每个 minimizer 一条记录，包含：

  • minimizer 的哈希值；
  • 它的 seed 位置在第三级表中的起始地址；
  • 它有多少个 seed 位置；
  • 所有 minimizer 按哈希值排序。

第三级：Seed Location 记录​

In the third level, each entry corresponds to one seed location. An entry contains the node ID of the corresponding seed location, and the relative offset of the corresponding seed location within the node.

翻译：
第三级每个条目是一个 seed 位置，包含：

  • 节点 ID；
  • 该 seed 在节点内的相对偏移。

三、查询时 bucket 怎么工作？​

假设 MinSeed 要查一个 minimizer 的出现频率和 seed 位置，流程是：

  1. 计算 minimizer 的哈希值；
  2. 用哈希值确定桶索引：比如取哈希值的某些位，映射到 2242^{24} 个桶中的一个；
  3. 读第一级桶条目：得到该桶的 minimizer 在第二级表中的起始地址和数量；
  4. 在第二级中查找匹配的哈希值：因为同一桶的 minimizer 按哈希值排序，可以顺序或二分查找；
  5. 找到匹配的 minimizer 后：读它的 seed 位置起始地址和数量；
  6. 去第三级取 seed 位置：得到节点 ID 和偏移。

这样，第一级桶表很小，第二级和第三级存实际数据。
桶的作用就是快速缩小范围，避免在全部 minimizer 中从头找。

四、桶数量怎么选？为什么是 2242^{24}？​

论文说：

We empirically choose the first-level bucket count. Figure 7 shows the impact that the number of buckets has on both the total memory footprint of the hash-table-based index and the maximum number of minimizers in each bucket.

翻译：
桶的数量是实验选出来的。图 7 显示桶数量对两件事的影响：

  • 索引总内存占用；
  • 每个桶中最大 minimizer 数量。

权衡关系​

桶数量第一级内存每桶 minimizer 数哈希冲突查询速度
少小多多慢（桶内要查很多）
多大少少快（桶内查得少）

论文原文：

We observe from the figure that while a lower bucket count decreases the memory footprint of the index, it increases the number of minimizers assigned to each bucket (i.e., the number of hash collisions increases), increasing the number of memory lookups required. We empirically find that a bucket count of 2242^{24} strikes a reasonable balance.

翻译：
桶越少，索引内存越小，但每个桶分到的 minimizer 越多，哈希冲突增加，查询时需要更多内存查找。
实验发现 2242^{24} 个桶比较平衡。

具体大小​

Each bucket entry requires 4 B of data, resulting in a size of 224∗42^{24}*4 B for the first level.

翻译：
每个桶条目 4 字节。
第一级总大小 = 224×42^{24} \times 4 字节 = 67,108,864 字节 ≈ 64 MB。

相对于总索引 9.8 GB，第一级桶表只占约 0.65%，非常小。

五、bucket 与其他两级的大小对比​

论文原文：

Each minimizer requires 12 B of data, resulting in a size of #distinct minimizers ∗12\ast 12 B for the second level. Each location requires 8 B of data, resulting in a size of #total number of locations ∗8\ast 8 B for the third level. Across all 24 chromosomes of the human genome, the total storage required for the hash-table-based index is 9.8 GB.

翻译：

  • 第一级桶：224×42^{24} \times 4 B ≈ 64 MB；
  • 第二级 minimizer：每个 12 B；
  • 第三级 seed 位置：每个 8 B；
  • 人类 24 条染色体索引总共约 9.8 GB。

所以桶只是“目录的目录”，占内存很小，但能大幅加速查询。

六、bucket 设计的核心思想总结​

  1. 作用：把大量 minimizer 按哈希值分组，第一级只存“起始地址 + 数量”，避免第一级表过大。
  2. 结构：
    • 第一级：桶表，每个桶 4 B，存第二级起始地址和数量；
    • 第二级：minimizer 记录，按哈希值排序；
    • 第三级：seed 位置记录。
  3. 查询流程：哈希 → 桶 → 第二级找匹配哈希 → 第三级取位置。
  4. 桶数选择：2242^{24} 是内存和查询速度的平衡点；桶少省内存但冲突多，桶多查询快但内存大。
  5. 总大小：第一级桶表约 64 MB，整个索引约 9.8 GB。

一句话：
bucket 是 SeGraM 哈希索引的第一级“粗目录”，用 4 字节的条目把 minimizer 分到 2242^{24} 个桶里，既节省内存又加快查询；桶数选 2242^{24} 是为了在内存占用和哈希冲突之间取得平衡。