ВУЗ:
Составители:
133
мому значением ключа. От этой записи переходят в порожденный блок третьего
уровня и т.д. вплоть до нахождения нужной записи в основном массиве или до
выработки сообщения об отсутствии нужной записи.
Максимальное число операций сравнения, необходимых для просмотра
справочника, равно mM, где М − число уровней индекса; m −
число интерва-
лов в каждом уровне индекса. Минимальное число операций сравнения равно
М.
Новая запись включается в справочник в соответствии со значением ее
ключа, упорядоченность уровней индекса при этом не должна нарушаться. В
зависимости от состояния нижнего уровня индекса при включении
новой записи возможны следующие варианты:
Рис. 10.4. В-дерево трехуровневого справочника
В соответствующем блоке нижнего уровня индекса есть свободная
ячейка. В этом случае новая запись размещается в этой ячейке. Так, например, в
В-дереве, показанном на рис. 10.4, запись с ключом 70 будет размещена в пер-
вой ячейке четвертого блока.
В нужном блоке нижнего
уровня индекса нет свободной ячейки. В этом
случае записи нижнего уровня передвигаются в сторону ближайшей свободной
ячейки другого блока. В освободившуюся ячейку помещается новая запись. При
необходимости корректируются стоящие выше уровни индекса.
К основному
массиву
7
13
19
К основному массиву
–
32 39
–
52 59
–
71 79 84 91 98
–
110 119
–
–
138
–
150 157
–
170 178
Место записи с
ключом 70
59 119 178
19 39 59 79 98 119 138 157 178
К основному
массиву
Страницы
- « первая
- ‹ предыдущая
- …
- 131
- 132
- 133
- 134
- 135
- …
- следующая ›
- последняя »
