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

Хранение данных и доступ к ним.

Интерфейсы при выполнении запроса.

Критерии эффективности хранения данных.

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

2. Размер блока. Размер блока и число блоков — два фактора, влияющие на эффективность хранения. При значительной длине блока статьи индекса занимают меньший объем памяти. По мере увеличения длины блоков сокращается их число. С ростом числа блоков требуется больше уровней индексации.

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

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

Что касается структур данных, то она (структура данных) подразумевает последовательный доступ, если за каждый конкретный момент времени можно обратиться лишь к одному элементу структуры, причем доступ к элементам происходит в определенном порядке. Каноническим примером служит связанный список. Индексация в списке с последовательным доступом требует O(k) времени, где k - индекс.

263. Индексно-последовательный доступ к данным.
ISAM (англ. Indexed Sequential Access Method — Индексно-Последовательный Метод Доступа) — способ хранения данных для быстрого доступа к ним. Способ был разработан компанией IBM для мейнфреймов в 1963 году, в настоящее время это основной способ представления данных почти во всех базах данных (реляционных и пр.).
В ISAM отдельно хранятся записи с данными и индексы (служебные данные), служащие для быстрого доступа к записям. Данные хранятся последовательно (изначально ISAM использовался для хранения данных на ленточных накопителях, обеспечивающих только последовательные чтение/запись). Второй набор данных — хеш-таблица — индексы, содержащие указатели, которые позволят извлечь определенные записи без поиска по всей базе данных. Это несколько отличается от индексов в современных поисковых базах данных, так как в них индексы хранятся прямо в записях. Ключевая особенность ISAM — индексы малы, и поиск по ним быстр. Изменение в записях не требует изменять все записи, требуется только перестроить индекс.
Индексно-последовательный.
• Метод доступа, при использовании которого до осуществления доступа к собственно записям базы данных проверяются значения ключей, называется индексно-последовательным.
• Значения ключей физических записей находятся в логической последовательности. Может применяться как для хранения, так и для выборки данных.
• В индекс значений ключей заносятся статьи наибольших значений ключей в блоках.
• Наличие дубликатов значений ключей недопустимо.
• Эффективность доступа зависит от числа уровней индексации, распределения памяти для размещения индекса, числа записей базы данных и уровня переполнения.
• Эффективность хранения зависит от размера и изменяемости базы данных.

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

При таком методе доступа записи хранятся в произвольном порядке и создается отдельный файл статей, включающих значения действительного ключа, и физические адреса хранимых записей. Статья, содержащая действительный ключ и адрес, называется статьей индекса, а весь файл – индексом. Каждой записи базы данных соответствует статья индекса.
Индексно-произвольный.
• При индексно-произвольном методе доступа записи хранятся в произвольном порядке. Создается отдельный файл из статей, содержащих значения действительного ключа и физические адреса хранимых записей.
• Значения ключей физических записей необязательно находятся в логической последовательности.
• Хранение и доступ к индексу могут осуществляться с помощью индексно-последовательного метода доступа.
• Индекс содержит статью для каждой записи базы данных. Эти статьи упорядочены по возрастанию. Ключи индекса сохраняют логическую последовательность. Если же они эту последовательность не сохраняют, доступ к индексу осуществляется посредством алгоритма хеширования. Записи базы данных могут быть и не упорядочены по возрастанию ключа.
• Может использоваться как для запоминания, так и для выборки данных.