Вставка и удаление в сортированной таблице
 |
При вставке новой записи в сортированной таблице, требуется найти место в которое её следует поместить (время ~
) и сдвинуть все записи от места вставки и ниже на одну позицию вниз. Аналогично, при удалении требуется найти удаляемую запись и все записи ниже удаляемой сдвинуть на одну позицию вверх. Обе операции требуют физического перемещения в среднем 
записей. Таким образом, при таком простодушном поведении, мы проигрываем все преимущества сортированной таблицы для операции поиска. Поэтому при удалении запись не удаляют физически, а лишь помечают как удаленную в специально отведенном байте. При вставке находят ту позицию, в которую следовало бы поместить новую запись, чтобы она не нарушала порядка, но не помещают ее туда, а помещают в линейный список,
начинающийся с позиции вставки, как на рис.31.
Рис.31. Сортированная таблица с цепочками переполнения
При поиске записи теперь следует найти позицию, в которой должна была бы находиться запись и, отправляясь от нее пройти линейный список, исходящий из этой позиции. Очевидно, что после большого количества вставок, поиск будет все больше походить на простой перебор записей. Рано или поздно, придется переписать таблицу как сортированную заново, таким образом, чтобы в ней не было удаленных позиций и цепочек переполнения. Отложенные операции обслуживания характерны для всех способов организации таблиц, кроме древовидных.
Дата добавления: 2014-12-02; просмотров: 1082;