Стр. 47 - Основы алгоритмов и структур данных

Содержание 45
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
страница
Рис. 46. Дерево страниц
Относительно оптимального размера страницы: если страница слишком
мала, то их придется прочитать много и число обращений к диску будет велико.
Если станица слишком велика, то она может не вместиться в оперативную
память или несколько последовательно обрабатываемых страниц не вместятся
туда.
Оптимальным считается следующее решение: выбирается некоторая
константа n, физический размер всех страниц 2n ключей. В каждый момент
времени число ключей в странице лежит в диапазоне от n до 2n
(действительный размер страниц вследствие включений-исключений будет
меняться в этих пределах), кроме корневой страницы, которая может содержать
меньшее их количество. Тогда каждая страница имеет от (n+1) до (2n+1) сына
и, таким образом, высота дерева (или затраты на поиск, или число обращений к
диску) составит: в худшем случае, когда все страницы на половину пусты,
О( 1 log n N
+ ), где N – общее число ключей; в лучшем случае, когда страница
заполнена полностью, О( 2 1 log n N
+ ). Кроме того, поскольку страницы всегда
заполнены не менее чем на половину, коэффициент использования внешней
памяти составляет не менее 50%. Другое преимущество ограничения числа
ключей в странице интервалом [n,2n ] несёт в себе удобство и простоту
включения-исключения и позволяет поддерживать дерево внешнего поиска в
сбалансированном состоянии.
3. Каждая дорожка на магнитном диске разбита на секторы. Поскольку
чтение и запись целыми секторами происходит быстрее, целесообразно
физический размер страницы сделать кратным размеру сектора.
Обычно секторы объединяются в кластеры (cluster), поскольку ввод/вывод
кластерами еще быстрее (желательно физический размер страницы сделать
кратным размеру кластера).
Структура данных, соответствующая рассмотренным соображениям,
называют В-деревом.
В-деревья обладают следующими свойствами: