Индексация в СУБД

1. Индексация в СУБД

2. Понятие индекса

Основная проблема в СУБД – это поиск нужных данных за
минимальное время
Быстрый поиск может быть выполнен в случае, если
данные отсортированы.
Сортировка данных в таблице невозможна, т.к. критериев
поиска может быть несколько.
Поэтому для таблицы с данными создаются специальные
таблицы для каждого критерия поиска, которые называются
ИНДЕКСЫ
Индекс – это структура данных для быстрого поиска
записей в таблице по значению ключа

3. Методы организации индекса

Методы организации индексов
Первичного ключа
Плотным
индексом
(некластерный
индекс)
Неплотным
индексом
(кластерный
индекс)
Индекснопрямой файл
Индекснопоследовательный файл
Вторичного ключа
Б-деревья
Инвертируемые
списки
Приведенный к
индексу РК

4. Плотный индекс

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

5. Плотный индекс

Таблица индекса
Блок 1
Блок 2
Блок 3
Блок 4
КодСотр
03
06
63
66
73
75
80
81
83
84
90
91
92
98
Номер
записи
6
5
10
4
1
2
3
12
7
11
8
9
14
13
Основная таблица
КодСотр
Фамилия
отдел
Адрес
73
Иванов
04
г.Минск …
75
Степанов
04
г.Минск …
80
Кустов
21
г.Минск …
66
Чернов
22
г.Минск …
06
Трусов
14
г.Минск …
03
Терпухов
12
г.Минск …
83
Павлов
04
г.Минск …
90
Мухина
12
г.Минск …
91
Артемьев
21
г.Минск …
63
Васильев
22
г.Минск …
84
Васильева
04
г.Минск …
81
Уваров
04
г.Минск …
98
Шишкин
21
г.Минск …
92
Удалов
22
г.Минск …

6. Плотный индекс

2-я таблица индекса
Фамилия
Блок 1
Блок 2
Блок
3
Артемьев
Васильев
Васильева
Иванов
Кустов
Мухина
Павлов
Степанов
Терпухов
Трусов
Уваров
Удалов
Чернов
Шишкин
Основная таблица
Номер
записи
9
10
11
1
3
8
7
2
6
5
12
14
4
13
КодСотр
Фамилия
отдел
Адрес
73
Иванов
04
г.Минск …
75
Степанов
04
г.Минск …
80
Кустов
21
г.Минск …
66
Чернов
22
г.Минск …
06
Трусов
14
г.Минск …
03
Терпухов
12
г.Минск …
83
Павлов
04
г.Минск …
90
Мухина
12
г.Минск …
91
Артемьев
21
г.Минск …
63
Васильев
22
г.Минск …
84
Васильева
04
г.Минск …
81
Уваров
04
г.Минск …
98
Шишкин
21
г.Минск …
92
Удалов
22
г.Минск …

7. Плотный индекс

Алгоритм поиска данных
начало
Поиск
индексного
блока
Блок
существует
Tпоиска Log 2 NIB
нет
да
Вычислить номер
блока основного файла
Считать блок
основного файла
конец
Данных нет
Tчтения 1

8. Плотный индекс

Алгоритм добавления записи
начало
Запись последнего
блока основного файла
Поиск индексного
блока
Tзаписи 1
Tпоиска Log 2 NIB
Добавление записи
в индексном блока
Запись индексного
блока
конец
Tзаписи 1

9. Плотный индекс

Алгоритм удаления записи
начало
Поиск индексного
блока
Tпоиска Log 2 NIB
Удаление записи
в индексном блока
Запись индексного
блока
Tзаписи 1
Чтение блока
основного файла
Tчтения 1
Пометить запись
на удаление в блоке
Запись блока
основного файла
конец
Tзаписи 1

10. Плотный индекс

Оценка времени на выполнение основных операций
(в максимальном количестве обращений к диску)
без использования индекса
с использованием индекса
Tпоиска
Tдобав 1
Tудал Tпоиск 1
N
Log 2 (
) 1
LB / LI
Tдобав Tпоиск 1
Tудал Tпоиск 2
где N – количество записей в основной
таблице;
LB – размер блока;
LZ- длина записи основной таблицы
где LI– длина записи в индексной
таблице;

11. Неплотный индекс

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

12. Неплотный индекс

Основная таблица
Таблица индекса
КодСотр
Блок 1
03
73
83
98
Номер
блока
1
2
3
4
Блок 1
Блок 2
Блок 2
Блок
3
КодСотр
03
06
63
66
Фамилия
Терпухов
Трусов
Васильев
Чернов
отдел
12
14
22
22
Адрес
г.Минск …
г.Минск …
г.Минск …
г.Минск …
73
75
80
81
Иванов
Степанов
Кустов
Уваров
4
4
21
4
г.Минск …
г.Минск …
г.Минск …
г.Минск …
83
84
90
91
92
Павлов
Васильева
Мухина
Артемьев
Удалов
4
4
12
21
22
г.Минск …
г.Минск …
г.Минск …
г.Минск …
г.Минск …
98
Шишкин
21
г.Минск …

13. Неплотный индекс

Алгоритм добавления записи
начало
Поиск индексного
блока
Tпоиска Log 2 NIB
Чтение блока
основной области
Tчтения 1
Добавление записи
в блоке основной
области
переполнение
да
нет
Запись блока основной
области
конец
Перестроение индекса
и основной области
Tзаписи 1
Tперестр ?

14. Неплотный индекс

Алгоритм удаления записи
начало
Поиск индексного
блока
Tпоиска Log 2 NIB
Чтение блока
основной области
Tчтения 1
Удаление записи
в блоке основной
области
Запись блока основной
области
конец
Tзаписи 1

15. Неплотный индекс

Оценка времени на выполнение основных операций
(в максимальном количестве обращений к диску)
Tпоиска
N LZ LI
Log 2 (
) 1
2
LB
Tдобав Tпоиск 1
Tудал Tпоиск 1
где N – количество записей в основной
таблице;
LB – размер блока;
LZ- длина записи основной таблицы
где LI– длина записи в индексной
таблице;

16. Индекс Б-дерево

4 уровень
NIBi
NIBi 1 LI
LB
3 уровень
2 уровень
1 уровень
1 бл.
для i >1
…
КодСотр
Номер
блока
03
73
83
98
1
2
3
4
172/73 =
3 бл.
…
12500/73 =
172 бл.
Со 2-го уровня тип индекса – неплотный индекс
…
100000
записей
12500 бл.

17. Индекс Б-дерево

Оценка времени на выполнение основных операций
(в максимальном количестве обращений к диску)
Tпоиска NLI
Tдобав Tпоиск 1
Tудал Tпоиск 1
где NLI – количество уровней индексов.

18. Инвертируемые списки

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

19. Инвертируемые списки

Индексная таблица
1-го уровня
отдел
Блок 1
4
12
14
21
Номер
блока
1
3
4
5
22
6
Индексная таблица
Основная таблица
2-го уровня
Ном.
зап. КодСотр Фамилия
отдел
2
Блок 1
уровень
21
22
24
61
62
Блок 2
Блок 2
Блок 3
1
63
1
2
3
4
03
06
63
66
Терпухов
Трусов
Васильев
Чернов
12
14
22
22
Адрес
г.Минск …
г.Минск …
г.Минск …
г.Минск …
21
22
23
24
73
75
80
81
Иванов
Степанов
Кустов
Уваров
4
4
21
4
г.Минск …
г.Минск …
г.Минск …
г.Минск …
61
62
63
64
65
83
84
90
91
92
Павлов
Васильева
Мухина
Артемьев
Удалов
4
4
12
21
22
г.Минск …
г.Минск …
г.Минск …
г.Минск …
г.Минск …
81
82
98
Шишкин
21
г.Минск …
2
Блок 4
Блок 5
23
64
81

20. Рекомендации по созданию индексов

Факторы, определяющие «хороший» индекс
- число столбцов в индексе не более 4-5 (максимум 16 столбцов общей
суммой не более 900 байт))
- в индекс включаются не часто обновляемые столбцы
- создание индексов по FK
- создание индексов по столбцам из выражения WHERE часто
выполняемых запросов
- не использовать поиски с предикатом LIKE
Факторы, определяющие «плохой» индекс
- по столбцам, входящих в индекс, не выполняются поиски строк
- слишком много столбцов в индексе
- слишком мало записей в индексируемой таблице
- слишком много индексов

21. Оператор создания индекса

СУБД всегда создает индекс для первичного ключа таблицы
Для создания индексов для других полей используется
оператор SQL
CREATE [ UNIQUE ] INDEX имя_индекса
ON имя_таблицы (имя_столбца [ ASC | DESC] [,…])
Пример. Создать индекс для таблицы ЗАКАЗ по вторичному
ключу
CREATE INDEX Заказ_FK_инд
ON Заказ (MFR, КодТов)
В каждой СУБД оператор создания индексов содержит
дополнительные предложения специфические для каждой СУБД.

22. Оператор создания индекса

Оператор для создания индексов в T - SQL
Создание уникального индекса
CREATE [ UNIDUE ]
[ CLASTERED | NOCLASTERED ] Создание неплотного или плотного
индекса
INDEX имя_индекса
ON {имя_таблицы | имя_представления}
(имя_столбца [ ASC | DESC] [,…]) По возрастанию или убыванию
WITH
[ < параметры > [ ,...n] ] ]
[ ON имя_файла_группы ] Расположение индекса в файлах ОС БД
Резервирование на каждой странице индекса
< параметры > - это
свободного пространства
{ PAD_INDEX |
FILLFACTOR = %запол. | Степень заполнения свободного пространства
IGNORE_DUP_KEY |
Поведение сервера при появлении дублей строк
DROP_EXISTING |
Поведение сервера при наличии индекса
STATISTICS_NORECOMPUTE |
…
SORT_IN_TEMPDB …
}

23. Инструмент настройки индексов

Database Engine Tuning Advisor (DTA)
DTA проводит анализ БД по файлу рабочей нагрузки (workload
file) и позволяет определить какие индексы следует поменять
или усовершенствовать.
Используется DTA через значительный интервал времени
работы БД.