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

Я ищу легкую реализацию подкачки с открытым исходным кодом B +, которая использует файл диска для хранения дерева.

До сих пор я нашел только реализации на основе памяти или что-то, зависящее от QT (?!) и даже не компилируется.

Современный С++ предпочтителен, но C тоже сделает.

Я предпочитаю избегать полного встраиваемого СУБД, потому что: 1) для моего нужного индекса костей, который может использовать простейшую возможную организацию дискового файла, достаточно, не нужно concurrency, атомарности и всего остального. 2) Я использую это, чтобы прототипировать свой собственный индекс и, скорее всего, изменит некоторые алгоритмы и макет хранилища. Я хочу сделать это с минимальными усилиями. Это не будет производственный код.

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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

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

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