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

Содержание 47
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.5.1. Алгоритм поиска
Считываем корневую страницу с магнитного диска в оперативную память.
Поскольку поиск, а следовательно, включение и выключение всегда начинается
с корневой страницы, то ее целесообразно всегда держать в оперативной
памяти. Производим бинарный поиск внутри текущей страницы. Если поиск
закончился удачей, – УРА, если поиск закончился неудачей, – переходим к
соответствующей дочерней странице.
?Самостоятельно записать алгоритм поиска?
В общем случае алгоритм обработки в ОП текущей страницы имеет
следующий вид:
if (успешный поиск z) <успех>
else
{




= <
= <<
= <
+
; then
; then
; then
1i
0 0
m i
i i
P P z x
P P x z x
PP x z
case
}
Считываем в оперативную память страницу с адресом P и обрабатываем её
таким же способом.
4.5.2. Алгоритм включения
Начинаем с поиска. Поиск либо заканчивается успехом, тогда включать
ничего не нужно, либо заканчивается неуспехом в одной из листовых страниц.
Например, если z = 10 – есть, то включать не надо.
Если z = 11, – неуспех в листе.
Если страница, в которой поиск заканчивается неуспехом, имеет m < 2 n
ключей (z = 23), то просто включаем этот ключ в данную страницу.
Если же страница, в которую мы включаем новый ключ, уже содержит m =
=2n ключей, то при попытке добавить в нее происходит переполнение
страницы (z = 16). Для обработки переполнения поступаем следующим
образом: делаем ее на 2 страницы, при этом каждая новая страница будет
содержать n ключей, а средний ключ включаем в отцовскую страницу.