openacid/succinct/tree/loc100 ), 区区95行代码, 包含了一组完整的功能:
用 前缀树 存储一个排序数组, 去掉指针, 压缩掉50%的空间; 例如在本文的例子中, 存储2.4MB...于是对于这类key集合确定的场景(例如rocksdb中的sstable, 就是典型的静态排序key的存储), 使用压缩的前缀树是一种更简洁有效的方式来去掉指针开销....前缀树的压缩算法
在这个前缀树中, 每个节点至多有256个出向label, 指向下一级节点. 一个节点可以是inner节点, 例如root节点^, 或1, 2, 3....: 这2块信息是 succinctSet 核心的2个字段, 有了这2部分数据就可以实现(不算高效的)key查找:
压缩后的查询
在标准的 trie 中查找一个 key 很简单, 在第L层的一个节点上,...这就是在压缩前缀树中逐层定位节点的算法.