1

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

所以我的问题是：是否有一些已知的方法来克服这个困难？我对该主题的个人搜索最终不成功，但也许我错过了一些东西。

4

3 回答 3

4

据我所知，有三种（有点）简单的方法可以解决这个问题。

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

这种方法允许您使用operator<<和使用已经存在的任何现有代码来获取您想要的字符串表示形式。

  • 优点：重用现有代码的负载。
  • 缺点：无法控制如何operator<<吐出内容。
  • 缺点：仅基于文本的表示。

方法2：编写自己的（多次重载）输出函数。

  • Pro：可以提出二进制表示。
  • 优点：精确控制每一种输出格式。
  • 缺点：重新编写这么多输出函数...由客户端为新类型编写重载是一件痛苦的事情，因为他们不应该编写属于您的库名称空间的函数...除非您求助于 Koenig（依赖于参数）查找！

方法3：编写btree_traits<>模板。

  • Pro：可以提出二进制表示。
  • 优点：精确控制每一种输出格式。
  • 优点：对函数的输出和格式进行更多控制，可能包含元数据和所有内容。
  • 缺点：仍然需要您/您的库的用户编写大量自定义重载。
  • 优点：除非有人覆盖特征，否则有使用的btree_traits<>detault吗？operator<<
于 2010-11-25T21:30:09.553 回答
0

您不能编写真正通用和透明的版本，因为如果非平凡项中的指针是用 malloc（或 new 和 new[]）分配的，那么它已经在堆中。

一个不透明的解决方案可能是序列化类是一个选项，这可以相对容易地完成。在存储类之前，您必须调用序列化函数，在拉取它之前，您将调用反序列化。Boost 有很好的序列化特性，你可以使用你的 B+Tree。

于 2010-11-25T21:30:50.650 回答
0

以通用方式处理指针和引用意味着您需要检查您尝试存储的结构的类型及其字段。C++ 是一种不以其反射性而闻名的语言。

但即使在具有强大反射功能的语言中，也很难找到通用的解决方案。您也许可以让它适用于Python、Ruby 等高级语言中的类型子集。一个相关且更强大的范例是持久性编程语言。

您想要的功能通常是通过将写入数据块的责任委托给目标类型本身来实现的。这称为序列化。它只是意味着编写一个接口，其中包含一个转储数据的方法和一个加载数据的方法。任何想要持久保存在 B 树中的类都只需实现此接口。

于 2010-11-25T21:32:19.873 回答