Почему поиск по первичному ключу (Primary Key) выполняется быстро?

Высокая скорость операций с первичным ключом (PK) обеспечивается за счет того, что СУБД автоматически создает для него индекс. Конкретная реализация зависит от движка:

• В InnoDB (MySQL): PK является кластеризованным индексом (clustered index). Это означает, что сами строки таблицы физически упорядочены на диске в порядке возрастания PK. Поиск по PK превращается в быстрое перемещение по B+-дереву индекса, которое сразу приводит к нужной строке данных.
• В других СУБД (PostgreSQL, SQL Server): PK создает уникальный индекс, который может быть кластеризованным или нет. В любом случае, это сбалансированное дерево (B-дерево или его вариация), обеспечивающее логарифмическую сложность поиска O(log n).

Ключевые причины производительности:

1. Индексирование: Поиск происходит по оптимизированной древовидной структуре, а не путем полного сканирования таблицы (full table scan).
2. Уникальность: Оптимизатору не нужно проверять данные после нахождения первой совпадающей записи.
3. Использование в JOIN: PK часто используется для соединений (например, FOREIGN KEY ссылается на PRIMARY KEY), и наличие индекса критически важно для скорости таких операций.

Пример в MySQL:

-- InnoDB автоматически создаст кластеризованный индекс по полю `id`
CREATE TABLE users (
    id INT UNSIGNED AUTO_INCREMENT PRIMARY KEY, -- Быстрый PK
    email VARCHAR(255) UNIQUE NOT NULL,         -- Уникальный, но некластеризованный индекс
    name VARCHAR(100)
);

-- Этот запрос будет максимально эффективен
EXPLAIN SELECT * FROM users WHERE id = 100;
-- В выводе EXPLAIN увидим: `type = const` или `type = eq_ref`, `key = PRIMARY`

Для максимальной эффективности PK должен быть:

• Узким: Предпочтительны типы INT, BIGINT, UUID (в бинарном виде). Широкие ключи (например, VARCHAR(255)) увеличивают размер индекса.
• Неизменяемым: Изменение значения PK ведет к физическому перемещению строки (в кластеризованном индексе), что дорого.
• Последовательным: Использование AUTO_INCREMENT или SEQUENCE уменьшает фрагментацию данных при вставках, в отличие от случайных значений (например, UUID).