Перейти в начало сайта Перейти в начало сайта
Электронная библиотека «Наука и техника»
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
Об организацииАудиторияСвязаться с намиРазместить рекламуПравовая информация
Яндекс цитирования
Яндекс.Метрика