 |
Структуры хранения данных и методы доступа к ним
|
|
|
|
Информация и СУБД
Появление компьютеров не сразу привело к разработке информационных систем. На заре вычислительной техники компьютеры обладали ограниченными возможностями в части памяти. Оперативная память не обладает свойством долговременного хранения, магнитные ленты не обеспечивают прямого доступа, а магнитные барабаны имели ограниченный объем. Развитие информационных систем началось с появлением магнитных дисков и файловых систем. Информационные системы, главным образом, ориентированы на хранения и вывод и модификацию постоянно существующей информации. Структура данных в разных информационных системах может быть различна, но между ними больше общего.
Стремление выделить и обобщить общую часть информационных систем, ответственную за управление сложно-структурированными данными является одной из побудительных причин создания СУБД.
СУБД – Системы Управления Базами Данных.
Понятие согласованности данных является ключевым понятием баз данных. Если информационная система поддерживает согласованное хранение информации в нескольких файлах, то можно говорить о том, что она поддерживает базу данных. Если некоторая вспомогательная система позволяет работать с несколькими файлами, обеспечивая их согласованность, то можно назвать ее системой управления базами данных.
Для обеспечения параллельной работы с базой данных использование файлов не дает возможности одновременной модификации данных, т.к. первый же процесс накладывает блокировки на весь файл целиком, что приводит к генерации ошибки для параллельных процессов. СУБД обеспечивают более тонкую синхронизацию параллельного доступа к данным.
|
|
|
Если информационная система поддерживает два согласованных файла сотрудники и отделы и была добавлена запись файл сотрудники, а в файле отделы модификация записи не была выполнена из-за аварийного выключения питания, то при перезапуске системы данные будут находиться в рассогласованном состоянии. Согласование информации после сбоев берет на себя СУБД. То есть прикладная система не обязана отвечать за согласованность данных.
Структуры хранения данных и методы доступа к ним
Структурой хранения называется любое упорядочение данных на диске. Могут быть реализованы различные структуры хранения. Более того эти структуры могут меняться по мере изменения требований к производительности системы.
Доступ к базе данных
Поиск и предоставление данных пользователю осуществляется с помощью нескольких программ. При этом можно выделить следующие уровни доступа к данным: СУБДß(запрос данных)(возвращение данных)àДиспетчер файловß(запрос файла)(возвращение файла)àДиспетчер дисковß(дисковая операция ввода, вывода)(чтение данных с диска)àБД.
1) В СУБД определяется искомая запись и затем для ее извлечения запрашивается диспетчер файлов.
Запись – хранимая информация об объекте базы данных.
2) Диспетчер файлов определяет страницу, на которой находится искомая запись, а затем для извлечения этой страницы запрашивают диспетчер диска.
Страницей (блоком) устройства ввода/вывода называется количество данных, передаваемых из вешней памяти в оперативную за одно обращение. Размер страницы обычно кратен одному килобайту.
3) Диспетчер дисков определяет физическое положение искомой страницы на диске, и посылает соответствующий запрос на ввод/вывод данных. Если в результате предыдущих запросов искомая страница уже находится в оперативной памяти, то этот пункт не выполняется.
С точки зрения СУБД база данных представляет собой набор записей, которые могут просматриваться с помощью диспетчера файлов. Диспетчер файлов рассматривает базу данных как набор страниц, просматривая с помощью диспетчера дисков. Диспетчер дисков непосредственно работает с диском.
|
|
|
Диспетчер дисков
Диспетчер дисков является компонентом ОС. При выполнении дисковых операций необходимо знать физические адреса на диске. Диспетчер файлов рассматривает диск как набор страниц фиксированного размера с уникальным идентификационным номером набора страниц. Каждая страница обладает уникальным внутри данного набора идентификационным номером страницы.
Соответствие физических номер на диске и номеров страниц достигается с помощью диспетчера дисков. Преимуществом такого подхода является аппаратная независимость программных компонентов высокого уровня.
Один из наборов страниц называется набором пустых страниц и содержит все имеющиеся свободные страницы.
Основные операции выполняемы диспетчером диска:
1) извлечь страницу P из набора страниц S
2) заменить страницу P из набора страниц S
3) добавить новую страницу в набор страниц S (то есть извлечь одну страницу из набора пустых страниц и возвратить новую страницу с номером P)
4) удалить страницу P из набора S (то есть возвратить страницу с номером P в набор пустых страниц)
Диспетчер файлов
Файлом называется набор однотипных записей. Основными операциями выполняемыми диспетчером файлов являются:
1) извлечь запись R из файла F
2) заменить запись M из файла F
3) добавить новую запись R в файл F
4) удалить запись R из файла F
5) создать новый файл F
6) удалить F
В одних системах диспетчер файлов является компонентом ОС а в других поставляется в составе СУБД.
Кластеризация
Это процесс как можно более близкого физического размещения на диске, логически связанных между собой и часто используемых данных.
Сегментàэкстент (непрерывная последовательность блоков).
Различают внутрифайловую и межфайловую кластеризацию. Например, у нас есть два файла: файл поставщиков и файл товаров. Если нам нужно получить поставщиков с номерами идентификаторов от ИД1 до ИД9, то оптимальным будет выполнение кластеризации поставщиков в соответствии с возрастанием убыванием) идентификаторов.
|
|
|
Если требуется одновременно получать информацию о поставщике и его товарах, то записи из двух разных файлов должны располагаться рядом. Для эффективного доступа. Это пример межфаловой кластеризации.
В каждый момент времени кластеризацию можно осуществить только одним из способов поскольку это связано с физическим размещением данных на диске.
Физическое размещение данных на диске
Логическая последовательность страниц задается с помощью указателей, то есть логически близко находящиеся данные физически могут отстоять друг от друга значительно.
С целью сохранения близкого расположения логически связанных страниц на диске диспетчер дисков обычно размещает или удаляет страницы в наборах не по одной, а экстентами.
Для получения информации о размещении различных наборов страниц, диспетчеру дисков достаточно знать расположение только первой страницы в группе, расположение остальных определяется с помощью указателей в заголовках страниц. Все имеющиеся наборы страниц вместе с указателями на первые страницы каждого из наборов перечислены в отдельном месте на диске. Это место, а именно страница часто называется таблицей содержания диска, каталогом набора страниц или просто страницей «нуль».
Записи в пределах страницы также можно разместить в соответствии с логическим порядком.
Записи идентифицируются с помощью идентификационного номера записи (RID). Этот RID состоит из двух частей – номера страницы, на которой данная запись находится и байта смещения слота от конца страницы. Этот байт смещения содержит байт смещения записи от начала страницы. Эта схема является компромиссом между быстротой и непосредственной адресацией и гибкостью косвенной. В результате записи внутри страницы могут сдвигаться вверх и вниз (для поддержания соответствия между логическим и физическим порядком) без изменения идентификационных номеров записей.
Согласно выше – изложенному, для каждого файла всегда можно осуществить последовательный доступ ко всем записям. Такая последовательность называется физической хотя она не обязательно соответствует физическому размещению данных на диске. Запись может содержать дополнительную информацию в так называемой приставке, в частности здесь может содержаться информация об идентификационном номере файла, которому принадлежит запись (в случае межфайловой кластеризации), длина записи (для записи переменной длины), флаг удаления, указатель при связывании записей в цепочку и тд.
|
|
|
Индексирование
Пример: Поставщики
| Номер | Фамилия | Скидка | Город |
| Иванов | Ростов | ||
| Петров | Таганрог | ||
| Сидоров | Таганрог | ||
| Федоров | Ростов | ||
| Агафонов | Азов |
При наличии индекса, имеется несколько стратегий доступа к данным из файла поставщики. Пример: найти поставщиков из города Ростов. 1я стратегия: прочитать (scan) файл поставщиков и выбрать те строки, у которых город = Ростов. 2я стратегия: чтение файла городов (scan). Для строк, у которых город = Ростов извлекаются записи из файла поставщики согласно RID указателям.
Если доля поставщиков из Ростова, по отношению к их количеству достаточно мала, то 2я стратегия будет эффективней 1й. Это связано с тем, что в силу упорядоченности записей в файле города, поиск будет прекращен с следующего за ростовом названия города, во вторых, если придется просмотреть файл городов полностью, то при этом потребуется значительно меньше операций ввода вывода. Поскольку файл городов имеет размер меньший чем файл поставщиков.
В просматриваемом примере файл городов называется индексным файлом или просто индексом по отношению к файлу поставщиков. Индексный файл это файл, который содержит данные из другого файла, который называется индексированным (в примере файл поставщики) и вид указателя фактические данные (файл поставщики). RID указатель служит для связывания записи индексного файла с записью индексируемого файла.
Использование индексов на ряду с ускорением выборки имеет недостаток, который связан с замедлением процесса обновления данных. Так как при изменении данных в индексированном файле придется менять данные в индексных файлах. И чем больше индексных файлов тем медленней процесс.
Индексы так же могут использоваться для проверки наличия некоторого значения. Например для ответа на вопрос, если поставщики из города Батайск, достаточно будет просмотреть только индексный файл. Файл может иметь несколько индексов, которые могут использоваться совместно. Кроме того индексы могут быть составными, которые эффективно могут использоваться при поиске значений в первом столбце или в первом втором, третьем.
|
|
|
Индексы часто называют инвертированными списками. Файл с индексами по каждому полю называется полностью инвертированным.
Плотное и неплотное индексирование
Плотный индекс имеет вход для каждой записи индексированного файла. В индексе используются RID указатели, хотя достаточно было бы только номеров страниц. Так как извлечение конкретной записи уже будет выполняться в ОП. То есть число дисковых операций ввода вывода не увеличится. Если физическая последовательность файл поставщиков соответствует логической последовательности (например по номер по номеру поставщика). Иначе говоря, в этом файле выполнена кластеризация по полю номера. Если проиндексировать файл по полю номер, то нет необходимости в таком индексе хранить указатели для каждой записи индексируемого файла. Достаточно хранить максимальный номер поставщика для каждой страницы и номер соответствующей страницы. Такой индекс называется неплотным. Преимущество использования неплотных индексов заключается в их малом размере поскольку просматриваться такие файлы будут с большой скоростью. Однако, с помощью одного такого индекса нельзя ответить на вопрос о наличии некоторого значения.
Для данного файла может быть построено любое число плотных индексов и только 1 неплотный индекс.
Структура типа B-tree
Дерево состоит из двух множеств: множество вершин и множество дуг. Корневой называется вершина не имеющая входящих в нее дуг. Дерево всегда имеет только 1 корень. Листом называется вершина, которая не имеется выходящих дуг. У листьев нет дочерних вершин, а у корня нет родителя. Каждая вершина кроме корня имеет только одну родительскую вершину. Дерево называют сбалансированным тогда и только тогда, когда каждый его лист имеет одинаковое число предков. B-tree является индексными последовательными файлами имеющими иерархические индексы. Подобные структуры используются практически во всех СУБД. Буква B означает сбалансированная, а не бинарная. В отличии от бинарных деревьев, которые юзаются в ОП и каждый узел имеет не более 2х потомков, узлы B дерева имеют множество потомков. Каждый узел сбалансированного дерева на диске фактически занимает полностью весь блок. В итоге в каждом блоке Б3 содержится сотня указателей на потомков. При поиске в B tree проверяется только 3 дисковых блока.
Необходимость создания структуры B tree заключается в желании заключается в желании в избежание просмотра всего содержимого индексного файла. Идея состоит в том, чтобы создать для индексного файла еще 1 индекс и так далее. При этом индекс на каждом из уровней будет не плотным по отношению к нижнему индексированному уровню. Такой многоуровневый индекс состоит из двух частей: набора последовательностей и набора индексов.
Набор последовательностей включает одноуровневый индекс для реальных данных, который обычно является, при этом записи внутри индекса сгруппированы по страницам, а страницы связаны в цепочку, что дает возможность организовать быстрый последовательный доступ к индексированным данным.
Набор индексов
Обеспечивает быстрый непосредственный доступ к наборам последовательностей (последовательным данным). Фактически набор индексов является индексным файлом со структурой B-tree. Комбинация набора индексов и набора последовательностей называется структурой типа B+tree.
Одним из недостатков иерархических структур является несбалансированность их работы после удаления или вставки некоторых элементов. В результате элементы с реальными данными могут оказаться на разных расстояниях от корневого элемента. Продолжительность поиска в несбалансированной структуре может оказаться непредсказуемой. Преимуществом структуры типа B tree является возможность сбалансированной вставки или удаление значений. Для вставки нового значения V в структуру типа B-tree порядка n. Пусть V = 41. Например, может быть использован следующий алгоритм:
1) на самом низком уровне набора индексов следует найти элемент содержащий 2m индексных записей. Нам нужно отложит элемент N содержащий 2m индексных записей. Если элемент N содержит свободное пространство, то значение вставляется в него и на этом процесс завершается.
2) в противном случае (если свободного пространства нет) элемент N разделяем на два элемента N1 и N2. Обозначим символом S множество 2m+1 значений, в котором 2m несходных значений и 42. Первые m значений этой логической последовательности и среднее между ними значение W необходимо поместить в элемент N1. А последние m в элемент N2. Значение W необходимо поместить в родительский элемент P на более высоком структурном уровне. В последствии при осуществлении поиска некоторого значения U, достижения элемента P, поиск будет перенаправлен в сторону элемента N1 (если U<=W), либо в сторону элемента N (если U> W).
Далее этот процесс следует повторить для вставки среднего значения W в родительский элемент P на более высоком структурном уровне. В худшем случае процесс разделения элемента структуры может продлиться вплоть до корневого элемента с образованием нового иерархического уровня. Для удаления элемента следует применить аналогичный алгоритм в обратном порядке.
Кэширование
Стилем и порядком дерева называется максимально допустимое количество дочерних узлов для каждого родительского узла. Большие степени обычно используются для создания более широких и менее глубоких деревьев. На практике каждый узел в дереве является страницей и потому в нем может храниться значительно больше 3х указателей и 2х ключевых значений как в рассмотренном примере. Пример: страница имеет размер 4096 байт, указатель 4 байта, размер индексируемого поля тоже 4 байта, указатель на узел того же уровня тоже 4 байта, и того: на одной странице можно хранить (4096-4)/(4+4)=511 записей. Таким образом порядок B-tree+ равен 512. То есть корень дерева должен содержать до 511 записей и иметь до 512 дочерних узлов. Каждый дочерний узел также может содержать до 511 записей и 512 для его дочерних узлов. Кэшированием, кэш адресацией или хэш - индексированием называется технология быстрого прямого доступа к записи на основе заданного значения некоторого поля. При этом: 1) каждая запись помещается по адресу (reed указатель или номер страницы), который вычисляется при помощи специальной хэш функции на основе значения некоторого поля данной записи, которая называется хэш полем иди хэш ключом. Вычисленный адрес называется хэш адресом. 2) для сохранения записи сначала вычисляется хэш адрес новой записи, а затем диспетчер файлов помещает эту запись по вычисленному адресу. 3) для извлечения записи по заданному значению хэш поля сначала вычисляется хэш адрес а затем запись извлекается по этому адресу.
Для выбора «хорошей» функции хэширования необходимо знать, во первых примерное число записей в файле и во вторых сколько записей может поместиться в блок. Эта информация нужна для вычисления количества блоков в файле и соответственно диапазона значений функции хэширования. Если для файла будет выделено слишком мало блоков, то эффективность доступа будет уменьшаться по мере их переполнения. Если наоборот, для размещения файла будет предусмотрено слишком много блоков, то доступ будет осуществляться быстро, но значительная часть памяти в этом случае останется незанятой данными. Обычно считается нормальным, когда занято данными две трети блока.
Функция хэширования выбирается таким образом чтобы максимально удовлетворить следующим условиям:1)каждое ее значение должно быть целым из интервала от 0 до (число блоков -1), 2) она должна быть удобной для вычислений, то есть вычисления значения функции должно происходить быстро, 3) для множества реальных значения ключа значения функции хэширования должны быть явно вероятными. Если хэш функция удовлетворяет 3му условию, то говорят, что она перемешивает значения ключа. Если это условие нарушено, то может оказаться так, что часть блоков окажется переполненной, в то время как остальные будут заполнены незначительно, что отрицательно скажется на эффективности доступа.
Непригодность файлов с хэш адресацией к групповой обработке
Прямой доступ имеет место, когда требуется найти одно значение ключа. В процессе групповой обработки требуется получить несколько значений (или говорят ответов). Назовем коэффициентов активности отношение числа ответов к числу записей в файле. Коэффициент активности близок к единице, когда требуется получить почти все записи из файла (например платежная ведомость). Прямой доступ имеет место, когда коэффициент активности близок к нулю. То есть нужно найти одну запись. При групповой обработке использовать последовательный файл бывает выгодней чем файл с хэш адресацией. Для того чтобы правильно выбрать организацию файла, необходимо хотя бы приблизительно знать коэффициент активности файла.
Цепочки указателей
Для выполнения запроса типа “найти поставщиков из города N” можно применить способ хранения данных с использованием цепочек указателей (смотри рисунок). В данном случае этот способ будет более эффективным чем индексирование. Из файла поставщиков извлекается атрибут город, который формирует родительскую структуру городов. Файл поставщиков по отношению к этому родительскому файлу называется дочерним. При выполнении запроса в такой дочерней структуре в файле городов находится нужный город, а затем по цепочке указателей извлекаются записи поставщиков из данного города. При таком способе не будет выполняться чтение записей поставщиков из других городов. Другим преимуществом данной структуры является более простое выполнение вставки и удаления записей по сравнению с индексной структурой. Кроме того эта структура занимает меньше места на диске, поскольку нет повторения названия городов.
Недостатки структуры
1) Для доступа к Nму поставщику требуется перебрать все предыдущие записи поставщиков. В худшем случае, для каждого доступа может потребоваться отдельная дисковая операция чтения.
2) Структура весьма неэффективна для обратного запроса: «найти город данного поставщика». Дело в том, что для поиска названия города приходится просматривать всю цепочку. В итоге часто совместно с цепочкой указателей приходится использовать другие структуры.
3) Создать родительско – дочернюю структуру в уже имеющемся наборе записей не так просто, поскольку цепочки указателей пронизывают все записи. А значения соответствующих полей необходимо извлечь и выстроить родительский файл. Выполнить же индексирование имеющегося набора гораздо проще.
Меры по улучшению структуры
1) Указатели можно задать также и в обратном направлении. При этом существенно упрощается процесс согласования указателей при удалении дочерней записи.
2) В записи дочерней структуры можно добавить указатель на родительскую запись.
3) Можно не удалять атрибут город из дочерней структуры.
В данном файле можно задать как любое количество индексов так и любое количество цепочек указателей.
Управление данными расположенными в оперативной памяти
Возможность размещать базу данных целиком в оперативной памяти появилась в связи с резким снижением цен на модули памяти и широким распространением 64х разрядных операционных систем. При простом перемещении данных «дисковой» СУБД в оперативную память, ожидаемого повышения производительности не произойдет. Дело в том, что реляционная база данных функционирует исходя из предположения, что обрабатываемые данные в основном находятся на диске. Алгоритмы оптимизации, управление буферным пулом и технология извлечения данных на основе индексов – все это существенным образом ориентировано на дисковое хранение данных. Оптимизация запросов также выполняется исходя из предположения о хранении данных на диске. При работе с данными резидентно находящимися в ОП, надобность в буферном пуле отпадает.
В традиционной СУБД узел B-tree представляет собой страницу диска и содержит максимально возможное число указателей на дочерние узлы. В результате дерево имеет малую глубину и большую ширину. Такая структура позволяет уменьшить число операций ввода-вывода. Если данные находятся в ОП, то эта структура будет работать хуже бинарных деревьев, так как вычислительная мощь процессора растрачивается на сравнение значений индекса в B-tree, а так же на управление буферами, которые содержат данные и индексы.
В Times Ten используется индекс типа T-tree оптимизированный для доступа к ОП. Для навигации по дереву используется указатели <= и >, представляющие собой непосредственно ссылки на адрес памяти, а не на дисковую страницу.
В Times Ten используются технологии индексирования двух типов: Хэш-индексы и T-tree. Хэш индексы используются, когда требуется найти точные совпадения с образцом, а T-tree более подходит для поиска значений в диапазоне. Хэшированные индексы создаются автоматически, когда в данных задается первичный ключ, а T-tree создаются при помощи команды.
|
|
|
