Ключи. Нормализация данных. Индексация данных

1. Ключи и их виды

В реляционных базах данных ключи играют важную роль в обеспечении уникальности записей и поддержании целостности данных.

Ключи — одно из основных требований к модели реляционной базы данных. Они широко используются для уникальной идентификации кортежей (строк) в таблице, а также для настройки отношений между столбцами и таблицами базы.

1.1. Потенциальный ключ

Потенциальный ключ (ключ-кандидат) — это минимальный набор атрибутов, который может однозначно идентифицировать кортеж. Его свойства:

• минимальный набор атрибутов, однозначно идентифицирующий запись;
• должен содержать уникальные значения;
• может содержать NULL-значения;
• каждая таблица должна иметь по крайней мере один потенциальный ключ;
• таблица может содержать несколько потенциальных ключей, но только один первичный ключ.

Например, в отношении STUDENT атрибут STUD_NO — ключ-кандидат: он уникально идентифицирует студентов.

Потенциальный ключ может быть простым (из одного атрибута) или составным. Составной ключ — комбинация нескольких полей, которая используется для уникальной идентификации записей. Например, в отношении STUDENT_COURSE составным ключом-кандидатом может служить комбинация {Year_in, Faculty, Spec, Group}:

1.2. Первичный ключ

Из множества потенциальных ключей отношения выбирается один, который становится первичным ключом (primary key). Например, STUD_NO в таблице STUDENT. Первичный ключ уникален и не может содержать NULL-значений; он может состоять из одного или нескольких столбцов.

1.3. Суперключ

Суперключ — набор атрибутов, который может однозначно идентифицировать кортеж. Например, STUD_NO и (STUD_NO, SNAME) — суперключи. Суперключ может включать NULL-значения; добавление любых атрибутов к ключу-кандидату формирует суперключ.

Суперключ отличается от потенциального ключа тем, что на него не накладывается требование минимальности (несократимости) — отсутствия меньшего подмножества атрибутов, удовлетворяющего условию уникальности. Вследствие этого в состав суперключа может входить другой, более «компактный» суперключ.

1.4. Альтернативный ключ

Альтернативный ключ — это ключ-кандидат, который не был выбран в качестве первичного. Все ключи, не являющиеся первичными, называются альтернативными. Например, если первичным ключом таблицы STUDENT выбран STUD_NO, то другие потенциальные ключи (скажем, NAME или CITY, если их уникальность гарантирована предметной областью) становятся альтернативными.

1.5. Внешний ключ

Внешний ключ (foreign key) — атрибут, который может принимать только те значения, которые присутствуют в качестве значений другого атрибута. Отношение, на которое ссылаются, называется ссылочным отношением, а соответствующий атрибут — ссылочным атрибутом. Ссылочный атрибут должен быть первичным ключом в другом отношении.

Здесь атрибут STUD_NO таблицы STUDENT_COURSE — внешний ключ по отношению к атрибуту STUD_NO таблицы STUDENT.

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

2. Нормализация данных

Нормализация базы данных — метод проектирования реляционных БД, который помогает правильно структурировать таблицы данных. Процесс направлен на создание системы с чётким представлением информации и взаимосвязей — без избыточности и потери данных.

Нормализация — итеративный процесс: она выполняется через серию тестов, и каждый последующий шаг разбивает таблицу на более лёгкую в управлении информацию, повышая общую логичность системы и простоту работы с ней.

Нормализация позволяет оптимально распределять атрибуты по таблицам и избавляет от:

• атрибутов с несколькими значениями;
• задвоения и повторяющихся атрибутов;
• атрибутов, не поддающихся классификации;
• атрибутов с избыточной информацией;
• атрибутов, созданных из других признаков.

Полную нормализацию выполнять не обязательно, однако она гарантирует полноценно функционирующую информационную среду. Метод:

• позволяет создать структуру базы, подходящую для общих запросов;
• сводит к минимуму избыточность данных, повышая эффективность использования памяти на сервере БД;
• гарантирует максимальную целостность данных, устраняя аномалии вставки, обновления и удаления.

2.1. Избыточность и аномалии

Когда в таблицу с избыточностью вносятся изменения, приходится корректировать все повторяющиеся экземпляры данных и связанные с ними объекты. Если этого не сделать, таблица становится несогласованной — возникают аномалии. Рассмотрим таблицу:

Для неё характерна избыточность данных, а при изменении данных возникают три аномалии.

1. Аномалия вставки. При добавлении нового сотрудника (employee) в отдел (sector) Finance обязательно указывается его руководитель (manager) — иначе данные вставить не удастся, даже если информация о руководителе отдела в базе уже есть:

2. Аномалия обновления. Когда сотрудник переходит в другой отдел, поле «Руководитель» содержит ошибочные данные: Джейкоб (Jacob) перешёл в Marketing, но его руководителем по-прежнему показан Адам:

3. Аномалия удаления. Если Джошуа (Joshua) уволится и его строка будет удалена, потеряется информация о том, что отдел Finance вообще существует — вместе с последним сотрудником исчезают сведения об отделе.

2.2. Основные понятия нормализации

Простейшие понятия, используемые в нормализации:

• ключи — атрибуты столбцов, которые однозначно (уникально) определяют запись в БД;
• функциональные зависимости — ограничения между двумя взаимосвязанными атрибутами;
• нормальные формы — этапы достижения определённого качества БД.

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

Все уровни нормализации кумулятивны (накопительны): прежде чем перейти к следующему этапу, выполняются все требования текущей формы.

База данных считается нормализованной после достижения третьей нормальной формы. Дальнейшие этапы усложняют структуру БД и могут нарушить функциональность системы.

2.3. Нормализация по шагам

Общие этапы нормализации подходят для всех таблиц; конкретные методы разделения зависят от предметной области. Разберём классический пример — таблицу сотрудников с руководителями и отделами. В ненормализованной таблице один столбец содержит несколько значений, а данные о руководителях дублируются:

Шаг 1: первая нормальная форма (1НФ). Значения полей должны быть атомарными: все сложные сущности разделяются на новые строки или столбцы. Чтобы не потерять информацию, для каждого сотрудника дублируются значения столбцов managerID, managerName и area:

Шаг 2: вторая нормальная форма (2НФ). Каждая строка таблицы должна зависеть от первичного ключа целиком. Таблица разделяется на две: Manager (managerID, managerName, area) и Employee (employeeID, employeeName, managerID, sectorID, sectorName) — без частичных зависимостей:

Шаг 3: третья нормальная форма (3НФ).

Третья нормальная форма разделяет любые транзитивные функциональные зависимости. В нашем примере транзитивная зависимость есть у таблицы Employee (employeeID → sectorID → sectorName); она разбивается на две новые таблицы — Employee (employeeID, employeeName, managerID, sectorID) и Sector (sectorID, sectorName):

Конечная структура — три взаимосвязанные таблицы:

Теперь база данных считается нормализованной. Дальнейшая нормализация зависит от конкретных целей. Пройдите те же шаги в интерактивном стёппере: на каждом шаге красным подсвечена проблема, зелёным — что изменилось.

3. Индексация

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

Общие этапы создания индекса:

1. определить столбцы для индексирования — обычно те, что чаще всего используются в запросах и поиске;
2. выбрать алгоритм индексирования, подходящий типу данных: B-деревья — для строковых и числовых данных, полнотекстовые индексы — для текстов;
3. применить алгоритм к выбранным столбцам — создаётся структура, сопоставляющая значения с местоположениями записей;
4. сохранить индекс в отдельной структуре данных — в другой части диска или в памяти, где доступ к нему эффективнее, чем к самой таблице;
5. обновлять индекс при добавлении, удалении и изменении записей.

Индекс существенно ускоряет запросы и поиск, но имеет цену: рост требований к объёму хранилища и замедление вставки и обновления. Перед созданием индекса следует взвесить плюсы и минусы.

3.1. B-дерево

B-tree (сбалансированное дерево) — самый распространённый тип индекса в PostgreSQL. Он поддерживает все стандартные операции сравнения (>, <, >=, <=, =, <>) и применим к большинству типов данных. B-tree индексы используются для сортировки, ограничений уникальности и поиска по диапазону значений.

Главное преимущество B-дерева — минимизация дисковых операций ввода-вывода: все узлы-листья находятся на одном уровне, а каждый узел хранит множество ключей и указателей. Количество ключей в узле определяется параметром, называемым «порядком» дерева.

Недостатки B-деревьев:

• расход ресурсов — каждый узел содержит указатели на родительский и дочерние узлы, что требует дополнительного пространства;
• сложность — алгоритмы вставки, удаления и поиска сложнее, чем у других структур, что усложняет реализацию и поддержку;
• медленные обновления — каждая операция обновления требует множества обращений к диску, что заметно на больших деревьях.

3.2. Bitmap-индекс

Bitmap-индексирование использует битовые карты для обозначения наличия или отсутствия значения в таблице. Это успешная техника для таблиц с низкой кардинальностью, где количество уникальных значений в столбце мало по сравнению с общим числом строк.

Битовые карты крайне компактны и быстро сканируются, поэтому bitmap-индексы удобны в хранилищах данных, где нужно быстро просматривать огромные объёмы, и в базах с большим количеством чтений при редких обновлениях.

Недостатки:

• большой размер на крупных датасетах — индекс может уступать в эффективности другим методикам;
• столбцы с высокой кардинальностью — при большом количестве уникальных значений битовые карты разрастаются и не помещаются в памяти;
• смещённое распределение данных (heavy-tail) — карты частых значений становятся очень большими и доминируют в индексе.

3.3. Хэш-индекс

Hash-индексы предназначены для быстрого доступа к данным по равенству. Они менее универсальны, чем B-tree, и не поддерживают сортировку или поиск по диапазону, из-за чего на практике используются редко.

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

• только поиск равенства — «найти записи, где столбец равен значению»; диапазоны и сортировка недоступны;
• коллизии — несколько ключей с одним хэш-значением снижают производительность из-за дополнительных операций разрешения;
• непредсказуемый размер — объём индекса зависит от количества уникальных значений, что усложняет планирование хранилища.

3.4. GiST

GiST (Generalized Search Tree, обобщённое поисковое дерево) — техника индексирования для сложных типов данных, например геометрических объектов.

Это сбалансированная древовидная структура из узлов с множественными дочерними узлами. Каждый узел описывает диапазон или множество значений и связан с предикативной функцией, проверяющей принадлежность значения диапазону. Предикативная функция зависит от типа индексируемых данных и настраивается под разные типы.

GiST часто используется для индексации пространственных данных — например, в PostGIS, расширении PostgreSQL. Он особенно полезен для запросов с геометрическими отношениями: поиск объектов в радиусе, пересечение областей и другие пространственные запросы.

Для создания индекса необходим один столбец, поэтому многомерные координаты преобразуются в одномерные. Один из эффективных методов — кривая Гильберта: пространство-заполняющая кривая, сохраняющая близость точек многомерного пространства.

Недостатки GiST:

• сниженная скорость вставок и обновлений из-за сложности структуры;
• больше дискового пространства — хранится дополнительная информация для поддержки разных типов поиска;
• подходит не для всех типов данных: для простых целых чисел и строк лучше классические индексы;
• повышенные затраты на поддержку по сравнению с традиционными индексами.

3.5. Гонка индексов

Почему индекс так ускоряет поиск? В отсортированном наборе значение можно искать делением диапазона пополам — как в B-дереве, — а без индекса приходится читать строки подряд. Запустите гонку: обе стратегии ищут одно и то же значение в таблице из 64 строк, счётчики показывают число сравнений. Попробуйте несколько целей — предельный выигрыш индекса растёт с размером таблицы как N / log₂N.

4. Использование индексов: пять сценариев

Рассмотрим пять примеров использования индексов PostgreSQL в реальных сценариях — с кодом таблицы, индексов и пояснением.

4.1. Онлайн-магазин

В онлайн-магазине есть таблица orders с информацией о заказах. Пользователи ищут заказы по customer_id, order_date и status — создадим индексы для этих столбцов:

CREATE TABLE orders (
  id SERIAL PRIMARY KEY,
  customer_id INT NOT NULL,
  order_date DATE NOT NULL,
  status VARCHAR(15) NOT NULL
);

CREATE INDEX ix_orders_customer_id ON orders (customer_id);
CREATE INDEX ix_orders_order_date ON orders (order_date);
CREATE INDEX ix_orders_status ON orders (status);

4.2. Система управления документацией

Таблица documents: поиск по title, author_id, creation_date, а для содержимого — полнотекстовый GIN-индекс:

CREATE TABLE documents (
  id SERIAL PRIMARY KEY,
  title VARCHAR(255) NOT NULL,
  author_id INT NOT NULL,
  creation_date DATE NOT NULL,
  content TEXT NOT NULL
);

CREATE INDEX ix_documents_title ON documents (title);
CREATE INDEX ix_documents_author_id ON documents (author_id);
CREATE INDEX ix_documents_creation_date ON documents (creation_date);

-- полнотекстовый индекс для столбца content
CREATE INDEX ix_documents_content ON documents
  USING gin(to_tsvector('english', content));

4.3. Система управления проектами

Таблица tasks: поиск задач по проекту, исполнителю и сроку:

CREATE TABLE tasks (
  id SERIAL PRIMARY KEY,
  project_id INT NOT NULL,
  assigned_to INT NOT NULL,
  due_date DATE NOT NULL,
  description TEXT NOT NULL
);

CREATE INDEX ix_tasks_project_id ON tasks (project_id);
CREATE INDEX ix_tasks_assigned_to ON tasks (assigned_to);
CREATE INDEX ix_tasks_due_date ON tasks (due_date);

4.4. Социальная сеть

Таблица friendships с дружескими связями; составной первичный ключ и индексы по обоим участникам связи:

CREATE TABLE friendships (
  user_id INT NOT NULL,
  friend_id INT NOT NULL,
  since_date DATE NOT NULL,
  PRIMARY KEY (user_id, friend_id)
);

CREATE INDEX ix_friendships_user_id ON friendships (user_id);
CREATE INDEX ix_friendships_friend_id ON friendships (friend_id);

4.5. Геоинформационная система

В ГИС есть таблица locations с географическими данными. Для пространственных запросов к столбцу geom создаётся GiST-индекс:

CREATE TABLE locations (
  id SERIAL PRIMARY KEY,
  name VARCHAR(255) NOT NULL,
  geom GEOMETRY(Point, 4326) NOT NULL
);

-- геометрический индекс для столбца geom
CREATE INDEX ix_locations_geom ON locations USING gist(geom);

С этим индексом мы встретимся в практике 3: PostGIS создаёт GiST-индексы для геометрических столбцов, ускоряя ST_Intersects, ST_DWithin и другие пространственные предикаты.

Контрольные вопросы

• Постройте цепочку: суперключ → потенциальный ключ → первичный ключ → альтернативный ключ.
  Суперключ — любой набор атрибутов, однозначно идентифицирующий кортеж. Потенциальный ключ — минимальный (несократимый) суперключ. Первичный ключ — один из потенциальных, выбранный для идентификации; NULL для него запрещён. Альтернативные ключи — остальные потенциальные ключи, не ставшие первичным.
• Что такое внешний ключ и какое ограничение целостности он реализует?
  Внешний ключ — атрибут, принимающий только значения, присутствующие в ссылочном атрибуте другого отношения (как правило, его первичном ключе). Он реализует ссылочную целостность: нельзя сослаться на несуществующую запись.
• Опишите три аномалии ненормализованной таблицы на примере сотрудников и отделов.
  Аномалия вставки: нового сотрудника не добавить без указания руководителя, хотя эти сведения в базе уже есть. Аномалия обновления: при переводе сотрудника поле руководителя остаётся старым — данные противоречивы. Аномалия удаления: удаление последнего сотрудника отдела уничтожает сведения о самом отделе.
• Сформулируйте требования 1НФ, 2НФ и 3НФ.
  1НФ: значения полей атомарны, нет повторяющихся групп. 2НФ: выполняется 1НФ, и каждый неключевой атрибут зависит от первичного ключа целиком (нет частичных зависимостей от части составного ключа). 3НФ: выполняется 2НФ, и нет транзитивных зависимостей — неключевые атрибуты зависят только от ключа, а не друг от друга.
• Почему нормализацию обычно останавливают на 3НФ?
  После 3НФ база считается нормализованной: главные источники аномалий устранены. Дальнейшие формы (НФБК, 4НФ, 5НФ) усложняют структуру, умножают число таблиц и соединений и могут ухудшить производительность и работоспособность системы; их применяют при особых видах зависимостей.
• Сравните B-tree и hash-индексы: что умеет каждый и почему hash редко используют?
  B-tree поддерживает все операции сравнения, сортировку, диапазоны и уникальные ограничения; листья на одном уровне, узлы хранят много ключей — минимум дисковых чтений. Hash даёт O(1) на точное равенство, но не умеет диапазоны и сортировку, страдает от коллизий, а размер индекса непредсказуем — поэтому на практике почти всегда выбирают B-tree.
• Когда эффективен bitmap-индекс и что его разрушает?
  Эффективен при низкой кардинальности столбца (мало уникальных значений при большом числе строк) и нагрузке «много чтений, мало изменений» — например, в хранилищах данных. Разрушают его высокая кардинальность (карты разрастаются) и смещённые распределения, где карты частых значений доминируют в индексе.
• Зачем PostGIS использует GiST и при чём здесь кривая Гильберта?
  GiST — обобщённое дерево с настраиваемой предикативной функцией узлов, поэтому оно умеет индексировать сложные типы — геометрии — и ускорять пространственные запросы (пересечения, поиск в радиусе). Индексу нужен один столбец, поэтому многомерные координаты сводят к одномерным пространство-заполняющей кривой Гильберта, сохраняющей близость точек.
• Назовите цену, которую база платит за каждый созданный индекс.
  Дополнительное дисковое пространство и замедление всех операций изменения данных: при INSERT, UPDATE и DELETE каждый индекс таблицы должен обновляться. Поэтому индексируют столбцы, реально участвующие в частых запросах, а не все подряд.

Источники

1. Дейт, К. Дж. Введение в системы баз данных / К. Дж. Дейт. — 8-е изд. — М. : Вильямс, 2005. — 1328 с.
2. PostgreSQL 15 Documentation. Chapter 11. Indexes : [сайт]. — URL: https://www.postgresql.org/docs/15/indexes.html (дата обращения: 18.08.2026).
3. Рогов, Е. В. PostgreSQL изнутри / Е. В. Рогов. — М. : ДМК Пресс, 2022. — 660 с.
4. PostGIS Documentation. Spatial Indexing : [сайт]. — URL: https://postgis.net/workshops/postgis-intro/indexing.html (дата обращения: 18.08.2026).