我正在寻找一个轻量级的开源分页 B+ 树实现，它使用磁盘文件来存储树。
到目前为止，我只发现了基于内存的实现，或者依赖于 QT（？！）并且甚至无法编译的东西。
现代 C++ 是首选，但 C 也可以。
我更喜欢避免完全嵌入的 DBMS 解决方案，因为：1）对于我的需要，可以使用最简单的磁盘文件组织的裸骨索引就足够了，不需要并发性、原子性和其他一切。2）我正在使用它来原型化我自己的索引，并且很可能会改变一些算法和存储布局。我想用最少的努力做到这一点。它不会是生产代码。
问问题
21044 次
7 回答
9
于 2009-11-12T08:48:11.433 回答
4
我自己的实现是在http://www.die-schoens.de/prg许可证是 Apache。它基于磁盘，映射到共享内存，它还可以在其中进行锁定（即多用户），文件格式可以防止崩溃等。以上所有内容都可以轻松关闭（如果您愿意，可以编译或运行时）。所以裸露的骨头几乎是ANSI-C，基本上缓存在自己的内存中，根本不加锁。包括测试程序。目前，它只处理固定大小的字段，但我正在努力......
于 2011-06-05T19:10:56.343 回答
3
Faircom 的 C-Tree Plus 已上市 20 多年。不要为他们工作等等...... FairCom
还有被甲骨文收购的Berkley DB，但仍然可以从他们的网站上免费获得。
于 2009-11-12T10:57:15.703 回答
3
我支持 Berkeley DB 的建议。我在它被甲骨文收购之前使用它。它不是一个完整的关系数据库，只是存储键值对。在编写了自己的分页 B-Tree 实现后，我们切换到了这个。这是一次很好的学习体验，但我们一直在添加功能，直到它只是一个（糟糕）实现的 BDB 版本。
如果你想自己做，这里是我们所做的概述。我们使用 mmap 将页面映射到内存中。每个页面的结构都是基于索引的，因此您可以使用页面起始地址访问页面上的任何元素。然后我们根据需要映射和取消映射页面。当 1 GB 的主内存被认为很多时，我们正在索引多 GB 的文本文件。
于 2009-11-12T15:01:30.987 回答
1
软件公司 RogueWave 很好地实现了 BTreeOnDisk，作为其 Tools++ 产品的一部分。我从 90 年代后期开始使用它。它的好处是您可以在一个文件中包含多个树。但是您确实需要商业许可证。
在他们的代码中，他们确实引用了一个叫做“Ammeraal”的人的书（参见http://home.planet.nl/~ammeraal/algds.html , Ammeraal, L. (1996) Algorithms and Data Structures in C++ ）。他似乎在磁盘上有一个 BTree 的实现，源代码似乎可以在线访问。我从来没有使用过它。
我目前正在处理我想要分发源代码的项目，因此我需要找到 Rogue Wave 类的开源替代品。不幸的是，我不想依赖 GPL 类型的许可证，否则解决方案就是使用“libdb”或等效的。我需要一个 BSD 类型的许可证，很长一段时间我都找不到合适的。但我会看看之前帖子中的一些链接。
于 2014-08-15T08:56:50.707 回答
1
您可以查看 Berkeley DB，它支持的 ny Oracle，但它是开源的，可以在此处找到。
于 2009-11-12T11:06:47.103 回答
1
我很确定这不是您正在寻找的解决方案，但是您为什么不自己将树存储在文件中呢？您所需要的只是一种序列化方法和一个 if/ofstream。
基本上你可以像这样序列化它：转到根目录，在文件中写入“0”，像“|”这样的分隔符，根目录中的元素数量，然后是所有根元素。对级别 1 重复“1”，依此类推。只要您不更改级别保持级别索引，空叶子可能看起来像 2|0。
于 2009-11-12T08:44:14.220 回答