代码之家 › 专栏 › 技术社区 › Laurynas Biveinis

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

b-tree data-structures c c++

Laurynas Biveinis · 技术社区 · 15 年前

我正在寻找一个轻量级的开源分页b+树实现,它使用一个磁盘文件来存储树。

到目前为止我只发现 memory-based implementations 或 something 它依赖于qt(?)!)甚至不编译。

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

我更喜欢避免使用完全可嵌入的dbms解决方案,因为:1)对于我的需求,可以使用最简单的磁盘文件组织的裸骨骼索引就足够了,不需要并发性、原子性和其他任何东西。2)我用这个来建立自己的索引原型,很可能会改变一些算法和存储布局。我想用最少的努力做到这一点。不会是生产代码。

7 回复 | 直到 14 年前

Vijay Mathew Chor-ming Lung 15 年前

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

您还可以考虑重新使用来自开源可嵌入数据库的b树实现。( BDB , SQLite 等)

AnthonyLambert 15 年前

Faircom的C-Tree Plus已经在商业上销售了20多年。别为他们工作等… FairCom

还有 Berkley DB 这是甲骨文收购的,但仍然免费从他们的网站。

Joerg Schoen 13 年前

我自己的实现 http://www.die-schoens.de/prg 许可证是apache。它基于磁盘,映射到共享内存,在那里它也可以做锁定(即多用户),文件格式防止崩溃等。所有上述都可以很容易地关闭(编译或运行,如果你喜欢)。因此,裸骨骼几乎是ansi-c,基本上是缓存在自己的内存中,根本不锁定。包括测试程序。目前,它只处理固定大小的字段,但我正在努力…

BatchyX 15 年前

我支持伯克利DB的建议。在被甲骨文收购之前我就用过。它不是一个完整的关系数据库,只是存储键值对。在编写了自己的分页b树实现之后,我们切换到了这一点。这是一个很好的学习体验,但是我们一直在添加特性,直到它只是bdb的(糟糕的)实现版本。

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

DaClown 15 年前

我很确定这不是你正在寻找的解决方案,但你为什么不自己将树存储在一个文件中呢?您只需要一种序列化方法和一个if/of流。

基本上可以这样序列化:转到根目录,在文件中写入“0”分隔符,如“”,根目录中的元素数,然后是所有根元素。对级别1重复“1”,以此类推。只要不更改level keep the level index,空叶可能看起来像2 0。

Jackson 15 年前

你可以看看Berkeley DB,它支持的NY Oracle,但是它是开源的,可以找到 here .

Peter Ritter 10 年前

RogueWave是一家软件公司,它有一个很好的Btreeondisk实现,作为其工具++产品的一部分。我从90年代后期就开始使用它了。它的好处是你可以在一个文件中有多个树。但你需要商业执照。

在他们的代码中,他们确实引用了一本叫做“ammeraal”的书(参见 http://home.planet.nl/~ammeraal/algds.html ,Ammeraal,L.(1996),C++中的算法和数据结构。他似乎在磁盘上有一个btree的元素,并且源代码似乎可以在线访问。但我从来没用过。

我目前正在为那些我想发布源代码的项目工作,所以我需要找到一个开源的rogue wave类的替代品。不幸的是,我不想依赖GPL类型的许可证,否则一个解决方案就是简单地使用“libdb”或等效的。我需要一个bsd类型的许可证,很长一段时间我找不到任何合适的。不过,我会看看前面文章中的一些链接。