Последовательное построение полных B-деревьев

Question

Если у меня есть отсортированный набор данных, который я хочу сохранить на диске таким образом, чтобы он был оптимальным как для последовательного чтения, так и для случайного поиска, то кажется, что B-дерево (или один из вариантов являетсяхороший выбор ... при условии, что этот набор данных не умещается в ОЗУ).

Вопрос в том, можно ли построить полное B-дерево из отсортированного набора данных, не разбивая страницы?Чтобы отсортированные данные могли быть записаны на диск последовательно.

Answer 1

Построить «дерево B +» по этим спецификациям просто.

1. Выберите коэффициент ветвления k.
2. Записать отсортированные данные в файл. Это уровень листа.
3. Чтобы построить следующий самый высокий уровень, отсканируйте текущий уровень и запишите каждый элемент k ^th .
4. Стоп, когда на текущем уровне k элементов или меньше.

Пример с k = 2:

0 1|2 3|4 5|6 7|8 9
0   2  |4   6  |8
0       4      |8
0               8

Теперь давайте посмотрим на 5. Используйте бинарный поиск, чтобы найти последнее число, меньшее или равное 5 на верхнем уровне или 0. Посмотрите на интервал в следующем нижнем уровне, соответствующем 0:

0       4

Сейчас 4:

        4   6

Теперь 4 Опять:

        4 5

Нашел это. В общем, элемент j ^th соответствует элементам jk, хотя (j + 1) k-1 на следующем уровне. Вы также можете сканировать уровень листа линейно.

Answer 2

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

Тем не менее, предположим, что каждая запись в вашем b-дереве содержит (m - 1) ключей ( m > 2, двоичный регистр немного отличается). Мы хотим, чтобы все листья на одном уровне и все внутренние узлы имели как минимум ключи (m - 1) / 2 . Мы знаем, что полное b-дерево высотой k имеет (m ^ k - 1) ключей. Предположим, что у нас есть n ключей для хранения. Пусть k будет наименьшим целым числом таким, что m ^ k - 1> n . Теперь, если 2 m ^ (k - 1) - 1 , мы можем полностью заполнить внутренние узлы и равномерно распределить оставшиеся ключи по листовым узлам, причем каждый листовой узел получает либо слово, либо потолок (n + 1 - m ^ (k - 1)) / m ^ (k - 1) ключей. Если мы не можем этого сделать, то мы знаем, что у нас достаточно, чтобы заполнить все узлы на глубине k - 1 хотя бы наполовину и сохранить один ключ в каждом из листьев.

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

Answer 3

Оптимальный означает, что при прохождении данных по порядку всегда будет выполняться поиск по файлу (или области mmaped), а случайный поиск выполняется за минимальное количество запросов.