Виды ЗУ

С точки зрения поиска данных большинство известных запоминающих устройств можно отнести к одному из трех видов: последовательные, адресные и ассоциативные.

Последовательные ЗУ при каждом считывании предоставляют во внешнюю среду очередную запись таблицы или файла. Чтобы получить в распоряжение некоторую i-ю запись таблицы, нужно прежде произвести считывание предыдущих (i-1) записей. Последовательный доступ к данным реализуют такие технические устройства, как накопитель на магнитной ленте, автомат магазинной памяти и т.п.

Адресные ЗУ при каждом считывании предоставляют запись, находящуюся в ячейке, адрес которой указан на входе устройства. Чтобы получить некоторую i-ю запись таблицы, нужно на входе ЗУ указать адрес (номер) ячейки, в которой размещена эта запись. На рис. 2.1 представлена схема адресного ЗУ.

Рис.2.2

Схема адресного ЗУ

Адресное ЗУ состоит из двух частей: дешифратора адреса и матрицы ЗУ. Записи хранятся в строках матрицы ЗУ. Двоичный код адреса записи поступает на вход дешифратора адреса, который преобразует его в унитарный код с числом разрядов, равным количеству строк в матрице ЗУ. Логическая единица появляется на выходе дешифратора, номер которого соответствует двоичному коду адреса. Под действием сигнала логической единицы содержимое соответствующей строки матрицы ЗУ выводится на выход устройства. В качестве адресных ЗУ выступают такие технические устройства, как оперативное и постоянные запоминающие устройства ЭВМ, накопители на магнитных, оптических дисках и т.п.

Ассоциативные ЗУ при каждом считывании выдают на выходе запись, содержимое определенного поля которой совпадает со значением ключевого слова, поданного на вход устройства. Чтобы получить в распоряжение i-ю запись таблицы, нужно на вход ЗУ подать кодовое слово, соответствующее ключевому слову i-й записи. На рис. 2.2 приведена схема ассоциативного ЗУ.

Рис.2.2

Схема ассоциативного ЗУ

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

Из запоминающих устройств всех видов ассоциативные ЗУ непосредственно решают задачу поиска: подавая на вход ассоциативного ЗУ аргумент поиска, на выходе сразу получаем запись, ключ которой совпадает с аргументом. Однако ассоциативные ЗУ являются также наиболее дорогими и сложными технически, поэтому в настоящее время задачи поиска обычно приходится решать на основе адресного или последовательного ЗУ.

Адресное ЗУ позволяет легко получить запись, зная ее порядковый номер в таблице. Следовательно, чтобы решить задачу поиска, нужно от аргумента поиска перейти к номеру записи в таблице. Для этого перехода требуется осуществить либо некоторую процедуру преобразования аргумента в адрес, либо некоторую процедуру проверки содержимого последовательности записей. В последовательных ЗУ поиск строится на основе просмотра содержимого записей.

Далее будут рассмотрены методы поиска, ориентированные, в основном, на адресные ЗУ. При этом, отвлекаясь от конкретных способов задания адресов в различных ЭВМ и системах программирования, будем считать, что имеется возможность получить значение ключа записи по ее номеру в файле или таблице.

Методы поиска можно разделить на два класса:

поиск, основанный на преобразовании аргумента в адрес;

поиск, основанный на сравнении ключей.

Рассмотрим оба этих класса.