Реализация B-дерева для ключей переменного размера

Question

Я ищу реализацию B-дерева (на Java) для индекса «одноразового использования», в который вставляется несколько миллионов ключей, а затем выполняется несколько запросов для каждого ключа. Ключи представляют собой <= 40-байтовые строки ascii, и связанные данные всегда занимают 6 байтов. Структура B-дерева была выбрана, потому что мой бюджет памяти не позволяет мне хранить весь временный индекс в памяти. </p>

Моя проблема касается практических деталей выбора фактора ветвления и хранения узлов на диске. Мне кажется, что есть два подхода:

• Один узел всегда помещается в одном блоке. Достигается путем выбора коэффициента ветвления k, чтобы даже для наихудшей длины ключа требования к хранилищу ключей, данных и структур управления были <= размер системного блока. k, вероятно, будет низким, и узлы в большинстве случаев будут иметь много пустого пространства. </li>
• Один узел может храниться в нескольких блоках. Коэффициент ветвления выбирается независимо от размера ключа. Загрузка одного узла может потребовать загрузки нескольких блоков.

Вопросы тогда:

• Является ли второй подход тем, что обычно используется для ключей переменной длины? или есть какой-то совершенно другой подход, который я пропустил?
• Учитывая мой вариант использования, вы бы порекомендовали другое общее решение?

В заключение я должен упомянуть, что мне известен проект jdbm3, и он рассматривает возможность его использования. В любом случае я попытаюсь реализовать свою собственную, как в качестве учебного упражнения, так и посмотреть, может ли оптимизация для конкретного случая привести к лучшей производительности.

Редактировать: Чтение о SB-деревьях в данный момент:

• S (b) -Деревья
• Алгоритмы и структуры данных для внешней памяти

Answer 1

Мне не хватает опции C здесь:

• Как минимум два кортежа всегда помещаются в один блок, размер блока выбирается соответственно.Блоки заполняются как можно большим количеством пар ключ / значение, что означает, что коэффициент ветвления является переменным.Если размер блока намного больше среднего размера кортежа (ключ, значение), потраченное пространство будет очень низким.Поскольку оптимальный размер ввода-вывода для дисков обычно составляет 4 КБ или более, а размер кортежа максимальный равен 46, это автоматически относится к вашему случаю.

И для всех вариантов, которые выесть несколько вариантов: B * или B + Trees (см. Википедия).

Answer 2

JDBM BTree уже самобалансируется.Он также имеет дефрагментацию, которая очень быстрая и решает все проблемы, описанные выше.

Один узел может храниться в нескольких блоках.Коэффициент ветвления выбирается независимо от размера ключа.Загрузка одного узла может потребовать загрузки нескольких блоков.

Не обязательно.JDBM3 использует отображенную память, поэтому он никогда не считывает полный блок с диска в память.Он создает «представление» поверх блока и считывает только частичные данные по мере необходимости.Таким образом, вместо чтения полного блока 4 КБ, он может читать только 2x128 байтов.Это зависит от размера блока ОС.

Является ли второй подход тем, что обычно используется для ключей переменной длины?или есть какой-то совершенно другой подход, который я пропустил?

Я думаю, вы упустили момент, что увеличение размера диска снижает производительность, так как необходимо читать больше данных.И у одного дерева могут быть общие подходы (сначала вставленные узлы, затем после дефрагментации).

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

Также посмотрите на leveldb.Он имеет новый порт Java, который почти превосходит JDBM:

https://github.com/dain/leveldb

http://code.google.com/p/leveldb/

Answer 3

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

Вы также пишете: "несколько миллионов ключей" ... "[max] 40-байтовые строки ascii" и "6 байтов [связанные данные]".Это не считается правильно.Один гигабайт оперативной памяти даст вам больше, чем «несколько миллионов» записей.