Тема №17

17 ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ БАЗ ДАННЫХ

17.1 Устройства для хранения баз данных

Современные базы данных имеют объемы, измеряемые в терабайтах (1 Тб = 1024 Гб) и даже петабайтах (1 Пб = = 1024 Тб). Для их хранения используются устройства внешней памяти большого объема.

Жесткие диски (винчестеры) применяются для хранения и использования информации баз данных. Из всех устройств хранения данных, не считая оперативную память, они обеспечивают наиболее быстрый доступ к данным, высокие скорости чтения и записи данных, поэтому применяются не только для хранения базы данных, но и для ее использования (работы с информацией базы данных), так как обеспечивают быстрое выполнение запросов к базе.

RАID-массивы (Redundant Arrays of Inexpensive Disks) представляют собой объединения нескольких жестких дисков в одно логическое устройство с целью увеличения общей емкости, быстродействия и надежности.

Надежность хранения у RAID-массивов достигается тем, часть дисков используется для записи и хранения дублирующей информации, что обеспечивает восстановление данных при выходе из строя одного, а в некоторых случаях сразу нескольких дисков. Повышение быстродействия достигается за счет того, что современные интерфейсы, позволяют осуществлять операции записи - чтения одновременно на несколько дисков.

Особый интерес представляют в настоящее время внешние RАID -массивы на дисках с интерфейсами IDE или SAТА, позволяющие создавать высокоскоростные дисковые массивы любой необходимой емкости. У них две основные области применения — хранение и использование баз данных объемом от 2 терабайт и более, а также компьютерная обработка цифрового кино- и видеоматериала.

CD-ROM — это один из видов оптических накопителей информации, при работе которых используется лазерная технология. Он представляет собой компакт-диск, предназначенный только для чтения предварительно записанной на него информации с помощью соответствующего устройства — привода. Доступ к данным на CD-ROM осуществляется быстрее, чем к данным на дискетах, но медленнее, чем на жестких дисках.

CD-ROM диски имеют небольшой размер, надежны, долговечны. Они используются для хранения баз данных объемом до 800 Мб.

DVD-диски — универсальные цифровые диски (Digital Versatile Disk). Имея те же габариты, что обычный компакт-диск, и весьма похожий принцип работы, они вмещают чрезвычайно много информации — от 4,7 до 17 Гб. В настоящее время DVD-диски применяются лишь в двух областях — для хранения сверхбольших баз данных и видеофильмов.

В отличие от CD-ROM информация на DVD-диски может записываться с обеих сторон. Более того, с каждой стороны могут быть нанесены один или два слоя информации. Односторонние однослойные диски имеют объем 4,7 Гб (DVD-5), двусторонние однослойные — 9,4 Гб (DVD-10), односторонние двуслойные — 8,5 Гб (DVD-9), двусторонние двуслойные — 17 Гб (DVD-18). В зависимости от объема требующих хранения данных и выбирается тип DVD-диска.

В настоящее время высокотехнологическими компаниями продвигается новый формат DVD-диска — Blu-Ray-диск, у которого для записи и воспроизведения используется не красный лазер, как у DVD и CD-ROM, а синий. У синего лазера длина волны значительно меньше и толщину дорожки данных можно сделать тоньше, что приводит к значительному увеличению емкости носителя. Первые прототипы 100 Гб и 200 Гб дисков уже созданы. У Blu-Ray-дисков высокая скорость обмена данными с основными устройствами компьютера, что при огромных объемах носителя весьма актуально. Это открывает перспективы их применения не только для хранения сверхбольших баз данных, но и для их использования.

Оптические библиотеки — это новое поколение устройств для хранения больших объемов данных. С их помощью можно организовать динамичный доступ к информации баз данных объемом от нескольких десятков гигабайт до пяти-шести терабайт. В этих устройствах может быть объединено более десяти приводов для чтения с CD-ROM и DVD-ROM, а также установлено свыше 500 компакт-дисков. В состав оптических библиотек входит специальная аппаратура для быстрой смены компакт-дисков.

Если же применяются носители, на которые информация перезаписывается, то оптические библиотеки становятся пригодными и для использования баз данных.

Оптическая библиотека, в которой объединены DVD-диски, называется роботизированной DVD-библиотекой. Она представляет собой массив из сотен дисков DVD-R или DVD-RAM, размещенных в отдельном корпусе. Внутри корпуса роботизированной библиотеки кроме самих носителей расположены и приводы, обеспечивающие запись и считывание информации, а также сам механизм робота. При обращении к файлу робот извлекает диск из слота, где он хранится, и вставляет в первый свободный привод. Далее производится работа с носителем по чтению или записи.

Роботизированные библиотеки имеют модульную конструкцию, что дает возможность подключения дополнительных дисков, хранящихся вне корпуса в специальных магазинах. Благодаря этому их емкость можно увеличить от единиц до десятков терабайт. Пример роботизированной DVD-библиотеки — Kubota SA-2100.

Таблица 17.1 –Характеристики роботизированной библиотеки Kubota SA-2100

Характеристика | Базовый модуль | С тремя модулями расширения
Модель | SA507 | SA2139
Емкость | 4,7 Тб | 20,0 Тб
Количество DVD-дисков | 507 | 2139
Размер (ширина х длина х высота), мм | 705x705x1800 | 1210x1210x1800

Для резервного копирования информации баз данных используются стримеры и магнитооптические диски.

Стримеры представляют собой мини-кассеты с магнитной лентой емкостью от 40 Мб до 13 Гб.

Магнитооптические диски построены на совмещении магнитного и оптического принципа хранения информации. Запись информации производится при помощи луча лазера и магнитного поля, а считывание — при помощи только одного лазера. Применение магнитооптических дисков также целесообразно при работе с персональными базами данных больших объемов.

17.2 Физический доступ к базе данных

Вопросы физической организации базы данных интересуют в первую очередь технических специалистов. Пользователи не должны заниматься деталями ее физического устройства, но им важно знать проблемы физической реализации базы данных и способы их решения, так как они влияют на быстродействие базы. Показателем быстродействия является время отклика — промежуток времени между обращением пользователя к базе данных и получением результата. Большое время отклика не устраивает пользователя. Эффективная физическая организация базы данных обеспечивает манипулирование данными (обновление существующих, удаление устаревших, добавление новых данных) и извлечение данных из базы за максимально короткое время.

Процесс физического доступа к базе данных представлен на рисунке 17.1.

Рисунок 17.1 – Физический доступ к БД

Пользователь взаимодействует с базой данных, вводя команды.

Программный компонент СУБД, называемый стратегическим селектором, преобразует команду в форму, эффективную для выполнения.

Преобразованная команда активизирует программный компонент СУБД — буферный диспетчер, который контролирует перемещение данных между диском и оперативной памятью.

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

Диспетчер файлов взаимодействует с диспетчером дисков – частью операционной системы, с помощью которой выполняются все дисковые операции ввода-вывода.

Диспетчер дисков обращается к диску, на котором расположена база данных.

База данных на диске представляет собой множество наборов, состоящих из страниц строго фиксированного размера. Каждый набор страниц имеет уникальный номер. Наборы не имеют общих страниц. Один из наборов содержит все имеющиеся свободные страницы, не используемые для размещения данных. Этот набор называют еще свободным пространством на диске.

Каждая страница внутри набора имеет уникальный, номер и содержит не более 255 записей. Схематичное изображение постраничной организации базы данных приведено на рисунке 17.2.

Рисунок 17.2 – Постраничная организация БД

В физической записи хранится одна строка реляционной таблицы. Как правило, на одной странице хранятся записи только одной таблицы, но не исключается хранение записей из нескольких таблиц. Это позволяет сократить число обращений к диску, если возникает необходимость соединения записей при выполнении запроса.

Каждая запись имеет уникальный в пределах страницы номер, который состоит из двух частей: номера страницы, на которой эта запись находится, и информации о смещении записи от конца страницы. При такой организации хранения данных упорядочение записей на страницах происходит не путем их физического перемещения, а посредством корректировки информации о смещении записи от конца страницы.

При размещении записей на страницах используется принцип кластеризации — возможность как можно более близко физически размещать логически связанные и часто используемые записи. Это важное условие высокой производительности базы данных.

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

В зависимости от запроса со стороны СУБД диспетчер файлов кроме извлечения записи может также:

• заменить запись в файле;

• добавить новую запись в файл;

• удалить запись из файла;

• создать новый файл;

• удалить файл.

В зависимости от запроса со стороны диспетчера файлов диспетчер дисков кроме извлечения страницы может также:

• заменить страницу в наборе страниц;

• добавить страницу в набор страниц;

• удалить страницу из набора страниц.

Таким образом, для СУБД база данных — это множество записей, просматриваемых диспетчером файлов. Для диспетчера файлов база данных — это набор страниц, просматриваемых диспетчером дисков, а диспетчер дисков уже непосредственно работает с устройствами хранения данных.

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

17.3 Управление страницами

Рассмотрим один из способов управления страницами.

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

Пусть на одной странице размещается только одна запись.

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

Если надо добавить запись в набор Х, то диспетчер файлов вставляет запись на пустую страницу, предоставленную диспетчером дисков, а тот добавляет страницу с записью к набору страниц X.

После выполнения нескольких таких действий не гарантировано, что логически близкие страницы будут и физически близко располагаться. И если стоит задача логически упорядочить записи согласно ключевому полю, то логическая последовательность страниц в наборе задается не на основе физически близкого размещения на устройстве хранения данных, а с помощью указателей. Для этого каждая страница, за исключением страницы с номером «ноль», имеет заголовок, в котором содержится указатель — информация о физическом адресе страницы, логически следующей за данной страницей. На странице с номером «ноль» перечисляются все наборы страниц на устройстве хранения данных вместе с указателями на первую страницу каждого набора.

Указатели обрабатываются диспетчером дисков и скрыты от диспетчера файлов. Диспетчер дисков скрывает от диспетчера файлов особенности физической организации ввода-вывода и дает ему возможность вести работу только на логическом уровне. Эта функция диспетчера дисков называется управлением страницами. Точно так же диспетчер файлов скрывает от СУБД операции ввода-вывода на основе страниц и дает ей возможность вести работу только с записями и файлами. Такая функция диспетчера файлов называется управлением записями.

Пусть на одной странице размещаются несколько записей.

При вставке новой записи в набор X диспетчер файлов сохранит ее на той же странице на свободном пространстве за последней сохраненной записью.

При удалении записи из набора X диспетчер файлов перемещает записи к началу страницы.

Логическая последовательность записей ни странице может соответствовать физической последовательности их внутри страницы. Для достижения соответствия диспетчер файлов размещает все записи вверху страницы, оставляя свободное пространство внизу ее. Если потребуется вставить новую запись на страницу, то диспетчер файлов разместит се соответственно уникальному номеру записи.

Длина записи может превысить размер страницы. Тогда такая запись размещается на странице переполнения. При переполнении данной страницы запись перемещается на новую страницу переполнения. Однако существуют более совершенные способы упорядочения записей — индексирование и хеширование.

17.4 Индексирование и xeширование

Для ускоренного доступа к данным БД по запросам пользователей используются индексирование и хеширование. Вначале рассмотрим суть индексирования.

Пусть в базе данных содержатся сведения о продажах автомобилей в таблице ПРОДАЖИ с полями НПП, AВTO, ФИО, ОБ, как в таблице 17.2.

Таблица 17.2 – Продажи автомобилей

№ п/п (НПП) | Марка автомобиля (АВТО) | Ф.И.О. менеджера (ФИО) | Объем продаж (ОБ)
1 | Волга | Гиль А.Б. | 4
2 | Жигули | Брель Б.В. | 5
3 | Москвич | Смаль В.Г. | 4
4 | Волга | Друздь Г.Д. | 3

Данные этой таблицы хранятся в файле ПРОДАЖИ. Предполагается, что пользователи будут составлять запросы на поиск менеджеров, продавших тот или иной автомобиль.

При необходимости поиска менеджеров, продавших, например, Волгу, нужно просмотреть весь файл ПРОДАЖИ и найти все записи, у которых марка автомобиля — «Волга».

Возможен и другой подход. Создается файл АВТОМОБИЛИ с расположением в нем марок автомобилей в алфавитном порядке (см. рисунок 17.3).

Рисунок 17.3 – Расположение записей файла АВТОМОБИЛИ

В этом файле просматриваются записи со значением поля АВТО «Волга» и соответственно указателю номера записи в файле ПРОДАЖИ извлекаются записи об искомых менеджерах.

Если доля менеджеров, продавших «Волгу», в общем количестве менеджеров невелика, то второй подход более эффективен. Во-первых, просмотр файла АВТОМОБИЛИ будет прекращен раньше — после извлечения записи о марке автомобиля, следующей за маркой «Волга». Во-вторых, физический размер записей файла АВТОМОБИЛИ меньше и для их просмотра потребуется меньше времени.

Файл АВТОМОБИЛИ называют индексным файлом, поле АВТО — индексом, а файл ПРОДАЖИ — индексированным.

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

Индексный файл — это файл, в котором хранится информация об индексе.

Записи в нем состоят из двух значений:

1) данного из индексированного файла;

2) указателя номера записи индексированного файла, в котором хранится информация об этом данном.

Если индексирование организовано на основе ключевого поля, например, на основе поля SN файла успеваемости, то индекс называется первичным. А если индекс организован на основе другого поля, например, поля PN, то он называется вторичным. Вторичные индексы могут создаваться как в процессе создания самой базы данных, так и позднее в процессе работы с ней. Вторичным индексам присваиваются имена — идентификаторы, по которым их можно использовать.

Кроме того, индекс, организованный на основе ключевого поля или другого ключа, называется уникальным.

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

Индексы можно использовать двумя разными способами:

■ для последовательного доступа к индексированному файлу, т. е. в последовательности, заданной значениями индексного поля.;

■ индексы могут использоваться и для прямого доступа к отдельным записям индексированного файла на основе заданного значения индексного поля, как это было сделано в приведенном примере.

Хранимый файл может иметь несколько индексов: например, хранимый файл успеваемости может иметь индекс PN и индекс OCENKA (см. рисунок 17.4).

Рисунок 17.4 – Индексирование таблицы оценок по двум полям

Индексы могут использоваться как раздельно, так и совместно для более эффективного доступа к данным об успеваемости, например, при запросе на поиск студентов, сдавших физику с оценкой 5.

Тогда согласно индексу PN для студентов будут найдены записи с идентификационными указателями 3412 и 3414, а согласно индексу OCENKA - записи с указателями 3412 и 3415. Понятно, что на основе сравнения этих двух наборов записей условиям запроса удовлетворяет только запись с данными о студенте 3412 и только после этого в СУБД будет организован доступ к файлу успеваемости и будет извлечена данная запись.

Часто индекс создают на основе комбинации двух или более полей. Например, на рисунке 17.5 показана схема индексирования файла успеваемости на основе комбинации полей PN и OCENKA. При такой организации индексов в СУБД можно выполнить запрос на поиск студентов, сдавших физику на 5 на основе однократного просмотра с помощью одного индекса, в то время как при использовании пары индексов требуется два отдельных просмотра, тем более, что скорость выполнения запроса может сильно зависеть от последовательности выполнения отдельных просмотров по индексам.

Рисунок 17.5 – Индексирование таблицы оценок по комбинации двух полей PN и OCENKA

Таким образом, цель использования индексирования — это ускорение извлечения данных за счет уменьшения количества дисковых операций ввода-вывода.

Другим распространенным способом упорядочивания записей и доступа к данным является хеширование – технология быстрого прямого доступа к записи базы данных на основе заданного значения некоторого поля записи, как правило, ключевого, к

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

Данный метод требует заранее резервировать место на диске для размещения файла базы данных (это является его недостатком).

Предположим, что необходимо записать 500 записей. Длина записи — 100 байтов, а длина блока ни диске 2000 байтов. Потребуется ровно 25 блоков, но обычно объем увеличивают, например, на 20 %, тогда будет зарезервировано 30 блоков (от 0-го до 29-го), т.е. создается область переполнения файла базы данных, необходимая для решении проблемы конфликтов, возникающих в случае вычисления по хеш-функции одного и того же адреса для нескольких записей.

Показателями эффективной стратегии прямого доступа к записям служат малое время поиска и малое число конфликтов. Лучше всего это достигается, если используется алгоритм хеширования, равномерно распределяющий записи по области записи.

Наилучший метод достижения равномерности состоит в использовании хеш-функции, которая определяет адрес хранения записи на основе остатка от деления значений ключа на размер файла в блоках. В этом случае записи файла базы данных упорядочиваются по значениям ключевого поля. Пусть первая запись имеет значение ключа 1532. Тогда остаток от его деления на количество блоков 30 равен 2. Этот остаток есть относительный адрес записи.

Пусть начальный адрес памяти для нулевого блока есть 4048. Тогда запись со значением ключа 1532 будет помещена диспетчером файлов в блок по абсолютному адресу 4050 (4048 + 2).

Взятие остатка гарантирует, что вычисленный относительный адрес для каждой из 500 записей будет находиться в промежутке от 0 до 29. Записи помещаются в один из этих блоков, т.е. происходит свертка значений ключа, разбросанных по домену, с целью эффективного использования дисковой памяти.

Так как в каждом блоке могут храниться несколько записей, то записи продолжают размещаться в блоке до тех пор, пока он не заполнится. Представим, что в процессе заполнения блока встретилась запись со значением ключа 1562. Для нее остаток от деления тоже равен 2. Возникает конфликт, так как вычисленный хеш-адрес уже занят.

Известны два способа решения проблемы конфликтов. В первом случае запись, для которой вычисленный хеш-адрес занят, помещается в область переполнения файла базы данных. Во втором случае запись, вступившая в конфликт, помещается в некоторое свободное место файла, начиная от текущей занятой позиции.

Если извлекается нужная запись по заданному значению ключевого поля, то СУБД вначале вычисляет хеш-адрес, а затем диспетчер файлов посылает запрос на извлечение записи по вычисленному адресу.

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