c++ - 是否有可能编写一个真正通用的磁盘烘焙 B+Tree 实现？

Question

我几次之前用 C++ 编写了一个通用的内存中 B+Tree 实现，我正在考虑让它持久保存在磁盘上(这就是 B+Tree 最初设计的原因)。我的第一个想法是使用 mmap(我在 Linux 下)能够像普通内存一样操作文件，只需重写我的节点类的 new 运算符，以便它返回映射部分中的指针并创建一个智能指针，它可以将 RAM 地址转换为文件偏移量，以将我的节点与其他节点链接起来。但我希望我的实现是通用的，这样用户就可以在 B+ 树中存储一个 int、一个 std::string 或任何他想要的自定义类。这就是问题发生的地方:对于不包含指针的原始类型或聚合类型，这一切都很好，但是一旦对象包含指向堆分配对象的指针/引用，这种方法就不再有效。

所以我的问题是:是否有一些已知的方法来克服这个困难？我对该主题的个人搜索最终没有成功，但也许我遗漏了什么。

Answer 1

据我所知，有三种(比较)简单的方法可以解决这个问题。

方法 1:写一个 std::streambuf指向一些预先分配的内存。

此方法允许您使用 operator<<并使用现有的任何现有代码来获得所需内容的字符串表示形式。

• 专业:重用大量现有代码。
• 缺点:无法控制 operator<<吐出内容。
• 缺点:仅基于文本的表示。

方法 2:编写您自己的(多次重载)输出函数。

• Pro:可以提出二进制表示。
• 专业版:精确控制每一种输出格式。
• 缺点:重写这么多输出函数……客户为新类型编写重载是一件痛苦的事情，因为他们不应该编写属于您库命名空间的函数……除非您求助于 Koenig(参数依赖)查找!

方法 3:写一个 btree_traits<>模板。

• Pro:可以提出二进制表示。
• 专业版:精确控制每一种输出格式。
• 优点:对函数的输出和格式有更多控制，可能包含元数据和所有内容。
• 缺点:仍然需要您/您的库的用户编写大量自定义重载。
• Pro:拥有 btree_traits<>默认使用 operator<<除非有人覆盖这些特征？