Я хочу реализовать B-дерево (на Java) для индекса «одноразового использования», куда вставляются несколько миллионов ключей, а затем запросы выполняются несколько раз для каждого ключа. Ключи представляют собой строки ascii ‹= 40 байтов, а связанные данные всегда занимают 6 байтов. Структура B-tree была выбрана потому, что мой бюджет памяти не позволяет мне хранить в памяти весь временный индекс.
Моя проблема связана с практическими деталями выбора фактора ветвления и хранения узлов на диске. Мне кажется, есть два подхода:
- Один узел всегда помещается в один блок. Достигается за счет выбора коэффициента ветвления k, так что даже для наихудшей длины ключа требования к хранению ключей, данных и управляющих структур составляют ‹= размер системного блока. k, вероятно, будет низким, и в большинстве случаев в узлах будет много пустого места.
- Один узел может храниться на нескольких блоках. Коэффициент ветвления выбирается независимо от размера ключа. Для загрузки одного узла может потребоваться загрузка нескольких блоков.
Тогда возникают следующие вопросы:
- Второй подход обычно используется для ключей переменной длины? или есть какой-то совершенно другой подход, который я пропустил?
- Учитывая мой вариант использования, вы бы порекомендовали другое общее решение?
В заключение я должен упомянуть, что я знаю о проекте jdbm3 и рассматриваю возможность его использования. В любом случае попытаюсь реализовать свою собственную, как в качестве обучающего упражнения, так и для того, чтобы увидеть, может ли оптимизация для конкретного случая повысить производительность.
Изменить: чтение о SB-Trees на данный момент:
