Перейти в начало сайта Перейти в начало сайта
Электронная библиотека «Наука и техника»
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-ускоритель (видеопроцессор).

 

Об авторе:

Денисенко Роман Александрович, аспирант ГосНИИ АС
e-mail: r214@chat.ru

Источники информации:

  1. Учебное пособие «Введение в Oracle: SQL, SQL*Plus, и PL/Plus».
  2. Кохонен Т. «Ассоциативные запоминающие устройства». Москва, «Мир», 1982 г.

Дата публикации:

27 октября 2001 года

Электронная версия:

© НиТ. Препринт, 1997

В начало сайта | Книги | Статьи | Журналы | Нобелевские лауреаты | Издания НиТ | Подписка
Карта сайта | Cовместные проекты | Журнал «Сумбур» | Игумен Валериан | Техническая библиотека
© МОО «Наука и техника», 1997...2017
Об организацииАудиторияСвязаться с намиРазместить рекламуПравовая информация
Яндекс цитирования
Яндекс.Метрика