Многоуровневые индексы

По способу своей организации индексы разделяются на одноуровневые и многоуровневые. Разбиение некоторого индекса на несколько уровней производится для дальнейшего увеличения скорости поиска записей при увеличении числа записей в индексируемой таблице. Число записей в самом индексе и, следовательно, размер индексного файла, может быть настолько большим, что операция открытия индекса и поиск в нем может занимать значительное время. Бинарный поиск требует приблизительно log₂b_i обращений к индексу, ссылающемуся на b_i блоков данных. Если разбить такой индекс на блоки записей одинаковой длины и включить в дополнительный уровень только значения первых записей полученных блоков и соответствующие указатели на эти блоки, то общее число обращений к индексу значительно сократиться. Количество обращений к индексу уже будет log_fs b_i, где fs это число записей в блоке индекса первого уровня. В такой схеме второй уровень будет являться первичным индексом для первого уровня, как представлено на рис. 4.4

Рис. 4.4. Структура многоуровневого индекса

Составные индексы

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

Ускорение поиска достигается опять возможностью применения быстрых алгоритмов поиска для всех полей составного индекса (вследствие их упорядоченности). В большинстве систем существует одно ограничение на использование составного индекса, а именно только последнее условие (т.е. сравнение с последним полем индекса) может быть неравенством. Например, Страна = ‘Беларусь’ And Город = ‘Минск’ And Предприятие <‘С’.

Хэширование данных

Хэширование – это метод прямого доступа к конкретной записи по значению её первичного ключа или некоторого поля.

Метод хэширования состоит в следующем:

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

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

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

Рассмотрим еще более простой пример использования подобной функции. Пусть имеются номера поставщиков S100, S200, S300, S400, S500 и для каждой записи поставщика отводится целая отдельная страница. Применяем следующую хэш-функцию:

хэш-адрес (т.е. номер страницы) = остаток от деления числовой части номера поставщика на число 13.

В результате вычислений получали для наших пяти поставщиков соответствующие значения: 9, 5, 1, 10, 6. То есть записи поставщика с номером S100 назначается страниц с номером 9, а с номером S500 – страница с номером 6.

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

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

Другой недостаток метода состоит в том, что всегда имеется возможность коллизий, т.е. получение одинакового хэш-адреса для различных записей, имеющих различные первичные ключи. Избежать этого недостатка можно следующим образом. Требуется взять вычисленный хэш-адрес в качестве отправной точки для просмотра всех записей, имеющих одинаковый хэш-адрес, и увязать в цепочку все такие записи. Такой подход позволяет по хэш-адресу найти одну из записей, а далее по цепочке среди многих записей с одинаковым хэш адресом найти требуемую запись с заданным первичным ключом. Цепь записей можно просто заменить их последовательным расположением, тогда не потребуются и ценные адреса. Например, если хэш-адресом является номер страницы, и на странице может разместиться несколько (p) записей, то p+1 запись и последующие записи будут размещаться на странице переполнения, для чего потребуется ещё одна операция ввода-вывода.

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

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

Этот метод требует соблюдения следующего условия: поле записи должно содержать уникальные значения, т. е. по сути быть первичным ключом. Заметим, что это не сильное требование.

Рассмотрим кратко расширяемый метод хэширования.

1. Пусть h(k) – хэш-функция от некоторого значения k, первичного ключа записи r. В результате использования этой функции мы получаем хэш-значение s=h(k), называемое псевдоключом записи r.Псевдоключи применяются для косвенного поиска адресов хранения, как описано ниже.

2. Файл имеет связанный с ним каталог, который также хранится на диске. Каталог включает 2^d указателей, где d – глубина (заголовок) каталога. Указатели указывают на страницы с записями, т. е. имеется 2^d страниц.

3. Ведущие d битов псевдоключа можно рассматривать как двоичное число σ, тогда указатель в каталоге (1 ≤ i ≤ 2^d) указывает на страницу, содержащую все записи с σ = i – 1. Чтобы найти запись с первичным ключом k, необходимо хэшировать k для определения псевдоключа s и взять первые d битов этого псевдоключа; если первые биты этого псевдоключа имеют значение i-1, осуществляется переход к i-му указателю в каталоге (первое обращение к диску) и далее переход по этому указателю к странице с требуемой записью (второе обращение к диску). Каталог обычно делают небольшим для того, чтобы он хранился в оперативной памяти. Поэтому требуется лишь одно обращение к диску для получения записи.

4. Каждая страница с данными также имеет заголовок с указанием локальной глубины p этой страницы (p≤d). Предположим d=3 и первый указатель в каталоге (000) указывает на страницу с глубиной p=2. Локальная глубина 2 означает, что эта страница содержит все записи с псевдоключами, начинающиеся с 00 (а именно, с 000 и с 001).

5. Предположим, что на страница с данными 000 заполнена нужно вставить новую запись, псевдоключ который начинается с 000 (или 001). В этом случае указанная страница разделяется на две: из пула свободных страниц берется новая, пустая страница, а все записи 001 изымаются из старой страницы и переносятся в новую. Указатель 001 в каталоге корректируется так, чтобы он указывал на новую страницу (указатель 000 указывает на струю страницу). Теперь локальная глубина для этих двух страниц будет равна 3, а не 2.

6. Теперь допустим, что страница с начальной строкой битов 000 снова заполнена и должна быть опять разделена. Существующий каталог не позволяет такого разделения, так как p=d=3. Поэтому размера каталога удваивается, т. е. значение d увеличивается на единицу и каждый указатель заменяется парой смежных указателей. Теперь страница разделяется на две: записи 0000 остаются на строй странице, а записи 0001 перемещаются на новую страницу (первый указатель в каталоге остается неизменным и указывает на струю страницу, а второй указатель корректируется таким образом, чтобы он указывал на новую страницу). Операция удваивания размера каталога не требует больших затрат времени.

Упражнения

1. Дайте определение СУБД.

2. Перечислите основные операции CУБД.

3. Перечислите три основные операции СУБД, отвечающие за поиск данных.

4. Зарисуйте структурную схему СУБД и поясните назначение каждого блока.

5. Дайте классификацию СУБД.

6. Перечислите признаки, по которым можно различать СУБД.

7. Сформулируйте назначение индексов в БД.

8. Представьте схематично структуру первичного индекса.

9. Представьте схематично структуру вторичного индекса.

10. Для чего используются многоуровневые индексы.

11. Поясните, почему скорость поиска с использованием первичного индекса является наибольшей.

12. Чем отличается составной индекс от простого.

ГЛАВА 5.ЯЗЫК ЗАПРОСОВ SQL

Структурированный язык запросов SQL (Structured Query Language) предназначен для создания запросов в реляционных базах данных. Он позволяет выполнять операции над таблицами (создание, удаление, изменение структуры) и над данными таблиц (выборка, изменение, добавление и удаление), а также производить некоторые сопутствующие операции. SQL основан на реляционном языке исчисления кортежей и является непроцедурным языком, т.е. не содержит операторов управления, организации подпрограмм, ввода-вывода и т. п. В связи с этим SQL автономно не используется, обычно он погружен в среду встроенного языка программирования СУБД. В различных СУБД состав операторов SQL может несколько отличаться. В данной главе при изложении синтаксиса мы будем придерживаться стандарта, принятого в СУБД Access.

В данной главе излагается язык запросов SQL: запросы манипулирования данными, действий, специальные запросы, определения данных, а также использование транзакций и управление доступом к данным.

Операторы языка SQL можно условно разделить на два подъязыка: язык определения данных и язык манипулирования данными. Основные операторы языка SQL представлены в таблице:

Операторы языка SQL

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

Запросы ЯМД различаются на запросы выборки, запросы действий и на специальные запросы. Результатом запроса выборки является некоторая таблица. Выходной набор может быть редактируемым, т.е. изменения, сделанные в выходном наборе, будут произведены и в таблицах, на которых основан запрос, если соблюдены определенные (различные для каждой СУБД) требования. Специальные запросы, к которым относятся запрос на объединение, запрос на создание перекрестной таблицы и некоторые другие, также возвращают таблицу как результат своего действия. Запросы действий, напротив, оказывают лишь некоторое действие над набором данных. Результат этого действия можно просмотреть, открыв соответствующие таблицы.