Индексы ускоряют поиск в БД, но увеличивают затраты на запись и объём памяти. Транзакции обеспечивают атомарность, согласованность, изоляцию и долговечность (ACID) или альтернативную модель BASE для масштабируемых NoSQL.

Индексы

Без индексов поиск — полное сканирование таблицы (full scan), O(n). Индексы дают поиск за логарифмическое или константное время, но замедляют вставку/обновление и занимают место.

Основные типы

• B-Tree: основной индекс в PostgreSQL, MySQL. Широкое дерево (ветвистость 100–200), минимизация обращений к диску. Поддержка диапазонов (WHERE date BETWEEN ...). Сложность порядка O(log n).
• Хэш-индекс: точечный поиск за O(1). Не поддерживает диапазоны. Подходит для точного совпадения по ключу (например, primary key).
• Bitmap: для бинарных или дискретных признаков; побитовые AND/OR, компактное хранение в памяти. Пример: фильтр по опциям поездки (can_with_pet, has_hookah).
• Reverse (инвертированный): для полнотекстового поиска — по слову список документов, где оно встречается (Elasticsearch).
• Spatial: для координат и геоданных (quad-tree и др.). Поиск объектов в радиусе, ближайшие точки.
• Разряженный: индексируется не каждая запись, а группы (например, каждая 1000-я). Меньше размер индекса, быстрее вставки. Используется в аналитических БД (ClickHouse).
• Покрывающий: в индекс включены не только ключи, но и поля, возвращаемые запросом. Запрос выполняется только по индексу, без обращения к таблице.
• Кластерный vs некластерный: кластерный — физический порядок строк по ключу (часто primary key); некластерный — отдельная структура, порядок строк не меняется. Хэш не может быть кластерным (нет порядка).

Транзакции и ACID

Транзакция — набор операций «всё или ничего»: либо все выполняются, либо все откатываются.

• A (Atomicity): выполнение полностью или откат целиком. Пример: перевод денег — списание с одного счёта и зачисление на другой должны быть одной транзакцией; при ошибке второго шага откатывается первый.
• C (Consistency): переход из одного согласованного состояния в другое; ограничения (NOT NULL, UNIQUE, FOREIGN KEY) не нарушаются. Бизнес-правила (например, баланс ≥ 0) должны обеспечиваться логикой и ограничениями.
• I (Isolation): параллельные транзакции изолированы. Аномалии при слабой изоляции: потерянное обновление, грязное чтение, неповторяющееся чтение, фантомы. Уровни изоляции (Read Uncommitted, Read Committed, Repeatable Read, Serializable) ограничивают эти эффекты. Реализация: блокировки (2PL), MVCC (многоверсионность — каждая запись имеет версии, SELECT видит согласованный снимок, UPDATE создаёт новую версию; в PostgreSQL — VACUUM для очистки старых версий).
• D (Durability): после commit данные сохранены даже при сбое. Обычно через WAL: сначала запись в журнал, затем подтверждение клиенту, затем асинхронное обновление основных данных.

Deferrable-транзакции: проверка ограничений (например, foreign key) откладывается до конца транзакции — удобно при циклических ссылках между таблицами.

BASE (альтернатива ACID)

В масштабируемых NoSQL (например, Cassandra) часто используют модель BASE:

• Basically Available: доступность за счёт репликации.
• Soft State: состояние может временно быть несогласованным.
• Eventual Consistency: со временем данные приходят к согласованному состоянию.

ACID — для строгой согласованности (реляционные БД, финансы). BASE — для высокой доступности и масштабирования при допустимой временной несогласованности. Граница размывается: многие NoSQL добавляют поддержку транзакций.

Выбор: индексы — как навигатор (ускоряют путь, но требуют ресурсов); транзакции ACID/BASE — как правила движения (безопасность и предсказуемость vs доступность и масштаб).