Ищу реализацию дерева B+ на диске в C++ или C

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

Вы также можете рассмотреть возможность повторного использования реализаций B-Tree из встраиваемой базы данных с открытым исходным кодом. (BDB, SQLite и т. д.)

Моя собственная реализация находится под http://www.die-schoens.de/prg. Лицензия Apache. . Он основан на диске, сопоставляется с общей памятью, где он также может выполнять блокировку (т. Е. Многопользовательский), формат файла защищает от сбоев и т. Д. Все вышеперечисленное можно легко отключить (компилировать или запускать, если хотите). Таким образом, голая кость будет почти ANSI-C, в основном кэшируется в собственной памяти и вообще не блокируется. Тестовая программа включена. В настоящее время он имеет дело только с полями фиксированного размера, но я работаю над этим...

Я поддерживаю предложение для Berkeley DB. Я использовал его до того, как его купил Oracle. Это не полноценная реляционная база данных, она просто хранит пары ключ-значение. Мы перешли на это после того, как написали собственную реализацию B-Tree подкачки. Это был хороший опыт обучения, но мы продолжали добавлять функции, пока не превратились в (плохо) реализованную версию BDB.

Если вы хотите сделать это самостоятельно, вот схема того, что мы сделали. Мы использовали mmap для отображения страниц в памяти. Структура каждой страницы была основана на индексе, поэтому с начальным адресом страницы вы могли получить доступ к любому элементу на странице. Затем мы сопоставили и удалили страницы по мере необходимости. Мы индексировали текстовые файлы размером в несколько ГБ, когда 1 ГБ основной памяти считался большим.

C-Tree Plus от Faircom доступен на рынке уже более 20 лет. Не работайте на них и т. д. FairCom

Существует также Berkley DB, которая была куплена Oracle, но по-прежнему бесплатна на их сайте.

Я почти уверен, что это не то решение, которое вы ищете, но почему бы вам не сохранить дерево в файле самостоятельно? Все, что вам нужно, это подход к сериализации и if/ofstream.

По сути, вы можете сериализовать это так: перейдите в корень, напишите «0» в своем файле, разделитель, например «|», количество элементов в корне, а затем все корневые элементы. Повторите с «1» для уровня 1 и так далее. Пока вы не измените уровень, сохраните индекс уровня, пустые листья могут выглядеть как 2|0.

Вы можете посмотреть на Berkeley DB, он поддерживается ny Oracle, но это открытый исходный код, и его можно найти здесь.

RogueWave, компания-разработчик программного обеспечения, имеет хорошую реализацию BTreeOnDisk как часть своего продукта Tools++. Пользуюсь с конца 90-х. Хорошая вещь в том, что вы можете иметь несколько деревьев в одном файле. Но вам нужна коммерческая лицензия.

В своем коде они ссылаются на книгу парня по имени Аммераал (см. http://home.planet.nl/~ammeraal/algds.html , Ammeraal, L. (1996) Алгоритмы и структуры данных в C++). Кажется, у него есть реализация BTree на диске, а исходный код доступен в Интернете. Я никогда не использовал его, хотя.

В настоящее время я работаю над проектами, для которых я хотел бы распространять исходный код, поэтому мне нужно найти замену классам Rogue Wave с открытым исходным кодом. К сожалению, я не хочу полагаться на лицензии типа GPL, иначе решением было бы просто использовать «libdb» или эквивалент. Мне нужна лицензия типа BSD, и я долго не мог найти ничего подходящего. Но я посмотрю на некоторые ссылки в предыдущих сообщениях.