Методы доступа к данным

Доступ к данным

Существует шесть основных методов доступа к данным:

• Физический последовательный.
• Индексно-последовательный.
• Индексно-произвольный.
• Инвертированный.
• Прямой.
• Доступ через хеширование.

Перечисленные методы отличаются друг от друга по двум признакам:

• Эффективность хранения;
• Эффективность доступа.

Как правило, эти два признака находятся в обратной зависимости. При эффективном хранении доступ усложняется. И наоборот - меры ускоряющие доступ к данным, приводят к увеличению объемов требуемой для хранения памяти.

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

Физический последовательный метод доступа

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

Эффективность физического последовательного доступа очень низка. Для нахождения нужной записи производится последовательный перебор. В среднем требуется перебрать N/2 записей при общем количестве записей N.

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

Индексно-последовательный метод доступа

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

При добавлении новой записи выполняется один из двух алгоритмов:

1. Запись сохраняется в отдельной области (область переполнения) и связывается с блоком, которому логически принадлежит.
2. Если запись невозможно добавить в некоторый блок, то блок делится пополам. В индексный файл записывается новый ключ.

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

Индексно-произвольный метод доступа

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

Эффективность доступа при этом методе очень высока, так как индекс содержит ссылки на сами записи, а не на блоки. Но индексные файлы по этой же причине имеют очень большой объем.

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

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

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

Прямой метод доступа

При этом методе между ключом записи и ее физическим адресом устанавливается взаимно-однозначное соответствие.

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

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

Доступ через хеширование

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

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