LMDB变种提供指纹B-Tree？

Question

一个指针B-树是一种B-树，它跟踪用户指定的关联“汇总”操作在叶子节点上。当节点合并时，使用该操作来组合摘要；当节点拆分时，使用节点的孙子重新计算摘要（但不使用更深的节点）。

通过每次拆分/合并更新摘要数据，指针B-树能够在最多O(log n)页查找（即沿着从根到范围floorkey和范围ceilkey的路径进行查找）中回答任何任意键范围的摘要查询。

我认为LMDB原生不支持这个功能，但我很乐意错。有人知道添加了它的LMDB分支或变体吗？如果没有，是否有其他轻量级持久（不一定事务性）的磁盘B树库可以实现？

- user4718

---

我曾经使用过CouchDB。在那里，指纹B-Tree不是一个选项，我认为这是因为它不能与分片一起使用。 - David Knipe

@DavidKnipe 我不需要分布式数据库。 - user4718

Answer 1

RocksDB提供自定义压缩过滤器和合并操作器，可以用于以相当高效的方式实现这样的摘要。当然，它的架构与LMDB非常不同。

- Florian Weimer

---

谢谢回复，但这两件事都不能提供O(log n)的摘要。 - user4718

你确定吗？确切的时间复杂度类有点难以确定，但我认为这些操作是次线性的，就像其他数据库更新一样。 - Florian Weimer

是的，我非常确定，并且复杂度类别非常容易定义。它也与RocksDB所称的压实和合并无关。 - user4718