7.2.1. Физический последовательный метод доступа
Физический последовательный метод доступа предполагает хранение физических записей в логической последовательности. При использовании в качестве носителя хранимых данных последовательного устройства, программист должен предоставлять системе физические записи в логической последовательности. В том случае, когда носителем служит память прямого доступа, система связывает физические записи таким образом, что они образуют логическую последовательность, даже если они не передавались ей в этой последовательности.
Эффективность доступа. Пусть одна физическая запись выбрана, и предстоит выбрать другую с большим значением ключа. В худшем случае для выборки нужной записи необходимо просмотреть все записи базы данных, а в лучшем достаточно выбрать следующую запись. Число записей, к которым необходимо осуществить доступ для выборки нужной, составляет в среднем половину общего числа записей, содержащихся в базе данных.
Эффективность хранения. Если носителем данных служит последовательное устройство, программист должен предоставлять записи базы данных в логической последовательности. В результате память на носителе будет заполняться плотно. При использовании устройства прямого доступа каждой следующей представляемой физической записи система отводит следующий доступный участок физической памяти. Затем между записями базы данных организуются связи, обеспечивающие возможность логически последовательной выборки.
Эффективность доступа физического последовательного метода крайне низка. Для выборки нужной записи необходимо просмотреть все предшествующие ей записи базы данных. Хранение физических записей в логической последовательности можно использовать для ускорения доступа, если до обращения к собственно записям базы данных проверять значения ключей. Метод доступа, построенный по этому принципу, называется индексно-последовательным, а значения ключей хранятся в «индексе».
7.2.2. Индексно-последовательный метод доступа
Существует множество индексных методов доступа, в основе которых лежит принцип создания отдельного файла или структуры из статей значений действительного ключа. Статья действительного ключа называется статьей индекса, а весь файл действительных ключей, как отмечено выше, – индексом. Индексный файл значительно меньше собственно базы данных, и, поскольку в оперативной памяти могут находиться многие из его статей, скорость поиска в нем гораздо выше.
В индексно-последовательном методе доступа индексный файл всегда упорядочен по так называемому первичному ключу (рис. 7.2). Первичный ключ – главный атрибут физической записи. По его значению идентифицируется физическая запись. До тех пор, пока это возможно, записи хранятся в той же логической последовательности, что и индекс (отсюда и название «индексно-последовательный метод доступа»). Поэтому индекс должен содержать ссылки не на каждую запись базы данных по ключу, а на группу записей, хранимых в физическом блоке, по диапазону ключей. Например, если в блоке хранится 10 записей, то для него в индексном файле будет одна статья, а не десять, и размер индексного файла уменьшится в 10 раз.
Последовательная организация индексного файла допускает индексацию его содержимого. Записи индекса группируются в блоки, которые можно также индексировать. При работе с большими файлами такая организация позволяет улучшить характеристики доступа,
На практике ключи редко распределены равномерно, из-за чего предварительное закрепление значений ключей за блоками нежелательно, поэтому при создании файла данных производится первоначальная загрузка в него физических записей, упорядоченных по первичному ключу.
Рис. 7.2
Индексный файл и файл данных организованы последовательно. Индексный файл содержит только максимальные значения первичных ключей записей каждого блока.
Наибольшее либо наименьшее значение ключа последней содержащейся в блоке записи (большинство поставляемых методов доступа обеспечивают загрузку файла данных по возрастанию значения первичного ключа) заносится в индексный файл (рис. 7.2).
Каким же образом метод доступа осуществляет включение новых записей? В зависимости от значений добавляемых записей может потребоваться изменение элементов индекса. Что происходит, когда в блоке нет места для размещения новой записи? Возможны два пути решения этой проблемы:
Запись запоминается в отдельной области, называемой областью переполнения, и блок в этой области связывается в цепочку с блоком, которому логически принадлежит запись. Обращения к записям в области переполнения могут значительно снизить эффективность доступа.
При невозможности введения записи в блок он делится пополам. Первый из двух вновь созданных блоков содержит половину записей, находящихся в исходном блоке, а второй – другую половину. (Иногда разделение блока производится таким образом, что первый блок содержит две трети записей исходного блока, а второй – оставшуюся одну треть.) Затем в индексном файле создается новая статья. По сравнению с организацией цепочек записей в области переполнения при использовании данного метода эффективность доступа в большинстве случаев выше. Однако при многократном расщеплении одних и тех же блоков следует разгрузить и реорганизовать файл, а также создать новый индексный файл.
Для очень больших файлов целесообразно строить несколько индексных файлов. Индексный файл следующего уровня содержит указатели на индексный файл предыдущего уровня. Построение системы индексации этого типа может обеспечить приемлемые размеры индексного файла высшего уровня и возможность хранения его в памяти процессора. На рис. 7.3 показано построение индексного файла более высокого уровня.
Рис. 7.3
Чтобы достичь наивысшей производительности при работе с индексно-последовательными файлами, необходимо учесть следующие факторы.
Эффективность доступа.
Размеры базы данных. По мере расширения базы данных индекс приобретает все большее число элементов. Вероятным результатом этого является повышение уровня индексации. Но наличие индексного файла большого размера или высокий уровень индексации снижают эффективность доступа. В большой базе данных решающим фактором становится скорость выборки первичных и вторичных ключей.
Размер блока. Средний размер блока .и число блоков в базе данных – величины взаимообратные. Чем больше размер блока, тем меньшее их число хранится в базе данных, и тем соответственно меньше элементов в индексе. Следует также принимать во внимание время передачи больших блоков по каналам. Необходимо определить оптимальный размер блока базы данных.
Обновление базы данных. Высокая активность включения и удаления записей базы данных снижает эффективность доступа, поэтому время от времени необходимо проводить реорганизацию базы данных и индексных файлов. В некоторых системах частое обновление несущественно снижает эффективность доступа. Однако использование методов, обеспечивающих возможность поддержания эффективности доступа на постоянном уровне, приводит к увеличению размера базы данных, т. е. к снижению эффективности хранения.
Индекс высшего уровня в памяти процессора. Выделение достаточного для размещения индекса высшего уровня памяти процессора повышает эффективность доступа.
Эффективность хранения.
Размеры базы данных. Для размещения записей, добавляемых в базу данных после начальной загрузки, используется свободная область, резервируемая во время начальной загрузки. Эффективность хранения зависит от того, какую часть памяти, отводимой базе данных, занимает эта свободная область. Поскольку записи должны быть организованы логически последовательно, эффективность хранения зависит и от того, в какой части базы данных частота включения и удаления записей базы данных наиболее высока. Определение числа свободных физических блоков и их частей требует проведения соответствующего анализа.
Размер блока. Размер блока и число блоков – два фактора, влияющие на эффективность хранения. При значительной длине блока статьи индекса занимают меньший объем памяти. По мере увеличения длины блоков сокращается их число. С ростом числа блоков требуется больше уровней индексации.
Также следует отметить, что большинство систем допускают только уникальные значения ключей индекса.