Организация и оптимизация доступа к данным

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

 

Стратегия буферизации, применяемая в операционных средах, не соответствует целям и задачам СУБД, поэтому для оптимизации обработки данных одной из главных задач СУБД является создание эффективной системы управления процессом буферизации.

Память, управляемая СУБД, состоит из нескольких типов буферов:

- буфера страниц данных, с которыми работает СУБД;

- буфера страниц журнала транзакций, которые отражают процесс выполнения транзакции — последовательности операций над БД, переводящей БД из одного непротиворечивого состояния в другое непротиворечивое состояние;

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

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

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

Физическая структура данных в СУБД Oracle

Единицами распределения пространства базы данных являются блоки данных, экстенты и сегменты.

При создании объекта, такого как таблица или индекс, создается сегмент этого объекта. Место для сегмента данных распределяется в одном или нескольких файлах данных, составляющих табличное пространство (слайд 15).

Сегмент объекта может размещаться лишь в одном табличном пространстве базы данных. Экстенты одного сегмента распределяются блоками данных, возможно в нескольких файлах табличного пространства: таким образом, объект может "занимать" один или несколько файлов данных. Но при этом, отдельный экстент не может находиться в нескольких файлах (слайд 16).

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

Сегменты

Сегмент - это совокупность экстентов, распределенных для специфического типа данных, и находящихся в одном и том же табличном пространстве. База данных ORACLE может содержать четыре различных типа сегментов: сегмент данных, сегмент индекса, сегмент отката, временный сегмент

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

Каждый сегмент в базе данных содержит заголовок, который описывает характеристики этого сегмента и оглавление (список) экстентов в этом сегменте.

Сегменты данных. Каждая некластеризованная таблица или кластер в БД ORACLE имеет единственный сегмент данных, содержащий все данные этого объекта.

Сегменты индекса. Каждый индекс в базе данных ORACLE имеет единственный сегмент индекса, содержащий все данные этого индекса.

Сегмент данных таблицы и сегмент индекса не обязаны размещаться в одном и том же табличном пространстве.

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

Временные сегменты. При обработке запросов ORACLE часто требует временного рабочего пространства для промежуточных этапов обработки предложения SQL. Это дисковое пространство, называемое ВРЕМЕННЫМ СЕГМЕНТОМ, распределяется автоматически.

 

Экстенты

Экстент - это смежные блоки данных, выделенные для хранения специфического типа информации. При создании объекта, такого как таблица или индекс, создается сегмент этого объекта в предназначенном табличном пространстве.

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

 

Блоки данных

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

Формат блока данных, независимо от того, содержит ли он данные таблицы, индекса или кластера, включает: Общий и переменный заголовок, Оглавление таблиц, Оглавление строк, Свободное пространство, Строки данных.

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

Оглавление таблиц содержит информацию о том, строки каких таблиц размещены в этом блоке.

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

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

Свободное пространство в блоке используется для вставки новых строк и для обновлений строк, требующих дополнительного пространства (например, при замене пустых хвостовых значений на непустые значения). Будут ли конкретные вставки действительно осуществляться в данном блоке - зависит от значения параметра управления пространством и от текущей величины свободного пространства в блоке.

20.4.4. Типы индексов (слайд 17)

- Индексы на основе В*-дерева. Аналогичные по конструкции двоичному дереву, они обеспечивают быстрый доступ по ключу к отдельной строке или диапазону строк, требуя обычно очень немного чтений для поиска соответствующей строки. Индекс на основе В*дерева имеет несколько подтипов:

- Таблицы, организованные по индексу. Это таблицы, хранящиеся в структуре В*-дерева

- Индексы кластера на основе В*-дерева. Используются не для перехода от ключа к строке, а для перехода от ключа кластера к блоку, содержащему строки, связанные с этим ключом.

- Индексы с обращенным ключом. Это индексы на основе В*-дерева, байты ключа в которых инвертированы. Это используется для более равномерного распределения записей по индексу при вводе возрастающих значений ключей. Предположим, при использовании последовательности для генерации первичного ключа генерируются значения 987500, 987501, 987502 и т.д. Поскольку это последовательные значения, они будут попадать в один и тот же блок индекса, конкурируя за него. В индексе с обращенным ключом сервер Oracle будет индексировать значения 205789, 105789, 005789. Эти значения обычно будут далеко отстоять друг от друга в индексе, и вставки в индекс будут распределены по нескольким блокам.

- Индексы по убыванию. Индексы по убыванию позволяют отсортировать данные в структуре индекса от "больших" к "меньшим", а не от меньших к большим (по возрастанию).

- Индексы на основе битовых карт. Обычно в В*-дереве имеется однозначное соответствие между записью индекса и строкой — запись индекса указывает на строку. В индексе на основе битовых карт запись использует битовую карту для ссылки на большое количество строк одновременно.

- Индексы по функции. Эти индексы на основе В*-дерева или битовых карт хранят вычисленный результат применения функции к элементам строки, а не сами данные строки.

- Прикладные индексы - индексы, которые строит и хранит приложение.

- Текстовые индексы interMedia - встроенные прикладные индексы для обеспечения поиска ключевых слов в текстах большого объема.

 

Кластеры

КЛАСТЕРЫ - это необязательный способ хранения данных таблиц. Кластер представляет собой группу таблиц, разделяющих одни и те же блоки данных, потому что они имеют общие столбцы и часто используются вместе.

Так как кластеры хранят связанные строки разных таблиц вместе в одних и тех же блоках данных, при правильном использовании кластеров достигаются два главных преимущества:

- Сокращается дисковый ввод-вывод и улучшается время доступа для соединений по кластеризованным таблицам.

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

 

Лекция 21 (DB _ l 21. ppt).

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

 

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

3. Запись базы данных – документ, который задается как набор в общем случае необязательных полей, для каждого из которых определены имя и тип. Допустимы большинство стандартных типов (так называемые «форматные» поля, задающие числовые, символьные и другие величины), а также текстовые. Текстовые поля имеют переменную длину и композиционную структуру, не имеющую прямых аналогов среди стандартных типов языков программирования: текстовое поле состоит из параграфов; параграф - из предложений; предложение - из слов. При этом идентифицируемым (адресуемым атомарным) элементом данных с точки зрения хранения будет поле, а с точки зрения поиска (атомарным семантически значимым) – слово. Вследствие этого поисковые структуры строятся в виде инвертированных файлов.

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

 

21.1. Модель организации данных системы поиска документов STAIRS

На слайде (слайд 3) приведена принципиальная схема организации данных для представления и поиска информации диалоговой системы поиска документов STAIRS (Storage and Information Retrieval System), разработанной фирмой IBM в 70-х годах. Такая структура характерна и для большинства современных АИПС.

Физическая структура БД рассматриваемой системы включает в себя четыре файла операционной системы:

- файл частотного словаря, устанавливающий соответствие между словом, встречающимся в БД, его кодом и частотой, используется при текстовом поиске;

- инверсный (инвертированный, обратный) список, содержащий для каждого слова БД список документов, его содержащих, используется при текстовом поиске;

- текстовый файл, содержащий собственно документы, используется при выдаче (просмотре) документов;

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

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

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

Система присваивает каждому документу уникальный номер. Этот номер является внутрисистемным и не связан с номерами, по которым пользователь может получить данный документ где-нибудь вне системы. В списке экземпляров, соответствующем какому-либо слову, содержатся внутрисистемные номера всех документов, в которых оно встречается. Поисковый критерий может включать требование поиска всех документов, содержащих одновременно два специфических слова. Например, можно осуществлять поиск документа, в котором содержится как слово ORANGUTANG, так и слово OSTRICH. В этом случае система находит множество документов, содержащих первое слово, а затем множество документов, содержащих второе слово, и путем их пересечения определяет множество документов, содержащих как первое, так и второе слово.

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

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

 

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