Введение в базы данных Ограничения, присущие файловым системам

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

ID кортежа	Отношение «Сотрудники»
	Таб.номер	ФИО
1	100200	Иванов
2	100015	Петров
3	100307	Сидоров
4	100001	Комаров
5	100308	Зимин
6	100202	Шишкин

Индекс по «Таб.номер»			Индекс по «ФИО»
100001	4		Зимин	5
100015	2		Иванов	1
100200	1		Комаров	4
100202	6		Петров	2
100307	3		Сидоров	3
100308	5		Шишкин	6

ID кортежа	Отношение «Начисления»
	Таб.номер	Месяц	Сумма
1	100	1	100
2	101	1	200
3	102	1	300
4	101	2	200
5	103	2	300
6	100	4	100
. . .	. . .	. . .	. . .
N	101	12	200

Индекс по «Таб.номер»
100	1, 6
101	2,4,N
102	3
103	5

Наиболее популярным подходом при организации индексов в базах данных является использование техники В-деревьев. Альтернативным подходом к организации индексов является использование техники хэширования. Один способ организации индексов отличается от другого, главным образом, в способе поиска ключа с заданным значением.
Поскольку при выполнении многих операций языкового уровня требуется сортировка отношений в соответствии со значениями некоторых атрибутов, то полезным свойством индекса является обеспечение последовательного просмотра кортежей отношения в диапазоне значений ключа в порядке возрастания или убывания ключей.
Индексы поддерживаются динамически, т.е. после обновления БД – добавлении или удалении записей, а также при модификации полей записи, входящих в ключ, – индекс приводится в соответствие с обновленной версией БД. Обновление индекса, естественно, занимает некоторое время (иногда, очень большое), поэтому существование многих индексов может замедлить работу БД.
Обращение к записи через индексы осуществляется в два этапа: сначала в индексной структуре находится требуемое значение атрибута и соответствующий адрес записи, затем по этому адресу происходит обращение к внешнему запоминающему устройству (ВЗУ). Индекс загружается в оперативную память целиком (или хранится в ней постоянно во время работы с БД).
Файл, содержащий логические записи, называется файлом данных, а файл, содержащий индексные записи, - индексным файлом.
Типы индексов:
- первичный индекс. Файл данных последовательно упорядочивается по по­лю ключа упорядочения, а на основе поля ключа упорядочения создается поле индексации, которое гарантированно имеет уникальное значение в каждой записи;
- вторичный индекс. Файл данных последовательно упорядочивается по неключевому полю и на основе этого неключевого поля формируется поле индексации, поэтому в файле может быть несколько записей, соответствующих значению этого поля индексации. Если в файле индексации содержится только одна запись, соответствующих каждому значению индексируемого поля, то такой индекс называют уникальным.
Для каждой таблицы БД можно одновременно поддерживать один первичный и несколько вторичных индексов, что также относится к достоинствам индексирования.
Различают также одиночные индексы и составные. Составной индекс включает два или более столбца одной таблицы.
Обычно чем больше индексов, тем больше производительность запросов к базе данных. Однако при излишнем увеличении количества индексов падает производительность операций изменения данных (вставка/изменение/удаление), увеличивается размер БД, поэтому к добавлению индексов следует относиться осторожно.
Некоторые общие принципы, связанные с созданием индексов:
- индексы необходимо создавать для столбцов по которым часто производится поиск и операции сортировки. При этом необходимо учесть, что индексы всегда автоматически создаются для столбцов, на которые накладывается ограничение primary key. Чаще всего они создаются и для столбцов с foreign key;
- индекс обязательно в автоматическом режиме создается для столбцов, на которые наложено ограничение уникальности;
- лучше всего индексы создавать для тех полей, в которых - минимальное число повторяющихся значений и данные распределены равномерно;
- если поиск постоянно производится по определенному набору столбцов (одновременно), то в этом случае, возможно, есть смысл создать композитный (составной) индекс (только в SQL Server) - один индекс для группы столбцов;
- при внесении изменений в таблицы автоматически изменяются и индексы, наложенные на эту таблицу. В результате индекс может быть сильно фрагментирован, что сказывается на производительности. Периодически следует проверять степень фрагментации индексов и дефрагментировать их. При загрузке большого количества данных иногда есть смысл вначале удалить все индексы, а после завершения операции создать их заново;
- индексы можно создавать не только для таблиц, но и для представлений (только в SQL Server). Преимущества - возможность вычислять поля не в момент запроса, а в момент появления новых значений в таблицах.
В SQL Server предусмотрено два типа индексов: кластерные и некластерные.
Кластерный индекс в таблице может быть только один. Каждый элемент индекса содержит название искомого объекта, и само значение этого объекта.
Проще всего сравнить таблицу, на которую наложен такой индекс, с телефонным справочником: все записи в данной таблице упорядочены по кластерному индексу. Относиться к выбору поля для кластерного индекса следует очень осторожно - например, если в эту таблицу часто производится вставка данных, а кластерный индекс наложен не на поле с автоприращением, то вполне может получиться так, что нам часто придется вставлять новые записи в середину таблицы. Результат - большое количество операций page split, фрагментация таблицы и, как следствие, серьезное падение производительности (за счет фрагментации и за счет того, что само по себе page split - достаточно ресурсоемкая операция. По умолчанию кластерный индекс создается для поля первичного ключа, и, учитывая это, лучше делать первичный ключ числовым полем с автоприращением.
Некластерный индекс. Каждый элемент индекса содержит название искомого объекта, а также один или несколько указателей (идентификаторов записей) на место его расположения.
Он больше всего похож на указатель в конце книги. Для таблицы можно создавать таких индексов очень много (можно даже по нескольку для каждого столбца, но большой пользы это не приносит).