Реализация индексов j

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

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

1.2 Архитектура СУБД

в этом разделе кратко описываются структуры типичной системы управления БД. р£1ссмат1эииаются обработка запросов пользователя с помощью СУБД н другие операиии БД. а также проблемы, связанные с проектированием СУБД, способных управлять б0льши.ми массивами данных и поддерживать высокую скорость обработки запросов. Технология реализаш1и СУБД не является темой данноП книги; мы сосредоточимся на проектировании и эффективном использовании БД.

1.2.1 Обзор компонентов СУБД

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

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

Модификадви схемы

Запросы

Менеджер транзакций

Данные Метаданные

Модификации Ри . 1.1. Главные компонента СУБД

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

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

В верхней части рис. 1.1 находятся три типа обращения СУБД:

1. Запросы - вопросы по поводу данных, которые генерируются двумя способами:

a) с помощью общего интерфейса запросов; например, реляционная СУБД позволяет печатать запросы SQL, передаваемые процессору запросов, и получать на них ответы;

b) с помощью интерфейсов прикладных программ Типичная СУБД позволяет писать прикладные программы, которые через вызовы СУБД запрашивают БД. Например, агент, применяющий систему резервирования авиабилетов, запускает программу, запрашивающую БД о наличии свободных мест иа рейсы. Запросы передаются через специальный интерфейс, который может содержать боксы, заполняемые названиями городов, указаниями времени и т.д Через этот интерфейс нельзя посылать произвольные запросы, ио все же проще отправить подходящий запрос через такой интерфейс, чем писать его непосредственно в SQL.

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

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

1.2.2 Менеджер памяти

в простых системах БД менеджером памяти может быть просто система файлов базовой операционной сисгсмы. Однако для повышения эфф<;ктивности СУБД обычно осущестапяет прямой контроль памяти, по крайней мере в определенных условиях. Менеджер памяти состоит из двух компонентов: менеджера буферн и менеджера файлов.

1. Менеджер <}ю11Лов контролирует расположение файлов на диске и получает блок или блоки, содержащие файлы, по запросу менеджера буфера. Напоминаем, чго диск в общем случае делится на дисковые блоки - смежные области памяти, содержащие большое число байтов, возможно 502 512 или 25 140 (от 4000 до 16 000 байт).

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

1.2.3 Менеджер запросов

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

Пример 1.2. Предположим, что банк имеет БД с двумя отношениями:

1. Customers - таблица, приписывающая каждому клиенту имя, номер страхового полиса и адрес.

2. Accounts - габлиия, приписывающая каждому счету номер, баланс и номер страхового полиса владельца. Заметим, что каждый счет имеет главного владельца, чей номер страхового полиса используется при иалогообложс-(И1и: могут быть н другие владельцы счета, но о них не>1ьзя узнать из двух упомянутых отношений.

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