ОП.08 Основы проектирования баз данных — Тема 3. Этапы проектирования баз данных — Практическое занятие №6 (Занятие №18)
В реляционной теории отношения математически не имеют определенного порядка строк (множество кортежей неупорядочено). На физическом уровне данные таблицы хранятся на диске в виде страниц (блоков размером от 8 КБ до 64 КБ) в так называемой куче (Heap), куда новые строки записываются в свободные пространства без какой-либо сортировки.
Если таблица содержит 10 000 000 строк и не имеет индексов, то выполнение простейшего запроса:
SELECT * FROM clients WHERE passport_number = '4510 123456';вынуждает СУБД выполнить последовательное сканирование (Sequential Scan, Seq Scan) — прочитать с накопителя абсолютно все страницы таблицы от первой до последней, проверить каждую запись в памяти процессора и отбросить неподходящие. При размере таблицы в десятки гигабайт это занимает десятки секунд и блокирует дисковую подсистему ввода-вывода.
Наиболее распространенным и универсальным типом индекса в мире реляционных баз данных является B-Tree (сбалансированное дерево). Его листовые страницы содержат отсортированные ключи и указатели на данные, а внутренние узлы направляют поиск от корня к нужному листу.
< 50, 50..100, > 100. Значение 25 меньше 50, поэтому СУБД переходит по первому левому указателю.[20 | 35]. Значение 25 попадает в диапазон между 20 и 35 (0 \le 25 < 35$). СУБД переходит по среднему указателю на листовую страницу.[20, 25, 30]. Методом бинарного поиска внутри блока процессор мгновенно находит точное совпадение ключа 25 и извлекает физический указатель строки: TID = (блок 7, позиция 3).Оптимизатор запросов СУБД (Query Optimizer) при получении любого SQL-запроса выполняет стоимостную оценку (Cost-based Optimization). Стоимость измеряется в условных единицах дискового ввода-вывода (где 1.0 — чтение одного блока данных последовательно, а 4.0 — случайное чтение блока).
| Параметр сравнения | Seq Scan (Последовательное сканирование) | Index Scan (Поиск по индексу B-Tree) |
|---|---|---|
| Характер чтения диска | Последовательный (Sequential I/O). Диск читает блоки подряд на максимальной скорости. | Случайный (Random I/O). Чтение разрозненных страниц индекса и кучи. |
| Эффективен при выборке | Более 10–20% от общего числа строк таблицы (высокая доля возвращаемых строк). | Менее 1–5% от общего объема таблицы (точечный или узкодиапазонный поиск). |
| Зависимость времени от размера | Линейная (N)$. С ростом таблицы время растет прямо пропорционально. | Логарифмическая (\log N)$. При росте таблицы в 100 раз время поиска почти не меняется. |
| Сортировка данных | Требует дополнительной фазы тяжелой сортировки в оперативной памяти (Sort). | Данные возвращаются уже упорядоченными по ключу индекса без затрат CPU. |
WHERE пол = 'M'), использование индекса приведет к чудовищной деградации, так как миллион случайных обращений к диску (Random I/O) медленнее, чем чтение всей таблицы одним сплошным потоком. В таких случаях СУБД осознанно выбирает Seq Scan!
Составной индекс (Composite Index) строится по двум или более колонкам: CREATE INDEX idx_name ON table (col1, col2, col3);.
Селективность определяется долей уникальных значений в столбце по отношению к общему числу строк:
1105862\text{Селективность} = \frac{\text{Количество уникальных значений (Cardinality)}}{\text{Общее число строк таблицы}}1105862Порядок полей в составном индексе определяет, сможет ли запрос использовать его эффективно:
=) с наибольшей селективностью.>, <, BETWEEN, LIKE 'abc%').ORDER BY).
Внешний ключ связывает дочернюю таблицу с родительской. Однако многие разработчики забывают, что СУБД НЕ создает индекс на FK автоматически.
DELETE FROM clients WHERE id = 100), СУБД обязана проверить, нет ли дочерних заказов этого клиента. Без индекса на orders.client_id СУБД накладывает разделяемую блокировку на всю таблицу orders и запускает Seq Scan по миллионам строк. В этот момент все кассиры и клиенты не могут оформить ни одного нового заказа!B-Tree является самобалансирующимся деревом. При добавлении данных переполненный узел расщепляется ровно пополам, выталкивая медианный ключ на уровень выше. Рост дерева происходит строго снизу вверх от корня, что обеспечивает постоянную глубину всех листьев и гарантию поиска за (\log N)$.
Функционально уникальный индекс запрещает дублирование значений, выполняя обязательную проверку уникальности (Unique Check) при каждой операции вставки. Неуникальный индекс допускает хранение множества одинаковых ключей, связывая их с разными идентификаторами строк (TID).
Нет, не будет (либо будет использоваться неэффективно через полное сканирование индекса). Согласно правилу левого префикса, поиск по B-Tree требует обязательного наличия ведущей колонки индекса (A). Без колонки A дерево не может локализовать ветку поиска.
Каждый созданный индекс ускоряет операции чтения (SELECT), но напрямую замедляет операции модификации данных (INSERT, UPDATE, DELETE), так как любая вставка строки в таблицу требует синхронного добавления ключей во все существующие индексы таблицы, что порождает дисковый ввод-вывод и риск расщепления страниц.