Ищем связанный с диском пример b-дерева - PullRequest
Новая
       12

Ищем связанный с диском пример b-дерева

5 голосов
/ 30 мая 2011

Может быть, мой google-foo просто не подходит, но я хочу поиграть с алогритом b-дерева, привязанным к диску. Поскольку большинство учебных пособий и примеров находятся в оперативной памяти, они предполагают, что оперативная память, в которой изменение узлов в дереве достаточно проста, но кроме интенсивного переписывания ввода-вывода или использования файлов, отображаемых в память, я не могу придумать хорошего подход.

Теория была бы в порядке, C # или Java были бы еще лучше.

РЕДАКТИРОВАТЬ: Я прошу прощения за отсутствие ясности. Я не ищу продукт или кодовую базу для использования, но пример или иллюстративную кодовую базу, чтобы лучше понять, как можно было бы построить b-дерево на основе диска.

Ответы [ 2 ]

2 голосов
/ 30 мая 2011

Одна из самых быстрых БД значения ключа (которая также содержит базу данных значения ключа, которая работает с деревьями B +) - это кабинет Токио (или кабинет Киото) :). Я работал с ним, когда проводил тестирование B + Trees, и код легко понять. Он написан на C, но имеет привязки Java ... Токийский кабинет: http://fallabs.com/tokyocabinet/

И Berkley DB также работает с B + Tree. Однако, когда я проводил сравнительный анализ Berkley DB, он был очень медленным по сравнению с Токийским кабинетом, хотя ... http://www.oracle.com/technetwork/database/berkeleydb/overview/index.html

1 голос
/ 30 мая 2011

Во-первых, посмотрите сверху 2-го, 3-го, 4-го и 5-го результатов из google .

Во-вторых, посмотрите этот стекопоток поток с очень похожим вопросом.

В-третьих, если вы используете MSSQL в качестве примера, вы можете прочитать кое-что здесь и визуализировать страницы, как описано здесь (так же, как и разбиение строки кэша, важно минимизировать такие разбиения).Кроме того, MSSQL, например, накладывает ограничение на размер индексируемых данных, равное 8k = размеру страницы.

В-четвертых, см. Ответ на мой вопрос, который я должен был задать, чтобы быть в состоянии дать этот ответ здесь В качестве альтернативы вы можете использовать шестнадцатеричный редактор, чтобы просмотреть файлы базы данных и посмотреть, как все отображается, но это крайне.

...