My own implementation is under http://www.die-schoens.de/prg License is Apache. Its disk-based, maps to shared memory where it also can do locking (i. e. multiuser), file format protects against crash etc. All of the above can be easily switched off (compile or runtime if you like). So bare bone would be almost ANSI-C, basically caching in ones own memory and not locking at all. Test program is included. Currently, it only deals with fixed-size fields, but I am working on that...
I second the suggestion for Berkeley DB. I used it before it was bought by Oracle. It is not a full relational database, but just stores key-value pairs. We switched to that after writing our own paging B-Tree implementation. It was a good learning experience, but we kept adding features until is was just a (poorly) implemented version of BDB.
If you want to do it yourself, here is an outline of what we did. We used mmap to map pages into memory. The structure of each page was index based, so with the page start address you could access any element on the page. Then we mapped and unmapped pages as necessary. We were indexing multi GB text files, back when 1 GB of main memory was considered a lot.
I' pretty sure it's not the solution you're looking but why don't you store the tree in a file yourself? All you need is an approach for serialization and an if/ofstream.
Basically you could serialize it like that: go to root, write '0' in your file a divider like '|', the number of elements in root and then all root elements. Repeat with '1' for level 1 and so on. As long as you don't change the level keep the level index, empty leafs could look like 2|0.
RogueWave, the software company, have a nice implementation of BTreeOnDisk as part of their Tools++ product. I've been using it since late 90's. The nice thing about it is that you can have multiple trees in one file. But you do need a commercial license.
In their code they do make a reference to a book by a guy called 'Ammeraal' (see http://home.planet.nl/~ammeraal/algds.html , Ammeraal, L. (1996) Algorithms and Data Structures in C++). He seems to have an imlementation of a BTree on disk, and the source code seems to be accessible online. I have never used it though.
I currently work on projects for which I'd like to distribute the source code so I need to find an open source replacement for the Rogue Wave classes. Unfortunately I don't want to rely on GPL type licenses, otherwise a solution would be simply to use 'libdb' or equivalent. I need a BSD type license, and for a long time I couldn't find anything suitable. But I will have a look at some the links in earlier posts.
发布评论
评论（7）
http://people.csail.mit.edu/jaffer/WB。
您还可以考虑重新使用开源可嵌入数据库中的 B 树实现。 （BDB，SQLite 等）
http://people.csail.mit.edu/jaffer/WB.
You can also consider re-using the B-Tree implementations from an open source embeddable database. (BDB, SQLite etc)
我自己的实现是在 http://www.die-schoens.de/prg 许可证是 Apache 。它基于磁盘，映射到共享内存，它还可以进行锁定（即多用户）、文件格式防止崩溃等。以上所有内容都可以轻松关闭（如果您愿意，可以编译或运行时）。所以基本结构几乎是 ANSI-C，基本上缓存在自己的内存中并且根本不锁定。包括测试程序。目前，它只处理固定大小的字段，但我正在努力......
My own implementation is under http://www.die-schoens.de/prg License is Apache. Its disk-based, maps to shared memory where it also can do locking (i. e. multiuser), file format protects against crash etc. All of the above can be easily switched off (compile or runtime if you like). So bare bone would be almost ANSI-C, basically caching in ones own memory and not locking at all. Test program is included. Currently, it only deals with fixed-size fields, but I am working on that...
我赞同 Berkeley DB 的建议。我在被Oracle收购之前就用过它。它不是一个完整的关系数据库，而只是存储键值对。在编写我们自己的分页 B 树实现后，我们转向了这一点。这是一次很好的学习经历，但我们不断添加功能，直到它只是 BDB 的一个（糟糕的）实现版本。
如果您想自己做，这里是我们所做的概述。我们使用 mmap 将页面映射到内存中。每个页面的结构都是基于索引的，因此通过页面起始地址，您可以访问页面上的任何元素。然后我们根据需要映射和取消映射页面。当 1 GB 主内存被认为很多时，我们正在索引多 GB 文本文件。
I second the suggestion for Berkeley DB. I used it before it was bought by Oracle. It is not a full relational database, but just stores key-value pairs. We switched to that after writing our own paging B-Tree implementation. It was a good learning experience, but we kept adding features until is was just a (poorly) implemented version of BDB.
If you want to do it yourself, here is an outline of what we did. We used mmap to map pages into memory. The structure of each page was index based, so with the page start address you could access any element on the page. Then we mapped and unmapped pages as necessary. We were indexing multi GB text files, back when 1 GB of main memory was considered a lot.
Faircom 的 C-Tree Plus 已投入商业使用 20 多年。不要为他们工作等等... FairCom
还有Berkley DB 已被 Oracle 收购，但仍可在其网站上免费使用。
Faircom's C-Tree Plus has been available commercially for over 20 years. Don't work for them etc... FairCom
There is also Berkley DB which was bought by Oracle but is still free from their site.
我很确定这不是您正在寻找的解决方案，但是您为什么不自己将树存储在文件中呢？您所需要的只是一种序列化方法和 if/ofstream。
基本上你可以像这样序列化它：转到根，在文件中写入“0”，像“|”这样的分隔符，根中的元素数量，然后是所有根元素。对级别 1 重复“1”，依此类推。只要您不更改级别并保持级别索引，空叶子可能看起来像 2|0。
I' pretty sure it's not the solution you're looking but why don't you store the tree in a file yourself? All you need is an approach for serialization and an if/ofstream.
Basically you could serialize it like that: go to root, write '0' in your file a divider like '|', the number of elements in root and then all root elements. Repeat with '1' for level 1 and so on. As long as you don't change the level keep the level index, empty leafs could look like 2|0.
您可以查看 Berkeley DB，它支持 ny Oracle，但它是开源的，可以找到 这里。
You could look at Berkeley DB, its supported ny Oracle but it is open source and can be found here.
RogueWave 软件公司在其 Tools++ 产品中很好地实现了 BTreeOnDisk。我从 90 年代末就开始使用它。它的好处是您可以在一个文件中包含多棵树。但您确实需要商业许可证。
在他们的代码中，他们确实引用了一个叫“Ammeraal”的人写的书（请参阅 http: //home.planet.nl/~ammeraal/algds.html，Ammeraal, L. (1996) C++ 中的算法和数据结构）。他似乎在磁盘上实现了 BTree，并且源代码似乎可以在线访问。但我从未使用过它。
我目前正在从事一些项目，我想为其分发源代码，因此我需要找到 Rogue Wave 类的开源替代品。不幸的是，我不想依赖 GPL 类型许可证，否则解决方案就是简单地使用“libdb”或等效项。我需要 BSD 类型的许可证，但很长一段时间我找不到合适的。但我会看一下之前帖子中的一些链接。
RogueWave, the software company, have a nice implementation of BTreeOnDisk as part of their Tools++ product. I've been using it since late 90's. The nice thing about it is that you can have multiple trees in one file. But you do need a commercial license.
In their code they do make a reference to a book by a guy called 'Ammeraal' (see http://home.planet.nl/~ammeraal/algds.html , Ammeraal, L. (1996) Algorithms and Data Structures in C++). He seems to have an imlementation of a BTree on disk, and the source code seems to be accessible online. I have never used it though.
I currently work on projects for which I'd like to distribute the source code so I need to find an open source replacement for the Rogue Wave classes. Unfortunately I don't want to rely on GPL type licenses, otherwise a solution would be simply to use 'libdb' or equivalent. I need a BSD type license, and for a long time I couldn't find anything suitable. But I will have a look at some the links in earlier posts.