在C++或C中寻找基于磁盘的B+树实现

Question

我正在寻找一款轻量级的开源分页B+树实现，它使用磁盘文件来存储树结构。

到目前为止，我只找到了基于内存的实现，或者某些依赖于QT（？！）且甚至无法编译。

现代C++是首选，但C也可以。

我希望避免完整的可嵌入DBMS解决方案，因为：1）对于我的需求，能够使用最简单的磁盘文件组织的裸骨索引就足够了，不需要并发性、原子性和其他所有东西。2）我正在使用它来原型化自己的索引，并且很可能会更改一些算法和存储布局。我想尽可能地减少工作量。这不会成为生产代码。

- Laurynas Biveinis

---

你找到了任何实现吗？因为我有和你一样的需求。另外，由于依赖关系，我不能使用现有的DBMS解决方案。 - Jannat Arora

@JannatArora，我最终自己编写了一个（不完整的；仅包含插入和查询）B+-树，它在http://libspatialindex.github.com/磁盘I/O例程的基础上构建。 - Laurynas Biveinis

Answer 1

http://people.csail.mit.edu/jaffer/WB。

您还可以考虑重复使用来自开源可嵌入数据库的B-Tree实现。（BDB，SQLite等）

- Vijay Mathew

---

@kastauyra 只需使用B-Tree实现，而不是整个DBMS。 - Vijay Mathew

可能是可以的，但上次我研究它时发现从整个DBMS中剥离索引非常混乱，有太多的依赖关系。 - Laurynas Biveinis

那么，哪些B树实现可以轻松地从这些数据库中获取？我一直在积极寻找，但是没有找到任何一个。 - Joe Soul-bringer

@Joe Soul-bringer，对于SQLite，请查看btree.h中的接口及其在btree.c中的实现。 - Vijay Mathew

@JoeSoul-bringer，你有没有找到符合上述要求的B+树实现？ - Jannat Arora

Answer 2

我自己的实现是在http://www.die-schoens.de/prg下使用Apache许可证。它基于磁盘，并映射到共享内存中，也可以进行锁定（即多用户），文件格式可防止崩溃等。所有上述功能都可以轻松关闭（如果需要，可以在编译时或运行时关闭）。因此，最基本的情况几乎是ANSI-C，基本上只是将缓存存在自己的内存中，根本不需要锁定。测试程序已包含。目前，它仅处理固定大小的字段，但我正在努力改进...

- Joerg Schoen

Answer 3

Faircom的C-Tree Plus已经商业化超过20年。不要为他们工作等等... FairCom

还有Berkley DB，它被Oracle收购，但仍可从其网站免费下载。

- AnthonyLambert

Answer 4

我赞同使用Berkeley DB的建议。我在Oracle收购它之前就使用过它。它不是完整的关系型数据库，而只是存储键值对。我们在编写自己的分页B-Tree实现之后切换到了它。这是一个很好的学习经验，但我们不断添加功能，直到它成为了（糟糕的）BDB版本。

如果你想自己做，这里是我们所做的概述。我们使用mmap将页面映射到内存中。每个页面的结构都是基于索引的，因此通过页面起始地址，您可以访问页面上的任何元素。然后我们根据需要映射和取消映射页面。当1 GB的主存被认为是很多时，我们正在索引多GB的文本文件。

- KeithB

Answer 5

我很确定这不是你要找的解决方案，但为什么不自己将树存储在文件中呢？你只需要一个序列化方法和一个 if/ofstream。

基本上，你可以像这样进行序列化：从根节点开始，在文件中写入“0”作为分隔符，然后写入根节点元素的数量以及所有根节点元素。对于第一层，重复此过程并写入“1”，以此类推。只要你不改变层级，就保持层级索引，空叶子看起来可能像 2|0。

- DaClown

---

我不想在内存中构建树，然后将其序列化。我希望在磁盘上构建树，在任何给定时间仅在内存中拥有其节点的子集。 - Laurynas Biveinis

你正在寻找对B树进行分页的方法。也许你可以在你的问题中澄清这一点？ - DaClown

这是我第一次听说它被称为“分页”树，但是请看这里。 - Laurynas Biveinis

这不是分页树。你拥有的是一种数据结构，你想在内存中处理其中的一个子集，但整个结构存储在硬盘上。加载大于内存的数据子集称为分页。 - DaClown

Answer 6

你可以看一下伯克利数据库，它得到了 Oracle 的支持，但它是开源的，可以在这里找到。

- Jackson

Answer 7

RogueWave是一家软件公司，他们在其Tools++产品中有一个很好的BTreeOnDisk实现。我自从90年代末就一直在使用它。它的好处是您可以在一个文件中拥有多个树。但是您需要商业许可证。

在他们的代码中，他们提到了一个名叫"Ammeraal"的人写的书（参见http://home.planet.nl/~ammeraal/algds.html，Ammeraal, L. (1996) Algorithms and Data Structures in C++）。他似乎有一个BTree On Disk的实现，并且源代码似乎在线可访问。不过我从未使用过。

我目前正在处理的项目需要分发源代码，因此我需要查找替换Rogue Wave类的开源解决方案。不幸的是，我不想依赖于GPL类型的许可证，否则解决方案只需使用'libdb'或相当的东西即可。我需要BSD类型的许可证，很长时间以来我都找不到合适的东西。但我会看一下早期帖子中的一些链接。

- Peter Ritter