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

Question

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

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

Answer 1

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

1. Выберите коэффициент размножения k.
2. Напишите отсортированные данные в файл. Это уровень листа.
3. Чтобы построить следующий самый высокий уровень, сканируйте текущий уровень и выпишите каждый k ^th вещь.
4. Остановить, если текущий уровень имеет 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-дерево за один проход, но это может быть не оптимальный метод хранения. В зависимости от того, как часто вы выполняете последовательные запросы по сравнению с произвольным доступом, может быть лучше сохранить его в последовательности и использовать двоичный поиск для обслуживания запроса с произвольным доступом.

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

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

Answer 3

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