Поиск записи с заданным значением ключа
При последовательной структуре хранения поиск может осуществляться только перебором. Читается первая физическая запись, в ОП она разбивается на k логических записей (разблокируется), заданное значение ключа сравнивается со значением ключа каждой логической записи. При несовпадении читается следующая физическая запись и процесс повторяется. В лучшем случае нужная запись будет найдена за одно обращение, в худшем – необходимо считать все физические записи. Среднее число обращений к внешней памяти для поиска нужной записи ТР определяется следующей формулой ТР = (1+ где N – число логических записей, k – коэффициент блокировки, Чтение записи с заданным значением ключа Сначала необходимо найти нужную запись (смотри операцию «поиск»). После окончания операции «поиск» нужная запись уже считана в ОП. Число обращений к ВП равно ТР. Корректировка записи Сначала необходимо найти нужную запись (смотри операцию «поиск»). После окончания операции «поиск» в ОП найденная логическая запись корректируется, формируется физическая запись (блок) и заносится во внешнюю память по тому адресу, откуда она была считана. Число обращений к ВП равно ТР+1. Удаление записи Аналогична операции корректировки. Служебное поле соответствующей логической записи помечается как «удаленная запись». Число обращений к ВП равно ТР+1. Добавление записи Рассмотрим два случая. В первом случае пользователь вводит новую логическую запись в конец таблицы. Тогда вводимая логическая запись добавляется в конец файла. Она заносится либо в последнюю физическую запись (если в ней меньше k логических записей – блок неполон), для чего эта запись должна быть считана в ОП, или формируется новая физическая запись, которая заносится в конец файла. Число обращений к ВП равно соответственно либо 2, либо 1.
Во втором случае пользователь вводит новую логическую запись в указываемую им i-ю строку таблицы (i=1, 2, …, n). В этом случае читается физическая запись с номером Если физические записи с номерами В лучшем случае (i = N) ни один блок не сдвигается. В худшем случае (i = 1) сдвигаются все блоки. Среднее число обращений к ВП для перезаписи блоков (чтение + запись) составит 2 Заметим, что если записи упорядочены по значениям ключа может производиться дихотомическим методом и число обращений к внешней памяти будет пропорционально не (1+
9.4.2. Размещение физических записей в виде списковой структуры Основная проблема в использовании изложенного в п. 9.4.1 способа организации записей состоит в отображении добавления логической записи в произвольное место таблицы. При этом приходится переписывать в памяти (сдвигать на одну позицию) физические записи, соответствующие логическим записям таблицы, расположенным ниже места вставки добавляемой строки. Соответствующую проблему можно устранить, используя для представления физических записей связный список (рис. 9.4.). Рис. 9.4. Список физических записей
Кроме этого списка в ВП формируется список свободных элементов («пустых» физических записей), элементы которого используются при вводе новой записи с данными (рис. 9.5). Напомним, что каждая физическая запись состоит, как и ранее, из k логических записей. Рис. 9.5. Список свободных элементов
Рассмотрим, как реализуются основные элементарные операции модели данных в этой структуре хранения.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|