Добавление записи

Рассмотрим два случая. В первом случае пользователь вводит новую логическую запись в конец таблицы. Тогда вводимая логическая запись добавляется в конец файла. Она заносится либо в последнюю физическую запись (если в ней меньше k логических записей – блок неполон), для чего эта запись должна быть считана в ОП, или формируется новая физическая запись, которая заносится в конец файла. Число обращений к ВП равно соответственно либо 2, либо 1.

Во втором случае пользователь вводит новую логическую запись в указываемую им i-ю строку таблицы (i=1, 2, …, n). В этом случае читается физическая запись с номером [(i-1)/k], содержащая i-ю логическую запись. Если соответствующая физическая запись содержит пустые логические записи, то добавляемая запись вставляется в этот блок, блок записывается на свое место в ВП. Число обращений к ВП равно 2. Если указанная физическая запись содержит k экземпляров логических записей исходной таблицы, читается физическая запись с номером ⎡⎤ k i. Если эта физическая запись содержит пустые логические записи, добавляемая запись вставляется в этот блок, блок записывается на свое место в ВП. Суммарное число обращений в этом случае будет на единицу больше и равно 3.

Если физические записи с номерами [(i-1)/k] и [i/k] содержат по k экземпляров исходных логических записей, необходимо формировать дополнительную физическую запись.

Соответствующий блок будет содержать добавляемую логическую запись и k-1 пустых логических записей. Блоки с номерами [i/k], [i+1/k], … [N/k] переписываются на одну позицию ниже (сдвигаются). Сформированная физическая запись заносится на освободившееся место (место записи с номером [i/k]).

В лучшем случае (i = N) ни один блок не сдвигается. В худшем случае (i = 1) сдвигаются все блоки. Среднее число обращений к ВП для перезаписи блоков (чтение + запись) составит 2[N/k]/2. Тогда суммарное число обращений к ВП при добавлении записи в этом случае будет равно 3+ [N/k].

Заметим, что если записи упорядочены по значениям ключа может производиться дихотомическим методом и число обращений к внешней памяти будет пропорционально не (1+ [i/k])/2, а log₂[N/k], т.е. существенно меньше. Однако добавление записи потребует для сохранения упорядоченности, как правило, сдвига большого числа записей. Поэтому размещение физических записей с упорядочением их по значениям ключа в СУБД не используется.

Date: 2015-11-15; view: 445; Нарушение авторских прав