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

• Обсуждение важности понимания работы одного компонента системы — сторожа.  

• План лекций: сначала анализ работы одной ноды, затем распределение, репликация и шардинг.  

• Пример сделки: покупка DataBricks опенсорсной базы данных Notion за миллиард долларов.  

• Объяснение преимуществ систем управления базами данных DBMS перед хранением данных в файлах.  

• DBMS обеспечивают независимость от формата хранения данных и конкурентный доступ.  

• Примеры проблем с файлами: необходимость переписывать программы при изменении схемы или формата.  

• Data independence: независимость от способа хранения данных.  

• Конкурентный доступ: управление транзакциями и одновременным доступом нескольких пользователей.  

• Crash recovery: сохранение данных на персистентный диск при отключении питания.  

• Security access control: управление доступом к данным.  

• Описание компонентов: команды, сервер, парсинг запросов, построение планов, выполнение планов.  

• Роль конкатенации, транзакционного менеджера, лок менеджера и recovery менеджера.  

• Компоненты: буфер-менеджер, диск-менеджер, данные в виде индекс-файлов и дата-файлов.  

• Пример архитектуры Rosh DB: компоненты Gateway, Executor, KV.  

• Особенности Notion: разделение PostgreSQL на компоненты компьютер и сторож, использование Amazon ES для репликации.  

• Архитектура TIBY: компоненты TIQV, взаимодействие через Raft, кластеризация.  

• Подчёркивание важности понимания компонентов для анализа новых решений.  

• Обещание детального разбора компонентов в следующих лекциях.  

• Обсуждение хранения данных в базе данных.  

• Пример с таблицей «юзерс» и её представлением на диске.  

• Упоминание движка INA DB и его формата файлов.  

• Необходимость управления записями в файле.  

• Проблемы с отслеживанием конца файла и свободного места.  

• Идея пейджинга для решения этих проблем.  

• Разбиение файла на блоки фиксированного размера.  

• Преимущества пейджинга для доступа к данным.  

• Логический юнит для работы с данными.  

• Хранение хедера в пейдже для проверки целостности данных.  

• Проверка свободного места в пейдже.  

• Пример хранения фиксированных по длине записей.  

• Трудности при удалении записей и отслеживании свободного места.  

• Необходимость различения записей разной длины.  

• Проблема определения начала и конца атрибутов в записи.  

• Использование фиксированных заголовков для атрибутов переменной длины.  

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

• Решение проблемы с атрибутами, превышающими размер пейджи.  

• Механизм оверфлоу пейджи для хранения данных, превышающих размер пейджи.  

• Ссылка на данные в оверфлоу пейдже из оригинальной пейджи.  

• Применение оверфлоу пейджи в PostgreSQL.  

• Добавление хедера фиксированной длины для каждой записи.  

• Указание на запись через хедеры фиксированной длины.  

• Пример использования подхода в PostgreSQL.  

• Хранение чек-суммы, LSN, версии и флагов в хедере пейджи.  

• Проверка свободного пространства в пейдже.  

• Хранение информации о транзакциях и версиях записей в хедерах записей.  

• Проблема вставки записей переменной длины после удаления других записей.  

• Необходимость отслеживания свободного места для вставки новых записей.  

• Необходимо удалить и переместить данные, чтобы освободить пространство.  

• При перемещении данных нужно пересобрать указатели.  

• Вакуум решает проблему с мёртвыми данными, помечая их для удаления.  

• Вакуум удаляет помеченные данные при следующем запуске.  

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

• Обсуждение альтернатив будет рассмотрено позже.  

• Колоночные базы данных работают с колонками, а не с пейджами.  

• Пример с записями в пейджах: «Влад», «7», «Олег», «5», «Игорь», «90».  

• Проблема: для расчёта статистики нужно извлекать весь пейдж, хотя требуется только одно число.  

• Переорганизация сторожа для хранения всех атрибутов рядом одного типа решает проблему.  

• Это позволяет извлекать только необходимые данные, избегая извлечения лишних элементов.  

• Хранение атрибутов рядом позволяет использовать сжатие и кодирование.  

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

• Проблема возникает при необходимости собрать запись обратно.  

• Для аналитического workload подходит один тип хранилища, для транзакционного — другой.  

• Тип хранилища напрямую влияет на работу с данными.  

• Системный каталог хранит метаданные о расположении таблиц и индексов.  

• Включает информацию о схеме, индексах и пользователях.  

• Буфер-пул загружает страницы с диска в память для ускорения доступа.  

• Выполняет функции кэширования и управления страницами.  

• Поддерживает различные стратегии управления страницами, включая LRU.  

• LRU наименее недавно использованные страницы.  

• Часто используемые страницы остаются в кэше.  

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

• Индексы ускоряют поиск данных в таблицах.  

• Примеры индексов: бинарные, хэш-индексы.  

• Кластеризованные индексы определяют порядок хранения записей в файлах.  

• Некластеризованные индексы не диктуют порядок хранения записей.  

• Пример: в MySQL первичный индекс кластеризованный, а в PostgreSQL используется heap-организация файлов.  

• Праймерик-индекс отвечает за уникальность записей, но не за их порядок.  

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

• Порядок записей необходим для построения разряженных индексов.  

• Секонд-индексы используются для поиска по вторичным атрибутам, например, по департаменту или зарплате.  

• Могут указывать на конкретную запись или хранить ссылку на первичный индекс.  

• Второй вариант добавляет дополнительный слой дирекции, но не требует обновления при перемещении страниц.  

• Хэш-индексы используют хэш-функцию для распределения значений по бакетам.  

• Проблемы: неравномерное распределение данных, необходимость обновления при перемещении страниц.  

• Преимущества: быстрое нахождение конкретных значений.  

• Не подходят для поиска диапазонов значений.  

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

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

• Проблема: перестройка дерева при добавлении новых значений.  

• B+Tree+: значения хранятся только в листовых нодах, указатели на соседние ноды упрощают поиск диапазонов, но требуют более сложной реализации при добавлении новых значений.  

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

• При перемещении страниц необходимо обновлять указатели.  

• Реализация B+Tree+ сложнее, но позволяет быстрее сканировать данные.  

• B+Tree требует полной перестройки дерева при модификации записей.  

• Оптимизация B-Epsilon позволяет накапливать изменения в буфере и перестраивать дерево постепенно.  

• Проблема оптимизации: необходимость проверки наличия записи в буфере при чтении.  

• Битмап индекс используется для атрибутов с фиксированным количеством значений.  

• Пример использования: проверка наличия записи с определённым значением в таблице.  

• Пример: проверка наличия «фейл л2» в таблице с помощью битовой маски.  

• Инвертированный индекс помогает быстро находить записи, содержащие определённые слова.  

• Пример применения: поиск песен с словом «любовь» или его производными.  

• Инвертированный индекс создаёт таблицу, где для каждого слова указано, в каких записях оно встречается.  

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

• Имбединги генерируются через модель, которая преобразует текст в вектор.  

• Векторы сопоставляются с метаданными, что позволяет находить похожие записи.  

• R-Tree понимает геометрию и минимизирует нахлёсты между диапазонами.  

• Пример использования: поиск кафешек между двумя точками на карте.  

• R-Tree строит иерархию диапазонов, минимизируя площадь и пересечение диапазонов.  

• R-Tree строится специфично, минимизируя метрику и площадь диапазонов.  

• При добавлении новой ноды R-Tree старается минимизировать площадь покрывающего диапазона и пересечение с другими диапазонами.  

• Балансировка диапазонов обеспечивает равномерное распределение данных по дереву.  

• Структура данных поддерживает высоту дерева и минимизирует площадь покрытия.  

• Применяется в геймдеве для определения, какую часть экрана нужно показать.  

• Работает в многомерных пространствах, включая трёхмерные.  

• Существуют различные вариации структуры данных, включая R3, R+3 и звёздочку R3.  

• Обсуждены сторож и индексы.  

• Упоминается использование LSM в различных приложениях.  

• Пример использования LSM в Rockstar Games.  

• LSM — это другой подход к сторожу.  

• Проблема с деревом B+3: необходимость перестройки и ребалансировки при добавлении данных.  

• LSM поддерживает heavy real-time workloads без необходимости перестройки дерева.  

• Записи добавляются в мем-таблицу, которая может быть красно-чёрным деревом, скип-листом или B-деревом.  

• При переполнении мем-таблицы данные сбрасываются в SST-файлы на диске.  

• SST-файлы компактно сливаются, образуя новые слои.  

• Мем-таблица хранит данные отсортированными.  

• Каждый SST-файл также содержит отсортированные данные.  

• Запись данных происходит в мем-таблицу, при переполнении данные сбрасываются на диск.  

• Чтение данных начинается с проверки мем-таблицы, затем данные могут быть прочитаны с диска.  

• Уровни SST-файлов позволяют поддерживать ограниченную длину файлов.  

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

• Файлы остаются мутабельными после слияния, что позволяет архивировать историю изменений.  

• Это позволяет возвращаться к определённым точкам в истории данных.  

• Левел тайринг использует диапазоны ключей для упрощения поиска.  

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

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

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

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

• Это обеспечивает точность и эффективность поиска, ускоряя процесс.  

• Веб-сайт Compak Шри предлагает различные стратегии для управления таблицами.  

• Можно настраивать параметры компактирования, включая размер таблиц и уровни.  

• Стратегии включают левел и тайер.  

• Файлы последовательно добавляются и сливаются в таблицы.  

• После добавления последнего файла все данные смешиваются и добавляются на уровень ниже.  

• Можно тестировать различные стратегии компактирования и оценивать производительность.  

• Каждый SST файл разбивается на логические блоки пейджи.  

• Блок кэш позволяет хранить данные в памяти.  

• Данные защищаются с помощью write-ahead-lock перед записью в мем-таблицу.  

• Манифест-лок отслеживает состояние SST файлов.  

• Мем-таблица использует структуру данных скип-лист.  

• Скип-лист применяется в Discord для оптимизации операций.  

• Скип-лист — вероятностная структура данных с сложностью O(logn).  

• При добавлении элемента значение может «прорасти» на несколько уровней вверх.  

• Пересечение уровней может привести к ошибкам, но это нормально.  

• Скип-лист — это структура данных, где значения «прорастают» наверх на несколько этажей.  

• Количество этажей, на которое «прорастает» значение, определяется случайным образом.  

• Для вставки значения нужно проверить, где оно находится относительно других значений, и вставить его в нужное место.  

• Благодаря рандому значения «прорастают» так, что в среднем получается логарифмическое распределение.  

• Логика работы скип-листа напоминает указатели в B-дереве.  

• Значения хранятся в отсортированном виде, что упрощает работу с ними.  

• Рекомендуется решить задачу на лит-коде, связанную со скип-листом.  

• Это поможет лучше понять структуру данных и её особенности.  

• Обсуждается использование LSM сторожа для управления данными.  

• LSM сторож позволяет легче дробить и шордировать значения.  

• Рекомендуется изучить репозиторий Talent Plan для построения сторожа на основе LSM.  

• Запрос сначала попадает в парсер-транслятор, который проверяет его валидность.  

• Из запроса строится выражение реляционной алгебры.  

• Оптимизатор собирает статистику о данных и выбирает оптимальный план выполнения запроса.  

• Оптимизатор использует законы эквивалентности для перестройки выражения запроса.  

• Примеры законов: коммутативность, ассоциативность, декартово произведение.  

• Перестройка выражения позволяет оптимизировать запрос без изменения его логики.  

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

• Упоминается, что лекция проводится в учебном формате.