Практическое занятие №6: ключевые поля, индексы, связи

Физическое хранение без порядка

В реляционной СУБД кортежи таблицы хранятся в неупорядоченном пространстве дисковых страниц (Heap / Куча):

• Новые строки записываются в первое попавшееся свободное место страницы.
• Физический адрес строки задается координатой TID (Block, Offset).
• Без специальных указателей найти конкретную запись можно лишь сплошным чтением всех страниц.

Определение и физическая суть

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

• Позволяет сократить чтение с миллионов блоков до 3–4 страниц.
• Снижает алгоритмическую сложность выборки с O(N) до O(log N).
• Обеспечивает принудительный контроль бизнес-ограничений (уникальность).

Почему именно B-Tree?

B-Tree (Balanced Tree) — основной тип индекса в реляционных базах данных благодаря трем физическим свойствам:

• Строгая сбалансированность: Все листья находятся на абсолютно одинаковом расстоянии от корня.
• Огромный Fan-out (ветвление): В блоке 8 КБ помещаются сотни ключей, поэтому при глубине всего в 3 уровня адресуются сотни миллионов строк.
• Двусвязный список листьев: Листовые блоки сцеплены вперед и назад указателями.

Маршрутизация от корня к листу

1. Корневой узел: Считывается корневая страница, определяется ветвь диапазона (например, 0 \le K < 50$).
2. Внутренний узел: Считывается промежуточный узел, уточняется указатель на листовой блок.
3. Листовой узел: Бинарным поиском внутри 8 КБ блока локализуется точный ключ и берется TID.
4. Выборка из кучи: Точечное чтение ровно одной страницы данных таблицы с диска.

Уникальные индексы (UNIQUE)

CREATE UNIQUE INDEX idx_u ON T (code);

• Гарантируют уникальность значений в масштабе всей таблицы.
• Создаются автоматически для PRIMARY KEY и ограничений UNIQUE.
• Требуют обязательной проверки коллизий при каждой вставке (Unique Constraint Overhead).
• Идеальны для паспортов, ИНН, трек-номеров, email.

Лексикографический порядок сортировки

Индекс CREATE INDEX idx_abc ON T (A, B, C); физически упорядочивает записи как в энциклопедическом словаре:

• Строки упорядочены строго по A.
• При одинаковых A — по B.
• При одинаковых A и B — по C.

Селективность (Cardinality / Total Rows)

Определяет, какую долю строк отсекает условие фильтрации:

• Высокая селективность (~1.0): id клиента, номер телефона, email — отсекают 99.99% таблицы.
• Низкая селективность (<0.05): пол, флаг активности, статус заказа.

Кластеризованный индекс (Clustered)

• Сама таблица физически упорядочена на диске по ключу индекса.
• Листья B-Tree содержат реальные данные всех колонок строки.
• У таблицы может быть только один кластеризованный индекс.
• Примеры: InnoDB в MySQL (всегда PK), MS SQL Server (по умолчанию PK).

Почему индекс на FK жизненно необходим?

1. Ускорение JOIN: Соединение таблиц по FK выполняется через мгновенный Index Scan вместо многократного Seq Scan.
2. Предотвращение Table Lock: При удалении или обновлении строки родителя (DELETE FROM clients) СУБД без индекса на FK блокирует всю дочернюю таблицу целиком для проверки ссылок.

Оптимизация асимметричных данных

Когда в таблице из 10 000 000 строк активными являются лишь 1% записей, индексировать всю таблицу — преступление.

CREATE INDEX idx_active_orders ON orders (client_id, created_at) WHERE status = 'ACTIVE';

• Индексируются только строки, удовлетворяющие условию WHERE.

Ключевые типы узлов сканирования

• Seq Scan — последовательное чтение всей таблицы от начала до конца.
• Index Scan — прямой поиск по B-Tree с последующим точечным извлечением строк из кучи.
• Index Only Scan — идеальный случай (покрывающий индекс): все запрошенные поля есть в индексе, куча не читается вообще!
• Bitmap Index Scan — сбор битовой карты страниц по индексу при выборке сотен строк.