Файл: Реферат Организация доступа к данным Страницы и файлы.docx
Добавлен: 08.11.2023
Просмотров: 96
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
РефератОрганизация доступа к данным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) наиболее популярен в реляционных базах данных. Их использование предусмотрено почти во всех СУБД, а некоторые СУБД работают только на основе индекса бинарного типа.
Тогда при извлечении страниц, содержащих множество кортежей отношения Поставщик, система будет извлекать и данные необходимых для соединения кортежей отношения Поставки. В каждый момент времени кластеризацию файла или набора файлов можно осуществлять только одним из этих способов.
Внутрифайловую и межфайловую кластеризацию СУБД может осуществлять, размещая логически связанные записи на одной странице (если это возможно) или на смежных страницах. Поэтому СУБД важно иметь сведения не только о сохраненных файлах, но и о страницах. Диспетчер дисков должен обеспечить, чтобы логически близкие страницы были физически близко расположены на диске.
Очевидно, что после выполнения нескольких обычных действий (например, добавление или удаление записей) нельзя гарантировать, что логически близкие страницы будут физически располагаться одна возле другой (диск будет «фрагментирован»). Поэтому логическую последовательность страниц в данном наборе следует задавать с помощью указателей, а не на основе их физически близкого размещения на диске. Для этого каждая страница содержит заголовок с информацией о физическом дисковом адресе той страницы, которая логически следует за данной. Тогда достаточно знать расположение только первой страницы из набора, поскольку положение второй и последующих страниц операционная система определит с помощью указателей в заголовках.
В реальных базах данных на одной странице может размещаться не одна, а несколько хранимых записей и их логическая последовательность для данной страницы может соответствовать физической последовательности, заданной внутри этой страницы. Для этого диспетчер файлов может передвигать отдельные записи вверх или вниз на странице, размещая все записи в верхней части страницы и оставляя свободное пространство в нижней части страницы.
В стандартных СУБД хранимый файл представляет собой набор хранимых записей с указателями, постоянными до тех пор, пока существуют эти записи. Для некоторого хранимого файла всегда можно осуществить последовательный доступ ко всем хранимым записям, где под термином «последовательный доступ» подразумевается доступ согласно последовательности записей внутри страницы и последовательности страниц внутри набора страниц (обычно это порядок возрастания идентификационных номеров записей). Такая последовательность называется физической, хотя она не обязательно соответствует физическому расположению данных на диске.
2. ИндексированиеОсновное назначение индексов состоит в обеспечении эффективного прямого доступа к кортежу отношения. Индекс - это упорядоченное множество значений, в чем-то подобное предметному указателю в книге (предметный указатель - упорядоченное множество слов с указанием страниц, где встречается это слово). Чтобы отыскать в книге нужное слово, можно сначала найти его в предметном указателе, где хранятся нужные страницы книги. В индексе базы данных перечислены значения некоторого атрибута вместе с указателями страниц, содержащих кортежи, где хранится соответствующее значение.Рассмотрим в качестве примера таблицу с данными о поставщиках (рис. 2.) и запрос типа «Найти всех поставщиков из города С». На основании этой таблицы может быть создан файл с данными о городах. Файл городов может быть упорядочен по алфавитному перечню их названий, т.е. по ключевому полю ГОРОД, с указателями на соответствующие записи в файле поставщиков.Поиск всех поставщиков из Минска, например, можно выполнить двумя способами:. Найти весь файл поставщиков, найти все записи, для которых названием города является строка «Минск»;. Найти файл городов, найти в нем строку «Минск», а затем согласно указателям извлечь все соответствующие записи из файла поставщиков.Если доля всех поставщиков из Минска по отношению к общему количеству поставщиков достаточно мала, то второй способ будет гораздо эффективнее первого. СУБД известна физическая последовательность записей в файле городов, но даже если придется просмотреть файл городов полностью, для такого поиска потребуется гораздо меньше операций ввода-вывода, поскольку физический размер файла городов меньше, чем размер файла поставщиков из-за меньшего размера записей.В рассматриваемом примере файл городов называется индексным файлом или индексом по отношению к файлу поставщиков, а файл поставщиков называется индексированным файлом по отношению к файлу городов. Индексный файл - это хранимый файл особого типа, в котором каждая запись состоит из двух значений, а именно данных и RID-указателя, необходимого для связывания с соответствующей записью индексированного файла.Если индексирование организовано на основе ключевого поля, например на основе поля П № файла поставщиков, то индекс называется первичным (или уникальным), а если индекс организован на основе другого поля, например поля ГОРОД, как в рассматриваемом примере, то он называется вторичным.
Существует два способа использования индексов. Во-первых, их можно использовать для последовательногодоступа к индексированному файлу, где последовательность задается значениями индексного поля. Например, индекс по полю ГОРОД из рассматриваемого примера будет определять доступ к записям файла поставщиков согласно алфавитному перечню городов (найти поставщиков из городов, начинающихся на буквы К-М). Во-вторых, индексы могут использоваться для прямого доступа к отдельным записям индексированного файла на основе заданного значения индексного поля. Пример запроса «Найти поставщиков из Минска» является типичным примером такого использования индексов.Хранимый файл может иметь несколько индексов. Например, хранимый файл поставщиков может иметь индекс ГОРОД и индекс СТАТУС. Они могут как раздельно, так и совместно использоваться для более эффективного доступа к записям о поставщиках. Для иллюстрации «совместного» использования индексов рассмотрим запрос «Найти поставщиков из Бреста со статусом 20». Если согласно индексу ГОРОД для поставщиков из Бреста найдены записи с RID-указателями r1 и r5, а согласно индексу СТАТУС - записи с RID-указателями r1 и r4, то условиям запроса удовлетворяет только запись с данными о поставщике c указателем r1. Только после этого в СУБД будет организован доступ к файлу поставщиков и будет извлечена данная запись.Индексы часто называют инвертированными списками, а файл с индексами по каждому полю называется полностью инвертированным.Индекс можно также создать на основе комбинации двух или более полей. Например, если проиндексировать файл поставщиков на основе комбинации полей ГОРОД и СТАТУС, то запрос типа «Найти поставщиков из Бреста со статусом 30» можно выполнить на основе однократного просмотра с помощью одного индекса. Причем, комбинированный индекс ГОРОД/СТАТУС может также служить индексом по одному полю ГОРОД, поскольку все записи в комбинированном индексе расположены по крайней мере последовательно.Значительное ускорение процесса выборки или извлечения данных является основным преимуществом использования индексов, а основным недостатком - замедление процесса обновления данных. Действительно, при каждом добавлении новой записи в индексированный файл потребуется также добавить новый индекс в индексный файл. Поэтому при выборе некоторого поля для индексирования необходимо выяснить, что более важно для данной СУБД: скорость извлечения данных или скорость обновления?
Кроме того, не рекомендуется создавать индексы по всем атрибутам. Обычно индексы создаются для следующих типов атрибутов:Первичные ключи (ускорение поиска записи);Внешние ключи (ускорение выполнения соединений);Атрибуты, часто фигурирующие в запросах, ответами на которые являются небольшие множества записей;Атрибуты, по которым часто сортируются данные.До сих пор предполагалось, что для ускорения процесса извлечения данных используются указатели записей (RID-указатели). Но иногда для этого достаточно использовать указатели страниц (т.е. номеров страниц). Конечно, для последующего поиска записи внутри данной страницы придется осуществить еще одну операцию извлечения записи. Однако теперь она будет выполняться в оперативной памяти и для этого не придется увеличивать число дисковых операций ввода-вывода. Если в таблице Поставщики выполнена кластеризация по полю П № и по этому же полю осуществляется индексирование, то нет необходимости хранить в индексном файле указатели для каждой записи индексируемого файла (в данном случае для файла поставщиков). Достаточно иметь указатель для каждой страницы, состоящий из максимального номера поставщика для данной страницы и соответствующего номера страницы. В этом случае процесс извлечения записи для некоторого поставщика будет состоять из помещения в оперативную память соответствующей страницы и очень быстрого поиска нужной хранимой записи.Такой индекс называется неплотным. Все описанные ранее индексы, наоборот, называются плотными. Одним из преимуществ неплотных индексов является их малый размер по сравнению с плотными индексами. Как правило, это обеспечивает просмотр содержимого базы данных с большей скоростью. Поэтому обычно при индексировании используют оба типа индексов.Структуры типа Б-дереваЕсли индексированный файл имеет большой размер, то и его индекс также велик. Поэтому последовательный просмотр даже одного только индекса требует больших затрат времени. Для разрешения такой проблемы можно рассмотреть индексный файл как обычный хранимый файл и создать для него еще один индекс. Эту операцию можно осуществлять повторно нужное количество раз (обычно она применяется трижды). При этом индекс на каждом из уровней будет неплотным по отношению к нижнему индексируемому уровню. Такой подход к организации индексов бинарного типа (или Б-дерева - B-tree) наиболее популярен в реляционных базах данных. Их использование предусмотрено почти во всех СУБД, а некоторые СУБД работают только на основе индекса бинарного типа.