Файловые структуры для хранения информации в базах данных

Классификация

Файлы:

прямого доступа
последовательного доступа
индексные

плотный индекс (индексно-прямые)
В – деревья
Индексно-последовательные

инвертированные списки
взаимосвязанные файлы

· с однонаправленными цепочками

· с двунаправленными цепочками

Файловые структуры для хранения информации в базах данных - student2.ru

Прямого доступа на устройствах прямого доступа. Имеют фиксированную длину записи, и обеспечивают более быстрый доступ. Адрес м.б. вычислен по номеру записи. Однако поиск по номеру неэффективен. Лучше искать по ключам, поэтому есть ф-я преобразования ключа в номер.(например – хеширование(рассказать))

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

Плотный индекс: данные в области данных одинаковой длины. В индексной области все записи упорядочены по значению ключа.

Неплотный индекс – ключ указывает не на запись, а на страницу записей. Внутри страниц записи упорядочены.

Б деревья – построение индекса по индексу

Инвертированные списки: ведется поиск по вторичным ключам. Они м.б. одинаковыми. Инвертированный список – двухуровневая индексная структура. На первом уровне расположены значения вторичных ключей. На втором – блок указателей на записи с таким значением ключа. На третьем – собственно данные.

Деревья – ежику понятно.(LPTR,DATA,RPTR)

Файлы прямого и последовательного доступа

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

Файлы последовательного доступа организованы на устройствах последовательного доступа.

Файлы последовательного доступа могут быть организованы двумя способами.

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

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

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

NZ=F(k)

NZ – номер записи

k – значение ключа

F - функция

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

Когда это не удается, применяются методы хэширования и создаются специальные хэш-функции.

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

Существуют разные методы:

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

Плотный, неплотный индекс

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

Файлы с плотным индексом

В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, в структура записи в ней имеет следующий вид:

Файловые структуры для хранения информации в базах данных - student2.ru

Значение ключа – значение первичного ключа

Номер записи – порядковый номер записи в основной области.

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

Схематично это можно представить следующим образом:

Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны 2 решения:

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

Первый способ требует дополнительного времени на переработку индексной области.

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

Файлы с неплотным индексом

Неплотный индекс строится для упорядочения файлов. Структура записей индекса для таких файлов имеет следующий вид

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

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

Инвертированные списки

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

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

Инвертированный список по номеру группы для списка студентов

1-ый уровень 2-ой уровень