Любицкий Ю.В. Базы данных
Подождите немного. Документ загружается.
Таблица 3.2
Сведения о поставках товаров в магазин
Номер
накладной
Название
товара
Артикул Количество Дата
поставки
18 Туфли 100 120 11.12.05
80 Туфли 100 100 12.12.05
54 Сапоги 200 75 10.12.05
28 Костюм 300 20 12.12.05
74 Костюм 400 50 12.12.05
37 Костюм 500 50 10.12.05
60 Костюм 500 35 11.12.05
Полученный инвертированный список позволяет выполнять быстрый поиск
информации по данным в поле Артикул, не требуя просмотра всех записей
(например, при поиске сведений о товарах, артикулы которых менее 300,
достаточно извлечь и рассмотреть только первые четыре записи).
Обеспечивая уменьшение времени выполнения запросов, инвертирование
приводит к существенному увеличению объемов внешней памяти для хранения
информации в результате ее дублирования. Это увеличение прямо
пропорционально количеству полей, по которым производится инвертирование.
Для частичного устранения данного недостатка применяется создание индексов.
3.4. Индексы
Индексы применяются для ускорения доступа к записям базы данных. Их
можно сравнить с предметным указателем книги – упорядоченной
последовательностью слов (словосочетаний) с перечнем номеров страниц, на
которых встречается это слово (словосочетание).
Индекс базы данных представляет собой структуру, в которой содержатся
рассортированные в заданном порядке значения данных в некотором поле и
указатели адресов записей (страниц), где находятся эти значения. В отличие от
инвертированных списков индексы занимают значительно меньшее место во
внешней памяти.
Построение индекса и его обновление выполняется автоматически самой
СУБД. Файл базы данных, для которого создан хотя бы один индекс, называется
индексированным файлом.
31
Дополним табл. 3.1 сведениями о номерах страниц, на которых хранятся
записи с данными (для простоты будем полагать, что каждая запись хранится на
отдельной странице внешней памяти) (табл. 3.3):
Таблица 3.3
Сведения о поставках товаров в магазин
Номер
накладной
Название
товара
Артикул Количество Дата
поставки
Номер
страницы
37 Костюм 500 50 10.12.05 1
54 Сапоги 200 75 10.12.05 2
18 Туфли 100 120 11.12.05 3
60 Костюм 500 35 11.12.05 4
28 Костюм 300 20 12.12.05 5
74 Костюм 400 50 12.12.05 6
80 Туфли 100 100 12.12.05 7
Индекс, созданный для поля Название товара, обеспечивающий быстрый
поиск данных в этом поле, будет иметь вид (табл. 3.4):
Таблица 3.4
Индекс Товар
Название товара Номера страниц
Костюм 1, 4, 5, 6
Сапоги 2
Туфли 3, 7
Поиск и выборка нужных записей в базе данных осуществляются в
следующей последовательности:
1. Выбирается индекс, соответствующий условию поиска (например Товар,
если в запросе выполняется поиск товара с конкретным названием).
2. В индексе находится строка с заданным условием поиска (например
Туфли).
3. Из найденной строки выбираются номера страниц, где хранятся искомые
записи.
4. Полученные номера страниц используются для чтения необходимой
информации.
Большинство СУБД реализует этот процесс автоматически, без участия
пользователя.
32
Если для таблицы определены несколько индексов по отдельным полям, при
поиске записей в данной таблице по условиям поиска, заданным в этих полях,
соответствующие индексы используются совместно.
Например, для поля Дата поставки табл. 3.3 создан также индекс Дата
(табл. 3.5):
Таблица 3.5
Индекс Дата
Дата поставки Номера страниц
10.12.05 1, 2
11.12.05 3, 4
12.12.05 5, 6, 7
При выполнении запроса «Найти сведения о туфлях, поступивших 11
декабря 2005 г.», номера страниц в индексе Товар для значения данных Туфли
будут сравниваться с номерами страниц значения 11.12.05 в индексе Дата. В
результате будет выбран номер страницы, встречающийся в обоих индексах,
равный 3.
Если поиск достаточно часто производится по одним и тем же полям,
желательно создать составной индекс, включающий несколько полей. При
использовании составного индекса сокращается время поиска, так как не
приходится сравнивать значения данных из нескольких индексов.
Проиллюстрируем процесс создания индексов на примере MS Access.
Если индекс создается по одному полю, необходимо выполнить действия:
1. Открыть таблицу в режиме Конструктора.
2. Активизировать поле, для которого создается индекс.
3. Выбрать свойство поля Индексированное поле.
4. Выбрать для данного свойства одно из значений:
Да (Допускаются совпадения);
Да (Совпадения не допускаются).
Для ключевого поля индекс в MS Access создается автоматически.
Для создания составного индекса следует открыть таблицу в режиме
Конструктора, нажать кнопку Индексы на панели инструментов или
выполнить действия ВидИндексы, затем в появившемся диалоговом окне
ввести имя индекса и указать имена полей, по которым он создается.
В MS Access имеются следующие ограничения:
в таблице не может быть более 32 индексов;
33
в составном индексе не может быть более 10 полей.
Индексы могут быть плотными, когда в них содержатся указатели на все
записи индексированной таблицы, и неплотными – указатели создаются для
блоков, включающих наборы записей. Детальная характеристика и примеры
указанных понятий приводятся в работах [ 2, 4 ].
Для больших таблиц сами индексы могут занимать несколько страниц во
внешней памяти. В таких ситуациях создаются многоуровневые индексы,
например, в виде сбалансированных деревьев (B-дерево или Balanced-tree),
имеющих иерархическую структуру [ 2, 4 ]. Целью создания B-дерева является
ускорение поиска, стремление избежать просмотра всего индекса.
Рассмотрим процесс построения B-дерева на простом примере.
Предположим, таблица сведений о поставках товаров в магазин включает 18
записей и индексируется по номерам накладных: 18, 28, 37, 54, 59, 60, 61, 67, 68,
70, 77, 80, 83, 91, 93, 96, 98, 99. На каждой странице в памяти содержатся только
два адреса (фактически их может быть больше).
Размещаем на корневой странице дерева значения данных в поле Номер
накладной, равные 60 и 82, и три указателя (рис. 5). Данные со значениями в
поле Номер накладной, меньшие или равные 60, могут быть найдены с
помощью левого указателя; бóльшие 60 и меньшие или равные 82 – с помощью
среднего указателя; бóльшие 82 – с помощью правого указателя (см. рис. 5).
Другие страницы индекса интерпретируются аналогичным образом.
На нижнем уровне B-дерева находится множество страниц с указателями на
страницы, где хранятся данные (см. рис. 5).
Для нахождения с помощью B-дерева адреса размещения во внешней памяти
любой страницы с данными, достаточно последовательно рассмотреть только
три страницы индекса (на рис. 5 жирными стрелками указан маршрут поиска
страницы с номером накладной 77), что существенно меньше общего количества
страниц с данными.
34
указатели на страницы, где находятся данные
Рис. 5. Индекс в виде B-дерева
Реальные данные, для которых строится многоуровневый индекс, часто не
позволяют непосредственно получить сбалансированное дерево, построенное на
рис. 5. В таких случаях для его создания применяются специальные алгоритмы,
рассмотренные, например, в работе [ 2 ].
Недостатком индексирования является необходимость выделения во
внешней памяти дополнительного места для хранения индексов. Существуют
оценки, что файл, в котором созданы индексы для всех полей размещенной в
нем таблицы, занимает практически вдвое больше места на внешнем носителе по
сравнению с исходным файлом [ 12 ]. Кроме того, наличие индексов затрудняет
обновление информации, хранящейся в базе данных, и требует дополнительных
затрат времени на данный процесс.
Поэтому не рекомендуется индексировать все поля таблиц или поля, данные
в которых часто изменяются. Наиболее эффективным является создание
индексов для первичных и внешних ключей, для полей, по которым в основном
выполняются запросы.
3.5. Хеширование
Хеширование (Hashing) – алгоритмическое преобразование значений
некоторого поля записей (первичного ключа или любого другого поля) в адреса
их размещения на внешнем носителе.
При вводе данных СУБД вычисляет адрес страницы, на которой будет
храниться запись, и заносит запись на эту страницу. При выполнении запросов
35
60 82
29 54
67 75
91 97
18 28
37 54
59 60
61 67
68 70
77 80
83 91
93 96
98 99
реализуются аналогичные расчеты адреса страницы с последующим чтением
записей с этой страницы. Достоинством такого метода является быстрый прямой
доступ к данным. При этом время доступа практически не зависит от количества
хранимых записей.
Рассмотрим технологию хеширования на примере данных, приводимых в
табл. 3.1. Используем для вычисления адресов страниц значения данных в поле
первичного ключа таблицы Номер накладной: 18, 28, 37, 54, 60, 74, 80.
Предположим, что на каждой странице внешней памяти можно разместить
только одну запись.
Номера накладных представляют собой целые двузначные числа. Поэтому
если использовать номера накладных в качестве адресов страниц, для
организации хранения информации потребуется 99 страниц с адресами от 01 до
99. Очевидно, что это нерационально, так как записей в исходной таблице всего
семь и абсолютное большинство страниц останутся пустыми (приводимые
рассуждения будут более убедительными, если значения данных, используемые
для хеширования, пятизначные или шестизначные числа).
По указанной причине адреса страниц вычисляются с помощью специальной
хеш-функции. Используем в качестве адресов страниц остаток от деления
каждого значения номера накладной на простое натуральное число (например,
11), называемое сверткой ключа (обычно хеш-функции имеют более сложный
вид) (табл. 3.6):
Таблица 3.6
Сведения о поставках товаров в магазин
Номер
накладной
Название
товара
Артикул Количество Дата
поставки
Адрес (номер
страницы)
37 Костюм 500 50 10.12.05 4
54 Сапоги 200 75 10.12.05 10
18 Туфли 100 120 11.12.05 7
60 Костюм 500 35 11.12.05 5
28 Костюм 300 20 12.12.05 6
74 Костюм 400 50 12.12.05 8
80 Туфли 100 100 12.12.05 3
С помощью выполненного хеширования записи размещаются на семи
страницах внешней памяти с адресами от 00 до 10.
Рассмотренный пример иллюстрирует и недостатки хеширования:
36
1. Страницы с записями во внешней памяти могут располагаться
неравномерно, с различным количеством пустых страниц между ними.
2. Возможно совпадение рассчитанных адресов страниц для двух или
нескольких записей (например адреса, вычисленные для номеров накладных 18,
29, 40, будут равны одному числу – семи).
Совпадение вычисленных адресов называется коллизией, значения данных,
для которых получены одинаковые адреса – синонимами.
Существует много стратегий разрешения коллизий, но основные из них две:
а) с областью переполнения;
б) свободного замещения.
Стратегия разрешения коллизий с помощью области переполнения
Область хранения разбивается на две части: основную область и область
переполнения (рис. 6).
При вводе в базу данных новой записи вычисляется значение хеш-функции,
которое используется для определения места расположения страницы в
основной области памяти. Например, если номер накладной равен 12, запись
будет размещена на странице с адресом 1 (см. обозначения курсивом на рис. 6).
Когда страница с полученным адресом занята и возникает коллизия, новая
запись заносится на первое свободное место в области переполнения. Например,
запись с номером накладной 29, следовательно, значением хеш-функции,
равным 7, будет размещена по адресу 500. В записи-синониме, которая
находится в основной области, делается ссылка на адрес записи, размещаемой в
области переполнения. В ситуациях повторения коллизий (номер накладной
равен 40, значение хеш-функции – 7) вновь вводимая запись помещается на
свободное место в области переполнения (например, если страница с номером
501 занята, по адресу 502). Она становится второй в цепочке синонимов (этим
обеспечивается сокращение времени на размещение новых записей) с помощью
изменения ссылок на адреса синонимов (см. рис. 6).
При поиске нужной записи вычисляется значение ее хеш-функции,
указывающее на адрес страницы в основной памяти. Если эта запись не является
искомой, последовательно просматривается цепочка синонимов до получения
необходимого результата. Очевидно, что скорость поиска существенно зависит
от длины цепочки синонимов. Считается, что в цепочке не должно быть более 10
синонимов [ 4 ].
При удалении записи в основной области памяти на ее место перемещается
вторая запись в цепочке синонимов, при этом все ссылки на синонимы в цепочке
37
сохраняются. Если удаляется запись в области переполнения, изменяется адрес
ссылки на следующий синоним в записи, предшествующей удаляемой записи.
Основная область
Адрес
(номер
страницы)
Номер
накладной
Название
товара
Арти-
кул
Коли-
чество
Дата
поставки
Ссылка
на
синонимы
0
1 12 Сапоги 150 150 13.12.05
2
3 80 Туфли 100 100 12.12.05
4 37 Костюм 500 50 10.12.05
5 60 Костюм 500 35 11.12.05
6 28 Костюм 300 20 12.12.05
7 18 Туфли 100 120 11.12.05 502
8 74 Костюм 400 50 12.12.05 501
9
10 54 Сапоги 200 75 10.12.05
Область переполнения
Адрес
(номер
страницы)
Номер
накладной
Название
товара
Арти-
кул
Коли-
чество
Дата
поставки
Ссылка
на
синонимы
500 29 Брюки 750 90 13.12.05
501 96 Сапоги 220 120 13.12.05
502 40 Костюм 300 35 14.12.05 500
503
504
505
Рис. 6. Пример хеширования с областью переполнения
38
Стратегия разрешения коллизий с помощью свободного замещения
В рамках данной стратегии память не разделяется на отдельные области.
Если в базу данных вводится новая запись и значение хеш-функции
соответствует адресу пустой страницы, запись помещается на этой странице и
становится первой в цепочке синонимов. Когда возникает коллизия, новая
запись размещается на первом свободном месте в памяти. С помощью ссылок
создается цепочка синонимов, при этом используются те же принципы, что и в
стратегии с областью переполнения.
Технологии поиска и удаления записей в обеих стратегиях также
аналогичны.
При реализации стратегии разрешения коллизий с помощью свободного
замещения может возникнуть ситуация, когда запись, размещаемая на первой
свободной странице в памяти, занимает место, на которое позднее будет
претендовать запись, значение хеш-функции которой соответствует адресу этой
страницы. В такой ситуации запись, занимающая свое место «незаконно»,
перемещается на другую страницу, при этом изменяются ссылки в цепочке
синонимов.
Основной проблемой хеширования является сложность выбора оптимальной
хеш-функции. При выполнении данной работы анализируются размеры записей
и страниц внешней памяти, вероятное распределение получаемых адресов.
Неудачно выбранная хеш-функция может вызвать неравномерное распределение
записей в памяти или формирование слишком длинных цепочек синонимов.
Весьма сложной является ситуация, когда количество запоминаемых записей
больше, чем предполагалось, и необходимо увеличить место в памяти для их
хранения или размеры таблицы хеширования. В этой ситуации потребуется
выполнить полное повторное хеширование.
Следует иметь в виду, что хеширование позволяет организовать быстрый
поиск информации только по одному полю, данные которого использовались
для хеширования. Нельзя хранить записи в порядке, определяемом несколькими
хеш-функциями.
Несмотря на отмеченные недостатки хеширования, данный способ
организации хранения и быстрого извлечения необходимых данных широко
применяется, в первую очередь в объектно-ориентированных базах данных [
12 ].
39
3.6. Кластеризация
Кластеризация использует принцип близкого размещения во внешней
памяти логически связанных данных. Этим обеспечиваются быстрый поиск и
извлечение необходимой информации.
Физически кластеризация достигается размещением логически связанных
записей на одной странице (если сделать это позволяют размеры страниц и
записей) или на страницах, расположенных рядом. Если из таблицы Сведения о
поставках товаров в магазин часто извлекаются сведения для товаров с
одинаковыми названиями, а на каждой странице во внешней памяти
размещаются две записи, структура хранения может иметь вид (табл. 3.7):
Таблица 3.7
Сведения о поставках товаров в магазин
Номер
накладной
Название
товара
Артикул Количество Дата
поставки
Номер
страницы
37 Костюм 500 50 10.12.05 1
60 Костюм 500 35 11.12.05 1
28 Костюм 300 20 12.12.05 2
74 Костюм 400 50 12.12.05 2
54 Сапоги 200 75 10.12.05 5
18 Туфли 100 120 11.12.05 9
80 Туфли 100 100 12.12.05 9
В результате из множества страниц формируются блоки, называемые
кластерами, в каждом из которых хранятся записи с одинаковыми названиями
товаров.
Новая запись, вводимая в базу данных, должна быть размещена в
конкретном кластере. Этот процесс может быть выполнен на уже имеющейся
странице (в рассматриваемом примере, если товар называется Сапоги, на
странице с номером 5) или при отсутствии на ней свободного места, на странице
физически наиболее близкой (товар Костюм – на странице с номером 3).
Для кластеризированных таблиц можно создать неплотные индексы (см. п.
3.4) с указателями на первые записи, входящие в каждый кластер (блок).
Рассмотренный способ кластеризации реализуется для одного логического
объекта (файла) базы данных. Такая кластеризация называется внутрифайловой
[ 2 ]. Иногда применяется межфайловая кластеризация, когда на одной
странице во внешней памяти размещаются записи из нескольких логических
40