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

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

54
Для хранения таблиц в памяти ЭВМ используются последовательное и
связанное представления данных.
При последовательном представлении таблица хранится в виде после-
довательного списка в заранее зарезервированном блоке памяти. Такие таблицы
легко составлять и дополнять, однако время поиска записей в них – велико. Для
поиска нужной записи необходим последовательный просмотр всех записей с
анализом ключей. Просмотр осуществляется до тех пор, пока не будет найдена
нужная запись или после просмотра всей таблицы не будет выработан сигнал
отсутствия нужной записи.
Обычно записи таблицы упорядочивают по какому-либо принципу (на-
пример, по возрастанию значения ключа или по частоте обращения к записям) и
хранят в виде упорядоченного последовательного
списка. В этом случае поиск
может быть ускорен за счет использования специальных методов. Однако веде-
ние упорядоченного последовательного списка усложняется и требует дополни-
тельных процедур по упорядочиванию при включении новых записей. Так, для
включения в упорядоченный последовательный список новой табличной записи
необходимо вначале определить место новой записи в соответствии со
значени-
ем ее ключа. Затем соответствующая ячейка памяти должна быть освобождена,
в нее заносится новая запись, а все последующие передвигаются на одну ячей-
ку, т.е. часть массива перезаписывается. Эти процедуры влекут дополнительные
затраты времени на перезапись массива.
На рис. 4.9 приведен пример включения новой записи при последова-
тельном представлении таблицы, в
которой упорядочение записей произведено
по алфавиту ключевых слов.
Для включения в таблицу новой записи D ее в соответствии со значени-
ем ключа необходимо разместить вслед за записью С в ячейке с адресом 104.
Ячейка 104 освобождается, в нее заносится новая запись D, а все последующие
записи смещаются на одну ячейку в сторону
бóльших адресов.
Исходная таблица Таблица с включенной
новой записью D
101 Запись A 101 Запись A
102 Запись B 102 Запись B
103 Запись C 103 Запись C
104 Запись F 104 Запись D
… … 105 Запись F
100+N Запись N … …

Страницы