База по базам данных — Storage
Индексы, Paging, LSM, B+-Tree, R-Tree и всё, что между ними
Ниже — большой, «практико-ориентированный» конспект с техническими деталями, примерами и рисками. Пишите его как справочник и учебник для команды: от системных аналитиков и архитекторов до разработчиков и администраторов СУБД.
Начало — карта территории
Зачем знать “storage”. Как данные физически лежат на носителе и в памяти, определяет всё: скорость чтения/записи, предсказуемость латентности, стоимость инфраструктуры, путь масштабирования и даже то, какие запросы вообще разумно выполнять.
Слои, которые нас интересуют:
- Логическая модель (таблицы, столбцы, типы, ограничения).
- Физическая организация (страницы/странички, заголовки, heap/segment, сжатие).
- Буферный пул и кэширование (страница ↔ RAM ↔ диск/SSD).
- Журналы (WAL/redo) и контрольные точки.
- Индексы (B+-Tree, hash, bitmap, inverted, R-Tree, вектора).
- Хранилища на деревьях vs LSM (compaction, memtable, SSTable).
- Планировщик запросов (статистика, эквивалентные преобразования).
DBMS — из чего она состоит
Типичная СУБД — это:
- Parser/Analyzer (разбор SQL, проверка типов и прав).
- Planner/Optimizer (логический план → физический).
- Executor (итераторы операторов: scan, join, sort, agg).
- Storage Engine (страницы, индексы, журнал, буферный пул).
- Процедуры надежности (WAL, checkpoint, recovery, replication).
- Сборщик статистики и каталог (system catalog + stats).
Практический совет. В проде вы почти всегда упираетесь в дуэт Storage Engine + Query Planner: неправильно выбранный индекс/формат страницы или неверные статистики дают 10–100× к задержке.
Архитектуры DBMS
- Monolithic (например, PostgreSQL): единый движок, тесно связаны парсер, планировщик, storage.
- Pluggable Engines (например, MySQL/InnoDB, MariaDB, некоторые MPP): под одну SQL-надстройку можно подключать разные хранилища.
- SMP vs MPP: один узел с многопоточностью vs кластер shared-nothing (распределённые партиции, обмен данными).
- Row-store vs Column-store vs Hybrid (PAX, cstore).
- In-Memory vs Disk-based (но почти всегда есть журнал и чекпоинты на диске).
Риски. Смена движка хранения (row↔column, B-Tree↔LSM) меняет не только производительность, но и поведение транзакций, фоновых задач, репликацию и обслуживание.
Storage — логическая и физическая схема
- Heap/Segment: таблица разбита на страницы (pages, обычно 4–32 КБ).
- Запись (tuple/row) внутри страницы хранится через слотовую директорию: массив указателей на начало записей, чтобы поддерживать переменную длину, обновления и удаление без тотальной перекладки.
- Выравнивание и bitmap NULL: компактное хранение пропусков, выравнивание по 8 байтам для ускорения CPU.
MVCC (многоверсионность): Вместо блокировок на чтение — версии строк + метаданные видимости (xmin/xmax), а чистка мусора — асинхронно (VACUUM/GC).
Paging — страничная организация ввода-вывода
- Страница — минимальная единица I/O (читается/пишется целиком).
- Размерами страницы управляют компромиссами: больше страница — больше пропускная способность на последовательных чтениях, но хуже точность кэширования и waste при мелких строках.
- Prefetch/Read-ahead и write-behind — оптимизация последовательного сканирования/записей.
- Double-write/Checksums — защита от torn-page.
Практика. При аналитических сканах (large scans) увеличивайте глубину prefetch и размер I/O; для OLTP — держите рабочий набор в RAM, не раздувая страницу.
Overflow Page — «слишком большие» строки
Когда строка не влезает на страницу (BLOB/CLOB, JSON крупный), движок:
- Выносит «тело» во внестраничные страницы (TOAST-подобные механизмы), а в основной строке оставляет указатель.
- Может применять сжатие и фрагментацию по чанкам.
Риск. Частый доступ к «переливам» рушит locality и сильно бьёт по латентности. Для OLTP держите большие поля отдельно, загружайте по требованию.
Page Header — что в заголовке страницы
Типично содержит:
- LSN (логическая позиция в WAL для recovery).
- Checksum/flags (целостность).
- Free space pointer (граница свободного места).
- Item directory (указатели на записи).
- PageId/SegmentId, ссылки на соседа (в B-Tree страницах).
Практика. Мониторинг свободного места и плотности (fillfactor) помогат выявлять bloat до того, как он «съест» диски и кеш.
VACUUM — жизнь с MVCC
Когда строки теряют видимость (удалены/переписаны), они не исчезают сразу, чтобы не блокировать читателей. Нужны фоновые процессы:
- Page pruning (быстрая локальная уборка).
- VACUUM/GC (полная очистка, дефрагментация свободного пространства).
- Freeze (нормализация версий для «вечной» видимости).
- Auto-tuning (автовакуум по порогам изменений).
Риски и анти-паттерны:
- Долгие транзакции задерживают уборку → bloat.
- Агрессивный VACUUM на горячих таблицах → конкуренция за I/O.
- Игнорировать статистику autovacuum — верный путь к аварийному росту.
Памятка настройки: ограничьте длительность транзакций (минуты, не часы), выставьте разумные cost_delay/cost_limit, контролируйте freeze на больших таблицах.
Row- vs Column-oriented DB
- Row-store (OLTP, point-lookups, много узких SELECT/UPDATE): локальность по строке, хороший cache-hit при доступе «по ключу».
- Column-store (OLAP, агрегации по множеству строк, сканы небольшого поднабора столбцов): отличный сжатый I/O, векторные операции CPU, late materialization.
- Гибриды (PAX/дубликаты витрин): строки в оперативном, колонки в витринах.
Риски. Пытаться делать тяжёлые OLAP-сканы на чистом row-store без предагрегаций и колонок — дорого. И наоборот, часто обновляемые OLTP-сущности в column-store → write amplification.
System Catalog — метаданные как двигатель планировщика
Каталог содержит:
- Список таблиц/индексов/последовательностей, схемы и права.
- Статистику: гистограммы, ndistinct, корелляции, MCV, гиперлоглоги.
- Зависимости (view → table, индекс → таблица), правила, триггеры.
Практика. Регулярный ANALYZE/сбор статистики — критичен. Иначе планировщик ошибается с кардинальностями → неверные планы (особенно join order).
Buffer Pool — кэш страниц СУБД
- Hash-таблица дескрипторов страниц (lookup по (file, pageNo)).
- Replacement policy: LRU-семейство, Clock-sweep, 2Q, ARC.
- Dirty pages и checkpoint: когда сбрасывать на диск.
- Pin/Unpin: фиксация страниц во время операции.
Риски. Слишком маленький пул → thrash с ОС-кешем. Слишком большой — длинные чекпоинты и всплески fsync.
LRU Cache — и почему «простой LRU» не спасает
- LRU хорошо держит «часто используемое, недавно использованное».
- Проблема scan pollution: длинный последовательный скан выталкивает полезный рабочий набор.
Решения:
- 2Q/ARC (разделение списков на «вновь пришедшее» и «часто используемое»).
- Специальные классы обращений: sequential страницы минуют горячую часть кэша.
- Тюнинг readahead и «через-страничных» предзагрузок.
Sequential flood — что это и как жить
Последовательный поток на огромной таблице «смывает» кэш, портя задержки у OLTP.
Симптом: резкие пики латентности на ключевых запросах при ETL/сканах.
Профилактика:
- Политики кэширования «сканы не нагревают LRU».
- Выделение пулов (OLTP vs OLAP) или изоляция нагрузок по узлам.
- Предагрегации/материализованные представления для отчётов.
Индексы — общая логика
Индекс — это структура, позволяющая быстро найти подмножество строк без полного скана.
Базовые понятия:
- Селективность: доля строк, удовлетворяющих предикату.
- Покрывающий индекс (covering): все нужные столбцы в листьях → можно обойтись без обращения к таблице (index-only).
- Maintenance cost: цена вставок/обновлений/удалений.
- Clustering: насколько порядок строк в таблице согласован с порядком индекса.
Практическое правило: индекс окупается, если сильно сокращает I/O на типичных фильтрах/джоинах и не убивает скорость записи.
Hash-индекс
- Ключ → хэш → bucket → (цепочка) → совпадения.
- Хорош для равенства (=), бесполезен для диапазонов (>, <, BETWEEN).
- Ресайзинг бакетов и борьба с overflow на горячих ключах.
Риски. Неестественное распределение/«горячие ключи» → цепочки растут, лок-конкуренция. Нет упорядоченности → нельзя использовать для сортировок/диапазонов.
B/B+-Trees — рабочая лошадка OLTP
- B+-Tree: все ключи в листьях, внутренние страницы — направляющие.
- Fanout (ветвистость) велик → глубина мала (обычно 2–4).
- Поддерживает диапазоны, ORDER BY, составные ключи, LIKE 'abc%'.
Важные параметры:
- Fillfactor: оставить в листьях запас под будущие вставки без частых расщеплений.
- Page splits/merges: дорогие в I/O и могут фрагментировать.
- CLUSTER или сближение порядка таблицы с индексом повышает locality.
- HOT-обновления (переписывать без изменения ключа) — экономят работу индекса.
Риски. Bloat при постоянных обновлениях, «горячие» границы диапазонов, большие ключи (UUID v4 хуже по locality, чем v7/временные).
Bitmap-индекс
- Для низкой кардинальности (например, пол, флаг, статус): на значение — битовая матрица строк.
- Логические операции AND/OR/NOT сверхбыстры.
- Варианты: Roaring, WAH, EWAH, bit-slice для агрегатов.
Практика. В OLAP (колоночные СУБД) битмапы часто формируются на лету в планировщике и комбинируются из нескольких индексов. В OLTP постоянные обновления делают чисто-дисковые bitmap-индексы дорогими.
Инвертированный индекс (full-text)
- Term → posting list (docID, позиции), плюс статистики (tf, df).
- Поиск по слову/фразе/стемму, ранжирование (BM25 и пр.).
- Для обновлений применяют сегменты и слияния (LSM-подход в поиске).
Риски. Большие списки у частотных терминов, порядок обновлений → «грязные» сегменты, необходимость позднего удаления (tombstones).
Embedding (векторные индексы)
- Хранят вектор признаков (числа float). Поиск — по метрике (L2, cosine, IP).
- Часто используют ANN: HNSW, IVF, PQ, IVFPQ, DiskANN.
- Баланс recall ↔ latency ↔ память задаётся параметрами графа/кластеризации/квантования.
Риски. Дрейф эмбеддингов при переобучении моделей, нормализация (cosine требует unit-norm), обновления «на лету» в графах дороже пакетных.
R-Tree — пространственные индексы
- Узлы хранят минимальные ограничивающие прямоугольники (MBR).
- Хорош для ST_Intersects, ST_Within, bbox запросов, гео/кадастр/IoT.
- Варианты R* и GiST (обобщённый интерфейс индекса).
Риски. Перекрывающиеся MBR → больше страниц при поиске; требуется грамотная вставка/перебалансировка. Для высоких размерностей лучше kd-tree/ball-tree/векторные индексы.
LSM-Storage — когда запись важнее чтения
Идея: не трогать диск по мелочи.
- Записи идут в WAL, затем — в memtable (in-memory),
- memtable периодически «замораживается» (immutable) и сбрасывается в SSTable на диск,
- фоновые compaction сливают много мелких файлов в крупные, поддерживая ключевой порядок.
Два основных режима компактаций:
- Size-Tiered (STCS): объединяем несколько равных по размеру файлов → приводит к быстрым последовательным записям, дешевле по CPU, но хуже по читающей амплификации.
- Leveled (LCS/Leveled): уровни L0…Ln, каждый — ограниченного размера; ключ в уровне встречается один раз → выше write amplification, но стабильнее чтение.
Инструменты вокруг LSM:
- Bloom-фильтры у файлов, чтобы не читать «точно нет».
- Index/summary в каждом SSTable, иногда prefix compression.
- Compaction filters (удаление мусора/просроченных TTL во время слияний).
- Tombstones для удалений/апдейтов (живут до compaction).
Риски:
- Write amplification (особенно в leveled).
- Read amplification (много файлов при холодном кеше).
- Stall при backpressure (memtable не успевает сбрасываться).
- Горячие ключи и перекос данных → дисбаланс уровней.
Когда выбирать LSM: поток вставок/апдейтов велик, ключевые выборки по range ограниченные, нужен дешёвый последовательный диск-I/O и масштабирование на SSD/HDD.
Bloom Filter — быстрый «нет»
- Структура: битовый массив + k хэшей.
- Отвечает: «элемент точно отсутствует» или «возможно есть» (ложноположительные).
- Настраивается выбором m (размер), k (число хэшей) под ожидаемый n.
Практика. В LSM лежит рядом с SSTable и экономит чтения с диска. Плохие параметры → высокий FP rate → фильтр бесполезен.
WAL и Manifest Log
- WAL (Write-Ahead Log): сначала логируем изменение, потом меняем страницы. Обеспечивает durability (D) в ACID и recovery.
- Group commit уменьшает количество fsync.
- Manifest/STATE: реестр актуальных файлов/сегментов SSTable, точки согласованности, снапшоты для быстрой реконструкции метаданных.
Риски. Длинные интервалы чекпоинтов/flush → большой хвост восстановления; NVRAM/SSD с нестабильным fsync — spikes латентности.
Memtable — оперативный фронт LSM
- Структура в памяти (часто skip-list, treap, AVL), принимает все записи после WAL.
- При достижении порога — immutable и flush в SSTable.
- Можно держать несколько активных memtable для параллельных потоков.
Тюнинг. Размер memtable = баланс между частотой flush и пиками компактаций. Слишком большая — долгая пауза на freeze; слишком маленькая — много мелких файлов.
Skip List — простая и быстрая для конкурентности
- У каждого узла есть «прыжковые уровни», случайные с вероятностью p (обычно 0.25/0.5).
- Среднее O(log n) на поиск/вставку, простая реализация lock-friendly/lock-free.
- Хорошо ложится в кэш CPU благодаря последовательности по уровням.
Обобщение — как выбирать формат и индекс
OLTP (много точечных операций):
Row-store + B+-Tree, маленькие страницы, агрессивный buffer pool, короткие транзакции, чёткий VACUUM/GC, композитные индексы по популярным предикатам, иногда hash-индексы под =.
OLAP (сканы и агрегации):
Column-store, сжатие, векторные исполнения, bitmap/инвертированные индексы, материализованные представления/предагрегации, разделение нагрузки (ETL/BI) от OLTP.
Поток записей, time-series, лог-данные:
LSM (Leveled), Bloom, TTL/tombstones, compaction filters, партиционирование по времени, индексы по (tenant_id, ts).
Гео/пространство:
R-Tree/GiST, ограничение перекрытий, нормализация геометрий, кластеризация по пространству.
Поиск/семантика/вектора:
Inverted + HNSW/IVF(PQ), offline переобучение эмбеддингов, контроль дрейфа, периодические reindex/merge.
Query Plan — путь от SQL к исполнителю
- Разбор и построение логического плана (сканы, фильтры, проектирование).
- Переписывания (см. ниже эквивалентности): pushdown предикатов, упрощение выражений.
- Оценка кардинальностей по статистике (ключ к правильному join order).
- Выбор физических операторов: Index Scan/Bitmap Scan/Seq Scan; Nested Loop/Hash Join/Merge Join; сортировки vs индексы; materialize/inline.
- Стоимость = CPU + I/O + сетевые передачи (в MPP) + память под сорт/хеш.
Практика. Неверная статистика → неверный join order → взрыв по памяти/времени. Регулярно обновляйте статистику; используйте extended stats (корреляции/множественные столбцы), когда данные «косые».
Эквивалентные выражения — как оптимизатор «делает магию»
Классические законы реляционной алгебры:
- Коммутативность/ассоциативность соединений: A ⋈ B = B ⋈ A, (A ⋈ B) ⋈ C = A ⋈ (B ⋈ C).
- Проекцию можно двигать вниз (убирать ненужные столбцы раньше).
- Предикаты pushdown: фильтры как можно ближе к источнику/индексу/скану.
- Константные выражения — сводить заранее; IN переписывать в semi-join/bitmap.
- Антисоединения для NOT IN/NOT EXISTS (иногда переписывать в anti-join быстрее).
- В колоночных СУБД — late materialization (откладывать сбор строки как можно позже).
Практика на SQL:
-- Плохо: тащим «жирные» строки в join, фильтруем после SELECT o.* FROM orders o JOIN customers c ON o.cust_id = c.id WHERE c.region = 'EMEA'; -- Лучше: сузить customers по индексу, затем join WITH emea AS ( SELECT id FROM customers WHERE region = 'EMEA' ) SELECT o.* FROM orders o JOIN emea e ON o.cust_id = e.id;
Практические примеры и чек-листы
Пример 1: точечные выборки по ключу (OLTP)
Задача. Быстро отдавать заказы по order_id и по (cust_id, created_at DESC LIMIT 10).
Решение.
CREATE INDEX ix_orders_id ON orders(order_id); -- PK, B+-Tree CREATE INDEX ix_orders_cust_time ON orders(cust_id, created_at DESC) INCLUDE (amount, status); -- покрывающий
Почему так: B+-Tree даст O(log N) и возможность сортировки по времени без отдельного ORDER BY. INCLUDE сделает index-only scan для списка последних заказов.
Риски: много обновлений created_at? — нет, это вставки; следите за fillfactor и авто-вакуумом.
Пример 2: аналитика по статусам (OLAP)
Задача. Частые отчёты WHERE status IN (...) AND region = ....
Решение:
- В колоночном хранилище: словарная компрессия + битмапы на status, region.
- В row-store: материализованные витрины или частичные индексы:
CREATE INDEX ix_orders_status_region
ON orders(region)
WHERE status IN ('SHIPPED','CANCELLED');
Риски: в OLTP bitmap-индексы на диске дорогие при UPDATE/DELETE; лучше — витрины.
Пример 3: time-series и LSM
Задача. 50k вставок/сек сенсорных данных, выборки по (device_id, ts BETWEEN ...).
Решение: LSM/Leveled, ключ (device_id, ts), партиции по дате, Bloom-фильтры на SSTable, TTL и compaction filters для старых данных.
Риски: всплески compaction → выделите бюджет I/O, настраивайте размер мемтаблиц и параллелизм слияний.
Пример 4: гео-поиск
Задача. ST_Intersects(geom, :bbox).
Решение: R-Tree/GiST по geom, хранить также упрощённый bbox для первичного фильтра (cheap), сложные предикаты — вторым шагом.
Риски: перекрытия MBR растут при разнородной геометрии → периодическая перестройка/пере-packing дерева.
Риски по разделам (сводно)
- Страницы/Heap: bloat из-за долгих транзакций и частых обновлений больших строк.
- Vacuum/GC: неправильные пороги → или тормоза, или раздувание.
- Buffer pool: sequential flood, конфликт с ОС-кешем, длинные чекпоинты.
- B+-Tree: горячие ключи, расщепления, фрагментация, большие ключи.
- Hash: цепочки overflow при skew, нет диапазонов/ORDER.
- Bitmap: дорого в OLTP, полезно в OLAP (часто он-the-fly).
- Inverted: большие Posting-листы, сложные merge, отсроченные удаления.
- R-Tree: перекрытия MBR, деградация на высоких размерностях.
- LSM: write/read amplification, compaction stalls, tombstone-накопление.
- Bloom: неверный бюджет → высокий FP, бесполезность.
- WAL: нестабильный fsync, большие окна между чекпоинтами → долгий recovery.
- Планировщик: устаревшая статистика → неверные планы.
Мини-гид по тюнингу
- Описать профиль нагрузки: доли point-lookups, range-сканов, джоинов, апдейтов.
- Выбрать формат: row vs column vs гибрид; LSM при интенсивных записях.
- Спроектировать ключи/индексы: селективность, покрытие, порядок столбцов.
- Партиционирование: по времени/tenant/гео для изоляции I/O.
- Кэш: политика против sequential flood, размер пула vs RAM.
- Вакуум/GC/Compaction: разумные пороги, бюджет фоновых задач.
- Статистика: регулярный ANALYZE; extended stats для корреляций.
- Наблюдаемость: метрики по I/O, cache-hit, compaction, bloat, latency p95/p99.
Вопрос–Ответ (FAQ)
Q1. Когда выбирать hash-индекс вместо B+-Tree?
Если нужны только проверки равенства и есть риск «горячих» диапазонов, где B-Tree будет много листать. Но помните: никакого порядка и диапазонов.
Q2. Почему мой индекс не используется?
Низкая селективность, неверная статистика, лишние CAST/функции на левом аргументе, неподходящий порядок столбцов, тип сравнения, лимит памяти на сорт/хеш.
Q3. Что такое “covering index” и как понять, что он сработал?
Лист содержит все нужные столбцы для запроса. Признак — index-only scan (в плане) и резкое снижение обращений к таблице.
Q4. Как бороться с bloat?
Короткие транзакции, автовакаум с адекватными порогами, fillfactor на горячих таблицах, периодический REINDEX/CLUSTER при сильной фрагментации.
Q5. LSM плох для чтения?
Не обязательно: leveled-compaction + Bloom + подходящий размер SSTable дают стабильные p95. Но «холодные» диапазоны с широким разносом по уровням дороже.
Q6. Почему большие JSON/тексты тормозят всё?
Overflow-страницы ломают locality; вытаскивайте крупные поля в отдельные таблицы/хранилища и подгружайте по требованию.
Q7. В чём профит column-store?
Сканирует только нужные столбцы, хорошо сжимает, выполняет векторные операции — выигрыши 10×+ на аналитике. Но апдейты дорогие.
Q8. Что такое sequential flood и как его распознать?
Падение cache-hit и рост латентности OLTP во время больших сканов/ETL. Решение — сканы «мимо» горячего кэша, изоляция нагрузок.
Q9. Почему у меня «внезапно» долгие чекпоинты?
Слишком много «грязных» страниц, большой интервал между чекпоинтами, низкая пропускная способность диска. Увеличьте частоту и распараллеливание сбросов.
Q10. Когда использовать R-Tree, а когда B-Tree для гео?
Для геометрий/полигонов — R-Tree/GiST. Для простой сортировки/диапазонов по широте/долготе — иногда хватает композитного B-Tree (но без точных гео-предикатов).
Q11. Векторный поиск: как добиться стабильной латентности?
Тюнинг параметров ANN (M, ef, nlist), нормализация векторов, отложенные batch-обновления, периодические рекомпоновки индекса.
Q12. WAL «съедает» диск — что делать?
Ускорить чекпоинты/flush, включить архивирование/ротацию, следить за длинными транзакциями/репликацией, чтобы не удерживать старые сегменты.
Короткие “рецепты” под задачи
- Справочник по коду + быстрый поиск: B+-Tree по (code); если LIKE 'ABC%' — text_pattern_ops-варианты/функциональный индекс.
- Последние события по пользователю: индекс (user_id, created_at DESC) INCLUDE (...).
- Фильтрация по нескольким флагам/категориям (OLAP): битмапы + предагрегации.
- Логи/клики: LSM, ключ (tenant, ts), TTL, leveled compaction, Bloom.
- Полнотекст: инвертированный индекс + сегментные слияния; храните doc values для сортировок.
- Гео: R-Tree/GiST + предварительный bbox-фильтр, точная проверка вторым шагом.
- Векторный поиск: HNSW (RAM, высокий recall) или IVF(PQ) (RAM+диск, экономнее), регулярная перестройка.
Правильно выбранная физическая модель хранения и индексация дают те же 10–100× ускорения, что и «оптимизированный SQL», а часто — и больше. Начинайте с профиля нагрузки, выбирайте подходящий «семейный» набор структур (B-Tree/LSM/column), и только потом точечно тюньте параметры (страницы, кэш, вакуум/компакты, статистику). Обязательно закладывайте наблюдаемость: метрики compaction/vacuum, cache-hit, bloat, p95/p99 — без этого управление производительностью слепо.
