База по Базам Данных - 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 наименее недавно использованные страницы.  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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