Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Индексно-последовательная организация




Лекция №5: «Физические модели баз данных»

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Индексные файлы

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

Различают 2 типа файлов: индексно-прямые файлы и индексно-последовательные файлы.

Индексно-последовательная организация

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

Пусть основной файл соответствует реляционной модели для сущности кафедра из рассмотренного ранее примера и имеет вид:

кафедра

название шифр в вузе
АПП  
СУиВТ  
ТАМ  
Экономики  

 

Для этого файла N = 4. Это значит, что индекс будет иметь вид:

 

название № п/п
СУиВТ  
Экономики  

 

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

1. Кдоступ = К – запись найдена, известен ее номер в основном файле, по этому номеру она считывается из него и предоставляется пользователю, алгоритм заканчивает работу;

2. Кдоступ > К – считывается следующая запись индекса. Если индекс закончен, алгоритм заканчивает работу – запись не найдена. Иначе вновь ключевое поле К очередной записи индекса сравнивается с ключом Кдоступ; возможные варианты исхода сравнения описаны выше, начиная с п.1);

3. Кдоступ < К – обнаружен блок основного файла, который может содержать искомую запись. Выполняется переход к найденному блоку по полю индекса № п/п – к последней его записи. Все записи блока основного файла последовательно сканируются в поисках искомой записи в соответствии с рассмотренным ранее методом последовательного сканирования.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...