Организация доступа к данным
Реферат
Организация доступа к данным
1. Страницы и файлы
За обработку файлов в операционной системе отвечает программа обслуживания файловой системы (диспетчер файлов) и программа управления дисковой памятью (диспетчер дисков). Запись и считывание данных с диска осуществляется блоками, которые называются страницами и имеют размер в зависимости от операционной системы 2 или 4 килобайта. Каждая страница имеет свой адрес PageID, который указывает на ее местонахождение на внешнем носителе. За обработку страниц отвечает диспетчер дисков. Он же обеспечивает их запись и чтение.
Итак, файл - это набор страниц. Управление файлами выполняет диспетчер файлов. При создании файла он запрашивает у диспетчера дисков необходимое число страниц. Выделенному набору страниц присваивается адрес FileID. Каждой странице внутри него дается некий логический ID, который просто указывает порядковый номер страницы в наборе, а не физическую последовательность записи на диске. Диспетчер файлов обращается к диспетчеру дисков, запрашивая считывание или запись логических страниц, принадлежащих файлу. Как правило, диспетчер дисков ведет каталог, в котором хранятся все FileID и указатели принадлежности к каждому набору страниц.
СУБД взаимодействует с диспетчером файлов операционной системы. При манипулировании логическими элементами данных (отношениями, атрибутами, записями…) СУБД запрашивает данные из определенных файлов. Далее диспетчер файлов преобразует их в запросы страниц из определенного набора. Когда диспетчер файлов передает СУБД полученную от диспетчера дисков страницу, система управления базами данных преобразует полученные данные в логическую форму представления самого нижнего уровня, доступного пользователю базы данных (рис. 1).
На практике не всегда четко распределены функции файловой системы и СУБД. Некоторые операционные системы не предоставляют необходимые для приложений баз данных возможности по управлению файлами. С другой стороны, некоторые СУБД сами обращаются непосредственно к диспетчеру дисков.
Для повышения производительности СУБД надо стремиться к тому, чтобы логически связанные между собой и часто используемые данные размещались на одной странице или в наборе страниц, связанных логическими указателями. Для этого используется технология кластеризации данных. Кластеризация базы данных - это такой метод хранения данных, когда их физическая организация отражает определенный логический порядок. Внутрифайловая кластеризация осуществляется в рамках одного хранимого файла (в теории систем баз данных под файлом подразумевается хранимый набор однотипных записей, т.е. в случае реляционной базы данных - таблица). Например, если часто требуется осуществлять доступ к данным о поставщике согласно его порядковому номеру, то все записи о поставщиках следует физически размещать таким образом, чтобы запись о поставщике П1 была возле записи П2, запись П2 - возле записи П3 и т.д. При межфайловой кластеризации учитываются сразу несколько файлов. Например, если часто требуется осуществлять доступ к данным о поставщике и обо всех его поставках деталей одновременно, то записи о поставщиках и их поставках должны располагаться рядом. Тогда при извлечении страниц, содержащих множество кортежей отношения Поставщик, система будет извлекать и данные необходимых для соединения кортежей отношения Поставки. В каждый момент времени кластеризацию файла или набора файлов можно осуществлять только одним из этих способов.
Внутрифайловую и межфайловую кластеризацию СУБД может осуществлять, размещая логически связанные записи на одной странице (если это возможно) или на смежных страницах. Поэтому СУБД важно иметь сведения не только о сохраненных файлах, но и о страницах. Диспетчер дисков должен обеспечить, чтобы логически близкие страницы были физически близко расположены на диске.
Очевидно, что после выполнения нескольких обычных действий (например, добавление или удаление записей) нельзя гарантировать, что логически близкие страницы будут физически располагаться одна возле другой (диск будет «фрагментирован»). Поэтому логическую последовательность страниц в данном наборе следует задавать с помощью указателей, а не на основе их физически близкого размещения на диске. Для этого каждая страница содержит заголовок с информацией о физическом дисковом адресе той страницы, которая логически следует за данной. Тогда достаточно знать расположение только первой страницы из набора, поскольку положение второй и последующих страниц операционная система определит с помощью указателей в заголовках.
В реальных базах данных на одной странице может размещаться не одна, а несколько хранимых записей и их логическая последовательность для данной страницы может соответствовать физической последовательности, заданной внутри этой страницы. Для этого диспетчер файлов может передвигать отдельные записи вверх или вниз на странице, размещая все записи в верхней части страницы и оставляя свободное пространство в нижней части страницы.
В стандартных СУБД хранимый файл представляет собой набор хранимых записей с указателями, постоянными до тех пор, пока существуют эти записи. Для некоторого хранимого файла всегда можно осуществить последовательный доступ ко всем хранимым записям, где под термином «последовательный доступ» подразумевается доступ согласно последовательности записей внутри страницы и последовательности страниц внутри набора страниц (обычно это порядок возрастания идентификационных номеров записей). Такая последовательность называется физической, хотя она не обязательно соответствует физическому расположению данных на диске.
2. Индексирование
Основное назначение индексов состоит в обеспечении эффективного прямого доступа к кортежу отношения. Индекс - это упорядоченное множество значений, в чем-то подобное предметному указателю в книге (предметный указатель - упорядоченное множество слов с указанием страниц, где встречается это слово). Чтобы отыскать в книге нужное слово, можно сначала найти его в предметном указателе, где хранятся нужные страницы книги. В индексе базы данных перечислены значения некоторого атрибута вместе с указателями страниц, содержащих кортежи, где хранится соответствующее значение.
Рассмотрим в качестве примера таблицу с данными о поставщиках (рис. 2.) и запрос типа «Найти всех поставщиков из города С». На основании этой таблицы может быть создан файл с данными о городах. Файл городов может быть упорядочен по алфавитному перечню их названий, т.е. по ключевому полю ГОРОД, с указателями на соответствующие записи в файле поставщиков.
Поиск всех поставщиков из Минска, например, можно выполнить двумя способами:
. Найти весь файл поставщиков, найти все записи, для которых названием города является строка «Минск»;
. Найти файл городов, найти в нем строку «Минск», а затем согласно указателям извлечь все соответствующие записи из файла поставщиков.
Если доля всех поставщиков из Минска по отношению к общему количеству поставщиков достаточно мала, то второй способ будет гораздо эффективнее первого. СУБД известна физическая последовательность записей в файле городов, но даже если придется просмотреть файл городов полностью, для такого поиска потребуется гораздо меньше операций ввода-вывода, поскольку физический размер файла городов меньше, чем размер файла поставщиков из-за меньшего размера записей.
В рассматриваемом примере файл городов называется индексным файлом или индексом по отношению к файлу поставщиков, а файл поставщиков называется индексированным файлом по отношению к файлу городов. Индексный файл - это хранимый файл особого типа, в котором каждая запись состоит из двух значений, а именно данных и RID-указателя, необходимого для связывания с соответствующей записью индексированного файла.
Существует два способа использования индексов. Во-первых, их можно использовать для последовательного доступа к индексированному файлу, где последовательность задается значениями индексного поля. Например, индекс по полю ГОРОД из рассматриваемого примера будет определять доступ к записям файла поставщиков согласно алфавитному перечню городов (найти поставщиков из городов, начинающихся на буквы К-М). Во-вторых, индексы могут использоваться для прямого доступа к отдельным записям индексированного файла на основе заданного значения индексного поля. Пример запроса «Найти поставщиков из Минска» является типичным примером такого использования индексов.
Хранимый файл может иметь несколько индексов. Например, хранимый файл поставщиков может иметь индекс ГОРОД и индекс СТАТУС. Они могут как раздельно, так и совместно использоваться для более эффективного доступа к записям о поставщиках. Для иллюстрации «совместного» использования индексов рассмотрим запрос «Найти поставщиков из Бреста со статусом 20». Если согласно индексу ГОРОД для поставщиков из Бреста найдены записи с RID-указателями r1 и r5, а согласно индексу СТАТУС - записи с RID-указателями r1 и r4, то условиям запроса удовлетворяет только запись с данными о поставщике c указателем r1. Только после этого в СУБД будет организован доступ к файлу поставщиков и будет извлечена данная запись.
Индексы часто называют инвертированными списками, а файл с индексами по каждому полю называется полностью инвертированным.
Индекс можно также создать на основе комбинации двух или более полей. Например, если проиндексировать файл поставщиков на основе комбинации полей ГОРОД и СТАТУС, то запрос типа «Найти поставщиков из Бреста со статусом 30» можно выполнить на основе однократного просмотра с помощью одного индекса. Причем, комбинированный индекс ГОРОД/СТАТУС может также служить индексом по одному полю ГОРОД, поскольку все записи в комбинированном индексе расположены по крайней мере последовательно.
Значительное ускорение процесса выборки или извлечения данных является основным преимуществом использования индексов, а основным недостатком - замедление процесса обновления данных. Действительно, при каждом добавлении новой записи в индексированный файл потребуется также добавить новый индекс в индексный файл. Поэтому при выборе некоторого поля для индексирования необходимо выяснить, что более важно для данной СУБД: скорость извлечения данных или скорость обновления?
Кроме того, не рекомендуется создавать индексы по всем атрибутам. Обычно индексы создаются для следующих типов атрибутов:
Первичные ключи (ускорение поиска записи);
Внешние ключи (ускорение выполнения соединений);
Атрибуты, часто фигурирующие в запросах, ответами на которые являются небольшие множества записей;
Атрибуты, по которым часто сортируются данные.
До сих пор предполагалось, что для ускорения процесса извлечения данных используются указатели записей (RID-указатели). Но иногда для этого достаточно использовать указатели страниц (т.е. номеров страниц). Конечно, для последующего поиска записи внутри данной страницы придется осуществить еще одну операцию извлечения записи. Однако теперь она будет выполняться в оперативной памяти и для этого не придется увеличивать число дисковых операций ввода-вывода. Если в таблице Поставщики выполнена кластеризация по полю П № и по этому же полю осуществляется индексирование, то нет необходимости хранить в индексном файле указатели для каждой записи индексируемого файла (в данном случае для файла поставщиков). Достаточно иметь указатель для каждой страницы, состоящий из максимального номера поставщика для данной страницы и соответствующего номера страницы. В этом случае процесс извлечения записи для некоторого поставщика будет состоять из помещения в оперативную память соответствующей страницы и очень быстрого поиска нужной хранимой записи.
Такой индекс называется неплотным. Все описанные ранее индексы, наоборот, называются плотными. Одним из преимуществ неплотных индексов является их малый размер по сравнению с плотными индексами. Как правило, это обеспечивает просмотр содержимого базы данных с большей скоростью. Поэтому обычно при индексировании используют оба типа индексов.
Структуры типа Б-дерева
Если индексированный файл имеет большой размер, то и его индекс также велик. Поэтому последовательный просмотр даже одного только индекса требует больших затрат времени. Для разрешения такой проблемы можно рассмотреть индексный файл как обычный хранимый файл и создать для него еще один индекс. Эту операцию можно осуществлять повторно нужное количество раз (обычно она применяется трижды). При этом индекс на каждом из уровней будет неплотным по отношению к нижнему индексируемому уровню. Такой подход к организации индексов бинарного типа (или Б-дерева - B-tree) наиболее популярен в реляционных базах данных. Их использование предусмотрено почти во всех СУБД, а некоторые СУБД работают только на основе индекса бинарного типа.
Индексы бинарного типа являются частным случаем древовидного индекса и состоят из двух частей: набора последовательностей и набора индексов.
Набор последовательностей представляет собой индекс, содержащий указатели на все записи в файле. Этот индекс физически упорядочен, обычно по значению первичного ключа. Это позволяет обращаться к записям последовательно, считывая один за другим адреса записей из последовательного набора и по ним считывая сами записи.
Набор индексов - это неплотный иерархический индекс для последовательного набора.
Бинарные деревья по определению являются сбалансированными, т.е., все записи находятся на одинаковом расстоянии от корневого уровня индексного набора, а справа от корневого значения находится столько же значений, сколько и слева. При изменении индексируемого множества применяется специальный алгоритм, который реорганизует все дерево и сделает его сбалансированным.
3. Хеширование
индексирование хеширование диск
-Каждая хранимая запись базы данных размещается по адресу (RID-указателю или номеру страницы), который вычисляется с помощью специальной хеш-функции на основе значения некоторого поля данной записи, называемого хеш-полем.
-Для сохранения записи в СУБД сначала вычисляется хеш-адрес новой записи, а затем диспетчер файлов помещает эту запись по вычисленному адресу.
-Для извлечения нужной записи по заданному значению хеш-поля в СУБД сначала вычисляется хеш-адрес, а затем диспетчеру файлов посылается запрос для извлечения записи по вычисленному адресу.
В качестве иллюстрации предположим, что у нас есть записи с данными о поставщиках с номерами 100, 200, 300, 400 и 500 (вместо П1, П2, ПЗ, П4, П5 в нашем примере), для хранения каждой из них предназначается отдельная страница, а в качестве хеш-функции используется следующая:
хеш-адрес (т.е. номер страницы или RID-указатель) = остаток от деления на 13 числа, содержащегося в поле П №
Это простейший пример общего класса хеш-функций типа деление / остаток (в качестве делителя следует выбирать простое натуральное число). В этом примере номерами страниц для заданных записей будут 9, 5, 1, 10 и 6 соответственно.
В общем случае, для определения адреса вместо хеш-функции можно было бы использовать непосредственно значение ключевого поля (если это поле имеет числовой тип данных). Однако такой способ нежелателен, поскольку диапазон возможных значений ключевого поля может быть гораздо шире диапазона имеющихся адресов. В нашем примере номера записей с данными о поставщиках находятся в диапазоне 000-500, тогда как в действительности может быть только несколько реальных поставщиков. Таким образом, во избежание неэффективного использования дискового пространства следует найти такую хеш-функцию, чтобы можно было сузить диапазон 000-500, например, до 0-9. Для того чтобы зарезервировать дополнительное пространство (рекомендуется 20% от исходной величины), диапазон 0-9 в нашем примере расширен до 0-12 за счет делителя 13.
В этом примере также наглядно проявляется недостаток хеширования. Физическая последовательность записей внутри хранимого файла почти всегда отличается от последовательности ключевого поля, а также любой другой логически заданной последовательности. К тому же, между последовательно размещенными записями могут быть промежутки неопределенной протяженности, т.к. страницы заполняются неравномерно. Практически всегда физическая последовательность записей в хранимом хешированном файле не имеет ничего общего с заданной в нем логической последовательностью.
Еще одним недостатком хеширования является возможность возникновения коллизий, т.е. ситуаций, когда две или более различных записи имеют одинаковые адреса. Допустим, что файл поставщиков из предыдущего примера (с поставщиками 100, 200 и т.д.) содержит также поставщика с номером 1400. При использовании хеш-функции типа «остаток от деления на 13» возникнет коллизия (по адресу 9) с записью 100. Ясно, что такая хеш-функция неадекватна и для устранения коллизий необходимо ее исправить.
Наиболее часто на практике для разрешения коллизий используется значение хеш-функции в качестве адреса не какой-либо записи с данными, а точки привязки. Точка привязки - это начальный адрес цепочки указателей (цепочки коллизий), связывающей вместе все записи или все страницы с записями, которые имеют одинаковый хеш-адрес. Внутри цепочки коллизий записи также могут быть упорядочены согласно хеш-полю для упрощения последующего поиска.
Еще один недостаток описанного выше способа хеширования - возрастание числа коллизий с увеличением размера хранимого файла. Это, в свою очередь, может привести к значительному увеличению среднего времени доступа, поскольку все больше и больше времени придется тратить на поиск записей в наборах конфликтующих записей. Однако этот недостаток можно устранить, если реорганизовать файл, т.е. выгрузить данный файл и загрузить его вновь, используя новую хеш-функцию. Для этого используют метод расширяемого хеширования, основанный на технологии B-деревьев с расщеплениями и слияниями, благодаря которой потребуется не более двух доступов к диску для поиска заданной записи (т.е., записи, имеющей заданное значение ключевого поля), а в некоторых случаях будет достаточно даже одного доступа независимо от размера файла.
Литература
1.Туманов, В.Е. Основы проектирования реляционных баз данных; Бином, 2012. - 420 c.
2.Уорден, К. Новые интеллектуальные материалы и конструкции. Свойства и применение; М.: Техносфера, 2012. - 456 c.
.Федоров, Алексей; Елманова, Наталья Введение в OLAP-технологии Microsoft; М.: Диалог-МИФИ, 2008. - 473 c.
.Фейерштейн, С.; Прибыл, Б. Oracle PL/SQL для профессионалов; СПб: Питер, 2012. - 540 c.
.Фуллер, Лори Ульрих; Кауфельд, Джон; Кук, Кен Microsoft Office Access 2007 для «чайников»; М.: Вильямс, 2012. - 384 c.
.Хаббард, Дж. Автоматизированное проектирование баз данных; М.: Мир, 2011. - 453 c.
.Хабрейкен, Джо; Хайден, Мэтт Освой самостоятельно сетевые технологии за 24 часа; М.: Вильямс, 2008. - 432 c.
.Шаймарданов, Р.Б. Моделирование и автоматизация проектирования структур баз данных; М.: Радио и связь, 2008. - 469 c.