Последовательная организация

Методы физического проектирования для реляционных моделей

Физическое проектирование структур данных

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

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

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

Записи файла соответствуют логической модели данных. Число реляционных структур (таблиц) соответствует числу файлов. Доступ к записям осуществляется тремя способами: последовательным сканированием, блочным, двоичным.

При последовательном сканировании записи файла могут быть неупорядочены по первичному ключу. Для обозначения значения ключевого поля в запросе введем нотацию К_доступ. Последовательно, начиная с первой записи, сравнивается ключ каждой записи файла К с ключом доступа К_доступ. При равенстве обоих ключей требуемая запись найдена: содержащаяся в ней информация полностью или частично выводится пользователю. Если же равенство не выполняется, последующие шаги алгоритма различаются для упорядоченного и неупорядоченного файла:

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

· для упорядоченного файла проверяется условие, например, превышения значения ключа доступа К_доступ значения ключа К: если файл упорядочен по возрастанию, поиск продолжается; если по убыванию – поиск прекращается ввиду отсутствия нужной записи.

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

Файл разделяется на виртуальные блоки размером ÖN записей, где N – число записей в файле. С ключом доступа К_доступ сравниваются ключевые поля последних записей в блоках - К_j^блока, начиная с первого блока (j – номер блока). С помощью такого сравнения вначале определяется блок, в котором возможно нахождение нужной записи (для этого требуется выполнение условия К_доступ < К_j^блока)[5], а затем уже, как правило, методом последовательного сканирования - сама запись в блоке.

При двоичном способе записи файла также должны быть упорядочены по первичному ключу. Файл последовательно делится на две части, уменьшая пространство поиска каждый раз вдвое. Ключ доступа К_доступ сравнивается с ключевым полем «средней» записи - К_ср. Здесь возможны варианты:

К_доступ=К_ср; «средняя» запись является искомой, алгоритм заканчивает работу;

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

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

Продолжение поиска заключается вновь в делении выбранной половины файла пополам и т.д. Алгоритм заканчивает работу при нахождении нужной записи или при условии, когда очередная «половина» файла содержит только одну запись, ключевое поле которой не совпадает с К_доступ. Делается вывод об отсутствии нужной записи в файле.

Дата добавления: 2014-01-15