| N-T.ru / Текущие публикации / Техника сегодня |
Нужна ли ассоциативная память?Мир захлестнула волна информации. Главное при работе с ней – быстрый поиск с последующей выборкой. Информация хранится в базах данных, и базы данных стоят сейчас почти на каждом компьютере. Обычно базы состоят из таблиц. Рассмотрим типичную структуру таблицы в реляционной базе данных. Все поля, входящие в таблицу, можно разбить на три группы: системные поля, поля наименования, и поля данных. Системные поля – это ключи. В них входят первичный ключ (счетчик) для связи с подчиненными таблицами и вторичные ключи для связи с главными таблицами (если данная таблица является подчиненной). Поля наименования – это те поля, по которым пользователь может идентифицировать описанный в таблице объект в ряду себе подобных. Для предотвращения дублирования записей (т.е. появления «двойников») необходимо обеспечивать уникальность записей. Типы полей – строковые, реже – числовые или дата/время. Поля данных – в них хранятся данные об объекте. Это поля типа числовые, денежные, дата/время, и т.д. При работе с таблицей одна из главных задач – выборка, причем в большинстве случаев выборка осуществляется по параметру (то есть из таблицы выбираются только те записи, которые соответствуют некоторому условию). Существуют два подхода к выборке: сверху, со стороны пользователей, и снизу, со стороны аппаратного обеспечения («железа»). При подходе сверху главный определяющий фактор – удобство пользователя. Существует много способов доступа к данным в таблицах, но наибольшее распространение получил язык SQL. Фактически SQL фактически стал индустриальным стандартом для реляционных баз данных. Американский Институт Национальных Стандартов (ANSI) в 1986 году объявил язык SQL стандартом для реляционных баз данных. То же самое сделала и Международная Организация по стандартам (ISO). Все основные реляционные системы управления баз данных поддерживают в том или ином виде язык SQL, и большинство разработчиков реляционных систем управления базами данных стремятся следовать стандарту ANSI [1, глава 2, стр. 4]. Конструкторы SQL встроены в настольные СУБД (ACCESS, Delphi), серверные приложения работают в основном с SQL (ORACLE, SQL server). В команде SQL указывается сама команда (действие, которое надо совершить), область выборки (таблицы, из которых необходимо произвести выборку), данные, которые должны быть выданы (список полей), условия связи между таблицами и условия отбора, то есть по команде SQL фактически осуществляется ассоциативная выборка из базы данных. При подходе снизу главный определяющий фактор – архитектура компьютера. В настоящее время компьютеры имеют адресную структуру памяти и приспособлены для операций «мало данных – много команд», а при работе с данными (при выборке) чаще всего происходят операции типа «много данных – мало команд» Произошедшее за последнее время бурное развитие компьютерной техники не только не решило, а скорее усугубило эту проблему. Производительность процессоров увеличилось во много раз, увеличилась емкость винчестеров и размер оперативной памяти. Но при этом производительность канала память – процессор увеличилась сравнительно медленно, и является в данный момент камнем преткновения. Применение аппаратных средств ускорения (кэширования) тоже не очень эффективно из-за больших объемов данных. Для того, чтобы получить доступ к нужной записи в таблице необходимо либо перебирать все записи (для этого потребуется N циклов, N – число записей в таблице), либо найти адрес записи (так как память компьютера имеет адресную архитектуру). Для ускорения поиска прилагаются большие усилия: применяют сортировки (то есть записи упорядочивают в определенном порядке), индексирование, и хеширование (адрес записи – некоторая функция от значения аргумента записи). Рассмотрим подробнее все эти способы. Сортировки. При дихотомическом поиске в упорядоченном массиве количество циклов поиска – log2N, где N – число записей в таблице. Но сортировки производят только по одному полю. После совершения любого действия над записями (добавления, изменения, удаления) приходится производить упорядочивание (пересортировку) таблицы, а число перестановок возрастает в геометрической прогрессии при увеличении количества записей. Индексирование. Индексы – это специальные конструкции, которые позволяют быстро найти адрес нужной записи и в настоящее время они широко применяются на практике. На одну таблицу можно создавать несколько индексов. В качестве примера можно рассмотреть рекомендации по применению индексов в ORACLE [1, глава 18, стр. 14]. Они сводятся к следующему: рекомендуется использовать индексы для обеспечения уникальности записей; для ускорения выборки данных; задавать индексы для тех полей, выборку по которым производится чаще всего, и при этом рекомендуется задавать на таблицу не более 3 индексов, что очень мало. На практике применяют индексы следующим образом: в системных полях таблиц используют 1...2 индекса, и еще один индекс – на поля наименования. Область данных почти никогда не индексируют, хотя отбор чаще всего происходит именно по этим полям [1, глава 2, стр. 22...33, глава 3, стр. 3]. Кроме того, на обновление индексов также требует времени, а сами индексы занимают место на диске (а иногда размер индексов превышает размер основной таблицы). Поэтому индексация таблиц не очень помогает: индексы занимают место (а иногда могут превышать размеры таблиц), а в случае отбора по неиндексированному полю они не помогают. Хеширование. При хешировании записей под таблицу сразу выделяют с запасом некоторый объем памяти, и адрес записи в этом объеме – некоторая функция от содержимого одного из полей записи (хеш-функция). Хеширование также проводят по одному полю. Недостатки этого способа: необходимость в избыточном резервировании памяти. Кроме этого, даже при достаточно большом выделенном объеме памяти возможна ситуация, при котором на некоторое место претендуют сразу две или более записей, то есть возникает коллизия. Выводы: проблема быстрого доступа к данным на машинах с адресной памятью до сих пор не решена. При работе с адресной памятью трудно добиться существенного повышения скорости доступа на аппаратном уровне, так как при обращении к памяти всегда необходимо указывать адрес данных, и за один цикл можно обратиться только к одной ячейке памяти [2, стр. 152]. В настоящее время большая тяжесть ускорения доступа ложится на программное обеспечение, которое фактически создает виртуальную ассоциативную память на машинах с адресной памятью, что не очень эффективно. Существенно повысить скорость доступа к данным можно если включить в состав компьютера память с адресацией по содержанию (ассоциативной памяти). Применение ассоциативной памяти позволяет существенно повысить скорость выборки и упростить доступ к данным. Так как при выборке происходит ряд логических операций по отбору данных, то отпадает необходимость в специальных программных конструкциях по ускорению доступа: сортировках и хешировании, а индексы потребуются только для обеспечения уникальности записей и задания связей между таблицами. Уже создан ряд микросхем ассоциативной памяти, их применение позволяет существенно повысить производительность. Так как устройство с ассоциативной памятью предназначено для повышения скорости доступа при работе с базами данных, то наиболее целесообразно выполнить его в виде отдельной платы расширения для компьютера. Впоследствии на основании этой платы может быть создан сопроцессор данных (SQL-сопроцессор). Использование специальных аппаратных средств для повышения производительности компьютера при выполнении узко специализированных задач – достаточно традиционный подход к решению проблемы. Если вспомнить историю, то в начале 80-х годов для ускорения расчетов был создан математический сопроцессор, а в середине 90-х для ускорения вывода графики – 3D-ускоритель (видеопроцессор).
Об авторе: Денисенко Роман Александрович, аспирант ГосНИИ АС Источники информации:
|
|
Дата публикации: 27 октября 2001 года |
|