数据结构H PJ记录

,

PJ

lab1

V1 swiss_table

design philosophy:

  • 我干不过现有的库

跑起来被同学代码薄纱，且有抄袭原有库的可能。

自己不怎么看得懂代码，codex写出来的代码有很多冗余，优化空间比较小。

V2 朴素手写开放寻址

design philosophy:

  • 我要掌握自己的代码，我要手写
  • 开放寻址，优化空间主要在于哈希函数

problem：指令集用处不大（？）

V2_1

design philosophy:

  • 没有其他方法，尝试优化空间
  • 如果空间开到不是 2 的幂次方呢？

如果一组在 $[0,2^{64})$ 的哈希值被认为是均匀分布的，尝试 $(n*key)>>64$，这样也可以认为是均匀分布的。

problem：还是干不过他们啊。

V3

来源于赛后助教下发的PPT。

design philosophy:

  • 开放地址法+SIMD指令集进行查找
  • 节省内存，不使用控制字节，采用所有数据集没有的一个uint64来作为空槽标志（这个做法在 lab2 被 ban 了）
  • 冲突比较少，哈希函数的效率很重要。哈希函数使用内置的 _mm_crc32_u64。
  • 申请内存会进行内存对齐，使用 huge page
  • 对分支预测添加hints来减少分支预测错误导致的bubble。不过我觉得用处不大。

lab2

我们需要关注 PJ 条件的特殊性，这是我们能优于现有的库的关键：

  • 只需要实现动态插入，查询，区间查询，不需要实现删除和更新
  • 仅支持单线程
  • key 和 value 都是 uint64_t 类型，key 互不相同
  • bulk load 不算时间

调研了各种学习性索引，考虑到PJ要求是动态插入，区间查询，单线程，所以排除了一些：

ART：最稳妥的传统基线，随机数据和从 0 在线长起来都很稳、点查和插入都强，但区间查找通常不如叶链式结构直接，综合上是“最不容易翻车”的方案。

B+Tree：最经典、最均衡、最容易保证正确性的方案，区间查找天然友好、尾延迟稳定，但点查和插入常数通常不如优秀的内存型结构或 learned index 激进。

ALEX：对这个题目最对口的 learned index 之一，内部节点模型路由 + 叶子 gap array + 叶链扫描，使它在单线程 mixed workload 且带 range 的场景里很强，但分布不友好时稳定性和 range 局部性会变差。

HIRE：如果按“你的题目背景”来选，它是最贴题的新一代 mixed-workload learned index，因为它专门强化了 range、稳定性和尾延迟，但实现复杂度明显高于 ALEX，完整版还强依赖后台重训练机制。需要多线程。

DILI：适合做为 ALEX 之后最值得补的 learned index，支持动态插入并试图减少叶内最后一步搜索，对点查和插入很有潜力，但论文对 range 的系统性证据不如 ALEX/HIRE 充分。

LIPP：点查和插入都可能很猛，因为它追求精确位置、几乎不做叶内纠错，但它为了这个牺牲了数据局部性和叶链式连续扫描，所以对你这种带区间查找的题目通常不合适。不能区间查询。

PGM / DPGM：更适合读多或纯写更重的模式，尤其 DPGM 对持续插入很友好，但它们的缓冲/多层合并会让 range 和 mixed workload 的综合表现吃亏，不是你这个题的主选。慢。

MAB+tree：属于能做、也能支持 range 的中间路线，整体思路比 ALEX 更保守，但在你这个随机数据 + mixed workload 的设定下，通常没有 ALEX 那么值得优先投入。慢。

LiBox：如果硬件有 AVX-512，它在 mixed workload 下可能很强，但它对指令集条件比较挑，而且论文自己也承认 range 上没有特别稳定的明显优势，所以更像“高风险高收益的后手”。区间查询慢。

学习性索引：ALEX ，HYPER

传统索引：B+Tree

学习性索引

V1

design philosophy:

  • codex 很牛
  • Alex 很牛

带着 codex 读了一下论文，让他写点东西，效果略逊 B+Tree。

problem:

  • codex 没有那么牛
  • Alex 的库函数实现包括了很多细节，比如计算需要 expand 还是 split 的 cost 函数，fanout 取多少…

V1_2

design philosophy:

  • codex 不牛，我需要看懂思路，自己写一个出来
  • 阅读 alex 核心库

尝试阅读原库，过于工程，且总代码有 6k 多行，烧 token 巨快。放弃实现。

V2

design philosophy:

  • 尝试实现 HYPER?

或许性价比不高，已经不想卷了。

传统索引 - B+Tree

V3

design philosophy:

  • 参考 PJ1，需要自己掌握代码，我要看懂代码，最好能自己写出来
  • 分析库函数的 B+ 树效率欠佳的原因，考虑优化方向：
    • 完全不考虑 delete 操作，减少代码复杂度并优化内存
    • 牺牲一点空间，进行节点内存预分配
    • 针对内存排布优化（leaf/internal 分离优化内存，key/value 分离优化SIMD)
    • 分叉数
    • 对于查找时，可以分析线性查找/SIMD（AVX2/AVX512)/二分/SIMD结合别的效果
    • 64B 对齐，优化 cache miss
    • huge page 优化 TLP miss
    • memmove 处理插入移动
    • CSB+Tree 风格 child 连续分配（待求证），child group 连续分配等

V3_1

problem:

  • keys[] 没有真正 64B 对齐 -> 舍弃一点点内存
  • bulkload 叶子填满效率不高，可以考虑变成 70 到 90 填充
  • internal _max 可以和 leaf_max 不一样，例如 32/64， 64/96/128 的组合
  • 内存池管理写的非常丑陋-> 尝试去掉 mmap
  • parent 可以用 path
  • 指针可以用内存池下标优化

接下来先尝试加 AVX2 ，去掉 mmap-> 去掉 mmap 和 huge page之后，效率下降。

AVX2 效果比 AVX512 好的多。

V4

read_cnt=0, insert_cnt=0, update_cnt=0, scan_cnt=999257, lower_bound_cnt=99000743, delete_cnt=0

read_cnt=0, insert_cnt=0, update_cnt=0, scan_cnt=20000000, lower_bound_cnt=0, delete_cnt=0

read_cnt=23748912, insert_cnt=99999060, update_cnt=0, scan_cnt=1252028, lower_bound_cnt=0, delete_cnt=0

read_cnt=95004975, insert_cnt=99997714, update_cnt=0, scan_cnt=4997311, lower_bound_cnt=0, delete_cnt=0

read_cnt=379947315, insert_cnt=100000000, update_cnt=0, scan_cnt=19991264, lower_bound_cnt=0, delete_cnt=0

read_cnt=0, insert_cnt=98999063, update_cnt=0, scan_cnt=1000937, lower_bound_cnt=0, delete_cnt=0

design philosophy:

  • 单 b 树没有前途，尝试多数据结构结合？
  • 对于 workload1，没有插入，考虑优化静态建树（bulk_load)
  • 对于 workload3,4,5，考虑 hash, 并且是要在有 insert 的时候做。

V4_1

design philosophy:

先优化静态建树，考虑 CSB+Tree 风格，让 children 连续。

  1. 先修 find_leaf 单叶/空树边界：if (cur->is_leaf) return static_cast<LeafNode*>(cur);。这是正确性优化，不改布局。
  2. 不要在插入开始就关闭静态模式；至少推迟到第一次 split_leaf/split_internal。只要没有 split，物理连续性仍然成立。
  3. 更进一步可以做“静态上层 + 动态下层”的 hybrid：叶子 split 后只禁用最后一跳 CSB，根和高层仍用 children[0] + pos。这对混合 workload 比全局 is_static=false 更有价值，也不改节点布局。

此外，考虑 prefetch B+Tree 风格:

  1. 在 find_leaf 和 scan 中预取 internal_node 和 next_leaf。

  2. scan 里可以预取 next_leaf->keys, next_leaf->values，而不只是 next_leaf 指针本身；scan_num=100 时这类小优化能吃到。

method:

  1. bulk_load 时候将每一层连续排布，children 连续排布，吃到 CSB+Tree 风格的收益。加了 children_base 字段，并且提前 prefetch。在节点静态时候取代 children[pos] 直接转跳，减小 cache miss.
  2. find_leaf 中 prefetch_internal 提前预取 children_base, keys, values
  3. scan 中 prefetch values, keys, next_leaf

observation:

  1. prefetch 只有在之后一段时间之后要用到的操作才有效果，不然可能是负优化
  2. prefetch_internal 把所有 cache 的 key 都取进来效果并不好
  3. scan 的 next_leaf 的 cache miss 是主要瓶颈，考虑到 leaf_max=128 但是 scan_num 最大只有 100，提前预取 1 个即可

V4_2

祝老师指出，可以尝试拟合数据集，并给AI充足的上下文来高效 vibe coding。

observation:

尝试发掘数据集构造的方式，并由此来做一些优化：

  1. 动态 workload 中 init_table_ratio=0.5，但这 50% 是从全量 key 打乱后取样，所以近似是全量分布的随机样本。
  2. 后续 insert 来自剩余 50% key，key 不重复。
  3. bulk_load 中，w1/2 的 num 大约 200M 左右，w3456 大约 100M 左右

design philosophy:

  1. 用 AI 尝试数据结构的加成
    1. 静态采用线性数组，做 delta b+tree
    2. 上层学习性索引，下层 b+tree
  2. 根据 bulkload 来判断是 workload:
    1. 如果是 bulkload 前面，则把 bulk_load_leaf = leaf_max，起码可以降空间和降树高
    2. 否则调整因子大小

method:

  1. 线性数组的 lower_bound 还没有我的 b+tree 快。可能 cache miss 过多，跨度过大。
  2. 太累了。放弃调教 AI.
  3. 调整 leaf_max 和 internal_max 收益不如波动，所以选择空间比较小的配置
  4. 如果 bulkload 是动态，即使根据“后续插入的大小是 bulkload 的大小，且分布近似随机” 这一特性，负载因子调整到 0.4~0.6 除了空间变大没有任何优点。

final:

  1. 根据 bulk_load_num 来区分 workload，相应调整分配空间和负载因子
  2. leaf_max=128, internal_max=64
  3. 负载因子依旧 0.85~0.9，换取空间

reference:

  • Effect of Node Size on the Performance of Cache-Conscious B+-trees
  • Improving Index Performance through Prefetching

感想：

  • 上下文还是很重要，虽然真很浪费 token。
  • AI 在具体实现上可能不如人工精细（比如 prefetch / 指令集会乱用），但是如果提出新的结构，将是很厉害。
  • 要成为最会使用 AI 的人。