Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





Рассмотрим два случая. В первом случае пользователь вводит новую логическую запись в конец таблицы. Тогда вводимая логическая запись добавляется в конец файла. Она заносится либо в последнюю физическую запись (если в ней меньше 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, а log2[N/k], т.е. существенно меньше. Однако добавление записи потребует для сохранения упорядоченности, как правило, сдвига большого числа записей. Поэтому размещение физических записей с упорядочением их по значениям ключа в СУБД не используется.

Date: 2015-11-15; view: 415; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.008 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию