Cтраница 2
Запоминающее устройство имеет емкость 10 000 записей. В нем должен быть размещен файл из 9000 записей с использованием алгоритма перемешивания. Под область переполнения выделена память емкостью 1000 записей ( всего записей 10 000), и вместимость участка записей выбрана равной 20 записям. [16]
Программная ассоциативная память по сравнению со своим аппаратным аналогом работает медленнее, лишена изящества и больше подвержена ошибкам, но ее внедрение обходится намного дешевле. Если производители оборудования обеспечивают лишь обычную память, то ассоциативности можно достичь с помощью организации подходящих структур данных, например с использованием алгоритмов перемешивания и колец. [17]
Запись, направленная алгоритмом перемешивания в полностью заполненный участок основной области, помещается в свободный участок области переполнения. Адрес этого участка запоминается в исходном участке основной области. Если алгоритм перемешивания направляет еще одну запись в тот же участок основной области, то она помещается в какой-нибудь другой участок области переполнения. [18]
Определенное число областей адресуемого пространства памяти, которое может быть доступно за одно обращение к внешнему запоминающему устройству, называется первичным участком записей. Такой участок может содержать одну или несколько записей. Выбирая размер участка и зная длину записи, системный аналитик может определить число записей, помещающихся на одном участке. Как показано на рис. 19.5, алгоритм перемешивания направляет записи в первичные участки подобно тому, как колесо рулетки направляет шарики в гнезда. [19]
Однако при использовании методов перемешивания возникает следующая проблема. Цепочка символов, образующая ключ записи, обычно позволяет строить гораздо больше записей с различными ключами, чем их может быть на самом деле. Поэтому отображение множества ключей в множество адресов необязательно взаимно-однозначно, а это означает, что имеются классы эквивалентности ключевых слов, известные как классы коллизий. Поскольку заранее неизвестно, какое из возможных ключевых слов будет использовано, а какое - нет, невозможно оптимизировать алгоритм перемешивания, чтобы сделать минимальной частоту возникновения коллизий и размеры классов коллизий. Считается, что, чем равномернее распределены полученные адреса, тем лучше алгоритм перемешивания. Следовательно, в этом случае оценка алгоритма перемешивания может быть выполнена только эмпирическим путем обычно на основе тщательно проведенного моделирования. Некоторые из этих часто используемых методов кратко рассмотрены ниже. [20]
Правда, при таком сочетании теряется основное достоинство перемешивания - поиск записи за одно обращение к внешней памяти. Однако перемешивание в сочетании с обычным индексированием может оказаться предпочтительней одного только перемешивания, поскольку в первом случае записи могут храниться в порядке, который диктуется определенными соображениями. Например, записи могут храниться последовательно по значению первичного ключа или по соседству с исходными записями в древовидной структуре; часто используемые записи могут размещаться на устройствах ( или частях устройств) с наименьшим временем доступа. Кроме того, незаполненные места на участках записей ( недостаток алгоритма перемешивания) теперь находятся в индексе, а не в файле данных. Таким образом, индексирование в сочетании с перемешиванием более экономично с точки зрения использования памяти, чем адресация записей с помощью одного только алгоритма перемешивания. Переполнения, неизбежные при перемешивании, проще обрабатывать в индексе, чем в файле данных, где это повлекло бы большие дополнительные расходы времени при поиске. [21]
Однако при использовании методов перемешивания возникает следующая проблема. Цепочка символов, образующая ключ записи, обычно позволяет строить гораздо больше записей с различными ключами, чем их может быть на самом деле. Поэтому отображение множества ключей в множество адресов необязательно взаимно-однозначно, а это означает, что имеются классы эквивалентности ключевых слов, известные как классы коллизий. Поскольку заранее неизвестно, какое из возможных ключевых слов будет использовано, а какое - нет, невозможно оптимизировать алгоритм перемешивания, чтобы сделать минимальной частоту возникновения коллизий и размеры классов коллизий. Считается, что, чем равномернее распределены полученные адреса, тем лучше алгоритм перемешивания. Следовательно, в этом случае оценка алгоритма перемешивания может быть выполнена только эмпирическим путем обычно на основе тщательно проведенного моделирования. Некоторые из этих часто используемых методов кратко рассмотрены ниже. [22]
Однако при использовании методов перемешивания возникает следующая проблема. Цепочка символов, образующая ключ записи, обычно позволяет строить гораздо больше записей с различными ключами, чем их может быть на самом деле. Поэтому отображение множества ключей в множество адресов необязательно взаимно-однозначно, а это означает, что имеются классы эквивалентности ключевых слов, известные как классы коллизий. Поскольку заранее неизвестно, какое из возможных ключевых слов будет использовано, а какое - нет, невозможно оптимизировать алгоритм перемешивания, чтобы сделать минимальной частоту возникновения коллизий и размеры классов коллизий. Считается, что, чем равномернее распределены полученные адреса, тем лучше алгоритм перемешивания. Следовательно, в этом случае оценка алгоритма перемешивания может быть выполнена только эмпирическим путем обычно на основе тщательно проведенного моделирования. Некоторые из этих часто используемых методов кратко рассмотрены ниже. [23]
Правда, при таком сочетании теряется основное достоинство перемешивания - поиск записи за одно обращение к внешней памяти. Однако перемешивание в сочетании с обычным индексированием может оказаться предпочтительней одного только перемешивания, поскольку в первом случае записи могут храниться в порядке, который диктуется определенными соображениями. Например, записи могут храниться последовательно по значению первичного ключа или по соседству с исходными записями в древовидной структуре; часто используемые записи могут размещаться на устройствах ( или частях устройств) с наименьшим временем доступа. Кроме того, незаполненные места на участках записей ( недостаток алгоритма перемешивания) теперь находятся в индексе, а не в файле данных. Таким образом, индексирование в сочетании с перемешиванием более экономично с точки зрения использования памяти, чем адресация записей с помощью одного только алгоритма перемешивания. Переполнения, неизбежные при перемешивании, проще обрабатывать в индексе, чем в файле данных, где это повлекло бы большие дополнительные расходы времени при поиске. [24]