100行代码的压缩前缀树: 50% smaller - OpenACID Blog

[giscus[bot]]

100行代码的压缩前缀树: 50% smaller - OpenACID Blog

压缩前缀树, 减少50%存储空间, 支持创建和查询, 只需100行代码

https://blog.openacid.com/algo/succinctset/

[StLeoX]

虽然没读太懂，但是大致的思想是用 Bitmap 维护路由信息。
在 DuckDB ART 的 Node256 也是类似的，可以参考。
ART 对于水平压缩还有一个优化，就是设定了 4 种扇出，从而优化了 Trie 内点扇出固定的浪费。

[drmingdrmer]

可了下 ART, 它是基于指针的, 支持修改的trie, 又在其上做了一系列优化, 是个很不错的参考范例. 本文介绍的是一个静态的, 无需指针的 succinct 的 trie, 场景略不同. 因为是静态的, 所以优化空间更大.