Введение в информационные системы. Брюхомицкий Ю.А. - 134 стр.

UptoLike

Составители:

Рубрика:

134

Индекс нижнего уровня заполнен полностью. Для включения новой за-

писи из свободной памяти берется блок ячеек и начинается формирование ново-

го уровня индекса. Для этого в последнюю ячейку заносится запись с ключом,

ближайшим по значению к вновь включаемому и имеющимся в нижнем уровне

индекса. Новая запись заносится во вторую ячейку

блока, который указателем

связывается с соответствующей ячейкой стоящего выше уровня.

На рис. 10.5 изображен фрагмент рассмотренного на рис. 10.4 справоч-

ника, в который включена запись с ключом 85. Записи с ключами 71, 79, 84 пе-

редвинуты влево. Во втором уровне индекса ключ 79 заменен на ключ 84. В

отличие от рассмотренного ранее многоуровневого единого справочника в дан-

ном случае

не требуется перезаписи всех уровней справочника.

Рис. 10.5. Фрагмент В-дерева, отражающий включение новой

записи с ключом 85

Предположим, что в справочнике, показанном на рис. 10.4, третий уро-

вень заполнен полностью и для включения новой записи требуется формирова-

ние четвертого уровня. Тогда фрагмент третьего и четвертого уровня этого

справочника

, в который внесена новая запись с ключом 95, будут выглядеть так,

как показано на рис. 10.6.

Рис. 10.6. Фрагмент В-дерева, отражающий включение новой

записи с ключом 95

84 98 119

71 79 84 85 91 98

–

110 119

К основному массиву

71 79 84 85 91 98 102 110 119

- 95 98Четвертый уровень

Третий уровень