Video Thumbnail

База по Базам Данных - Storage (Индексы, Paging, LSM, B+-Tree, R-Tree) | Влад Тен Систем Дизайн

Влад Тен01:37:34
https://www.youtube.com/watch?v=i-FFVM4cIXQ

Содержание

Краткое резюме

  • Системы управления базами данных (СУБД) необходимы для абстрагирования хранения, управления конкурентным доступом, восстановления после сбоев и контроля безопасности.
  • Классическая архитектура реляционных СУБД включает построение оптимальных планов выполнения SQL-запросов, буферный пул для кеширования страниц и менеджмент дискового пространства.
  • Сторедж строится из фиксированных страниц (pages), разбитых на записи с поддержкой переменных и фиксированных размеров, что требует сложных структур данных и механизма вакуума.
  • Различают row-oriented (хранение построчно) и column-oriented (по столбцам) модели, подходящие для OLTP и OLAP задач соответственно.
  • Для индексации используются разные типы: хэш-индексы (для точечного поиска), B+-деревья (для диапазонного поиска), bitmap и инвертированные индексы (для категориальных и полнотекстовых данных), а также геоиндексы (R-tree).
  • Альтернативный сторедж — LSM-деревья (Log-Structured Merge-trees), реализованные в RocksDB: быстрые записи, медленные чтения, с помощью слияния слоёв и bloom-фильтров для ускорения запросов.
  • Skip list — вероятностная структура для быстрой сортировки и поиска, используемая в LSM-движках.
  • Оптимизатор SQL-запросов преобразует запрос в реляционную алгебру и перестраивает план выполнения на основе статистики и законов эквивалентности для максимальной эффективности.

Введение в СУБД и их назначение

Системы управления базами данных (DBMS) нужны для удобного, безопасного и эффективного хранения больших объемов данных. Хранение в простых файлах, например, CSV или Excel, не обеспечивает:

  • Независимость данных (data independence): абстракция доступа к данным независимо от их физического формата.
  • Контроль конкурентного доступа (concurrency control): правильное управление одновременными запросами, предотвращение конфликтов обновления.
  • Восстановление после сбоев (crash recovery): сохранение целостности данных, откат незавершённых операций.
  • Управление доступом (security access control): разграничение прав пользователей к разным частям базы.

«СУБД забирает от нас часть самых больных проблем с файлами и при этом даёт мощные абстракции и гарантии.»

Архитектура реляционной СУБД

Классическая реляционная СУБД состоит из нескольких ключевых компонентов:

  • Query Evaluation Engine: преобразование SQL-запроса сначала в реляционные выражения, затем в планы выполнения, выбор оптимального плана на основе статистики о данных.
  • Concurrency Control и Transaction Manager: управление транзакциями, блокировками, версиями данных.
  • Log Manager и Recovery Manager: ведение журналов изменений (write-ahead log) и механизмов восстановления после сбоев.
  • Buffer Manager (буферный пул): кеширует страницы с данными из диска в память, управляет политиками вытеснения (например, LRU).
  • Disk Space Manager: отвечает за физическое размещение страниц на диске.
  • Файлы данных, индексы и системный каталог: хранят сами данные, вспомогательные структуры и метаданные о таблицах и индексах.

«Мы не строим все с нуля, а ориентируемся на реальные решения, понимая, как движущиеся части складываются в пазл.»

Организация стореджа: страницы и запись

Для хранения данных используется концепция страниц (pages) фиксированного размера (4KB, 8KB и др.), которые разбивают файлы таблиц:

  • Каждая таблица — отдельный файл со страницами.
  • Страница содержит заголовок, описывающий состояние и свободное место.
  • Записи в странице могут быть фиксированной длины — просто друг за другом.
  • Для переменных длины записей структура записей усложняется: у каждой записи есть заголовок с указателями на поля переменной длины.
  • Имеется также механизм overflow pages (переполнения), куда выносятся слишком большие поля (например, большие JSON или BLOB).

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

Обработка удалений: Vacuum

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

  • СУБД помечают записи как удалённые.
  • Периодически запускается Vacuum — процесс «сборки мусора», который освобождает место, сдвигает записи, обновляет указатели.

Это комплексный процесс, требующий внимательного учёта потенциальных конкурирующих операций.

Способы хранения данных: Row-oriented vs Column-oriented

  • Row-oriented (запись построчно) — классический подход, полезен для транзакционных систем (OLTP).
  • Column-oriented (хранение по столбцам) — оптимален для аналитических систем (OLAP): при вычислении агрегатов на одном столбце читается меньше данных, возможна лучшая компрессия и векторные операции.

«Хранение по столбцам позволяет выгребать только нужные атрибуты и вычислять агрегаты очень эффективно.»

Метаданные и системный каталог

Системный каталог — «директория» по таблицам, индексам и правам доступа:

  • Где лежит таблица, какие индексы затронуты?
  • Какая схема у таблицы?
  • Кто может её читать или изменять?

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

Буферный пул и политика кеширования

Доступ к данным с диска медленный (микросекунды), а из памяти — очень быстрый (наносекунды). Для ускорения:

  • Используется буферный пул — кеш страниц из диска.
  • Задача — эффективно загружать нужные страницы и решать, какую вытеснить.
  • Простая политика — FIFO, подходит плохо.
  • Часто используется LRU (Least Recently Used) — вытесняет страницу, которую давно не трогали.
  • Проблема LRU — последовательное чтение (sequential flooding): один тяжелый запрос «прогревает» кеш и вытесняет часто используемые данные.

Индексы: кластеризованные, некластеризованные и виды структур

  • Кластеризованный индекс диктует физический порядок записей по ключу.
  • Некластеризованный — отдельная структура, указывающая на записи.

Типы индексов:

  • Хэш-индексы: отличный для точечных запросов (например, «найти по exact match»), но не поддерживают диапазонные запросы.

  • B+-деревья (B+Tree): универсальные структуры для быстрого диапазонного поиска и точных значений.

    Классический B-дерево хранит ключи и данные везде, при вставках требует частых ребалансировок.

  • B+Tree хранит все данные только в листовых узлах, что улучшает скорость обхода диапазонов.

«B+-дерево позволяет эффективно находить диапазоны значений и делает сканирование линейным.»

  • Bitmap индексы — используют битовые маски для атрибутов с ограниченным числом значений (пол, уровень, категория).
  • Инвертированные индексы — для полнотекстового поиска, поисковых систем (напр. Elasticsearch).
  • Векторные базы (embedding indices) — для семантического поиска с помощью векторных представлений (например, для понимания смысла текста, поиска похожих песен).
  • Геоиндексы (R-tree и его вариации) — для пространственного поиска по двум и более измерениям.

LSM Storage: Log-Structured Merge-trees

LSM-деревья оптимизированы для интенсивных записей:

  • Данные сначала попадают в memtable — структура в памяти (красно-чёрное дерево, skip list).
  • При переполнении memtable сбрасывается в SST-файл — отсортированный файл на диске.
  • SST-файлы компактифицируются и сливаются для уменьшения фрагментации и оптимизации чтений.
  • Все файлы иммутабельны — не модифицируются на месте, что упрощает параллелизм и версионирование.
  • Для ускорения поиска используются bloom-фильтры — позволяют быстро проверить, есть ли ключ в файле, с небольшой ошибкой типа «ложное присутствие» (false positive).

«LSM-сторедж — это стройная цепочка memtable → SST-файлы → компактификация, обеспечивающая высокую скорость записи.»

Skip list: вероятностная структура данных

  • Skip list — вероятностная структура, ускоряющая поиск по отсортированному списку.
  • Работает как несколько уровней связных списков, где верхний уровень «перескакивает» через данные.
  • Средняя сложность поиска, вставки и удаления — O(log n).
  • Используется в RocksDB и других LSM-движках для реализации memtable.

Оптимизация чтения и слияние SST-файлов

  • При чтении нужно искать в нескольких SST-файлах разных уровней.
  • Используются разные стратегии слияния (leveling, tiering) для управления количеством файлов и увеличения производительности.
  • Важна сортировка данных для упрощения операций слияния.

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

  • Запрос сначала парсится в валидный SQL.
  • Преобразуется в выражение реляционной алгебры — дерево операторов (проекции, фильтры, джойны и т.д.).
  • Оптимизатор преобразует дерево, используя законы эквивалентности (коммутативность, ассоциативность, переноса условий) для постановки запроса в более эффективный вид.
  • Выбирается оптимальный план с помощью статистики (количество строк, уровень прогрева данных, наличие индексов).
  • План выполняется, даёт результат.

«Оптимизатор строит такое выражение, которое эквивалентно исходному запросу, но выполняется быстрее и эффективнее.»

Заключение

Этот урок подробно раскрывает внутренности стореджа СУБД и связанные компоненты — от хранения байт в страницах до сложных индексов и оптимизаций SQL-запросов. Был охвачен широкий спектр тем:

  • Основания и мотивация создания СУБД.
  • Архитектура реляционной базы.
  • Механизмы хранения, управления страницами и вакуум.
  • Различия row vs column форматов.
  • Классические индексы: хэш, B+, bitmap, инвертированные, гео.
  • Современные подходы с LSM-деревьями.
  • Использование probabilistic структур (skiplist, bloom filter).
  • Введение в оптимизацию планов SQL-запросов.

Эти знания помогут разбираться в технических особенностях баз данных, понимать новости рынка, технологии и принимать обоснованные решения по выбору СУБД и проектированию систем хранения.

📚 Разработка и внедрение распределённых баз данных — не простая задача, но понимание основ одной ноды стореджа — фундамент для будущих масштабируемых решений.