Инвертированные списки

Cтраница 2

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

Создавая файл с несколькими ключами для обслуживания широкого класса произвольно поступающих запросов к данным, разработчик должен понять, для каких именно атрибутов объектов следует вводить индексирование. Желательно, конечно, избегать слишком больших индексов. Разработчик может предпочесть индексировать атрибуты с небольшим набором значений, чтобы соответствующие им инвертированные списки были невелики. К сожалению, атрибуты с небольшим числом значений на практике мало избирательны. Например, в библиотечной системе значение атрибута беллетристика соответствует половине стоящих на полке книг, так что индекс с одним этим значением оказывает очень слабую помощь. Наоборот, атрибуты, обеспечивающие выдачу небольшого числа элементов на запрос, требуют большого числа индексируемых значений. [17]

Записи файла упорядочены по основному ключу, но при этом экземпляры других ключей этих записей расположены произвольно. Для доступа к записям по дополнительным ключам используются индексы. Такая организация дополнительных индексов носит название инвертированных списков. Если каждому значению ключа и каждому адресу записи файла поставить в соответствие вершину графа, то инвертированные списки в дополнительном индексе и будут реализовать ту графовую структуру, которая, как говорилось ранее, присутствует в физической организации файла с несколькими ключами. [18]

В системе возможно два доступа к записям БД: последовательный и прямой. Последовательный доступ бывает: физическим; логическим. Физический последовательный доступ выполняется по возрастанию внутрисистемных номеров записей. Логический последовательный доступ выполняется по возрастанию значений любого дескриптора и обеспечивается наличием в системе соответствующих инвертированных списков. Система управления базами данных, анализируя инвертированные списки, определяет внутрисистемные номера записей, удовлетворяющих условию поиска, формирует с помощью адресного конвертера их физические адреса и выполняет обращение к области данных. [19]

Состав набора системных файлов СУБД МИРИС. [20]

В системных файлах представлена управляющая информация. Состав системных файлов показан на рис. 9.16. В файле системного словаря представлены схемы файлов и подсхемы. В системном журнале хранится информация об изменениях, проводимых в БД. Эта информация используется при необходимости восстановлений базы данных. Данные, хранимые в базе, представлены набором пользовательских файлов. Каждый пользовательский файл физически разделен на две области: ассоциатор и область данных. В ассоциаторе содержится вся служебная информация, необходимая для определения адреса расположения записи в области данных, а также инвертированные списки для каждого заданного при описании файла дескрипторного поля. Любому уникальному значению дескриптора в инвертированном списке соответствует набор номеров записей, в которых встретилось это значение дескриптора. С помощью специального адресного конвертора, содержащего один указатель на каждую запись, выполняется преобразование номера записи в ее физический адрес в области данных. Если запись требуется переместить в области данных, то изменению подлежит только значение указателя записи в адресном конвертере. [21]

На внутреннем уровне компонентами базы являются накопитель, ассоциатор и рабочий набор. Накопитель представляет собой пространство памяти для размещения записей файлов. Информация о свободной памяти накопителя регистрируется в специальных таблицах. Записи размещаются в блоках набора данных накопителя фиксированного размера. Каждый блок накопителя содержит заголовок блока и хранимые записи. В заголовке указывается общая длина занятой части блока. Каждой записи, при ее первичной загрузке, система назначает внутрисистемный номер, являющийся логическим адресом записи на период ее существования в БД. Размещаемые в блоках накопители записи подвергаются сжатию. В состав ассоциатора входят: преобразователь адреса, инвертированные списки, списки связи и системные управляющие таблицы. С помощью преобразователя адреса выполняется переход от внутрисистемного номера записи к физическому адресу блока накопителя, в котором хранится эта запись. [22]

Страницы: 1 2