Структуры хранения в базе данных

Структуры хранения в базе данных — структуры СУБД, обеспечивающие хранение данных, и как правило независимые от логической структуры данных. Структура хранения может быть изменена без затрагивания кода приложения и не влияет на семантику запросов. В редких случаях знание структуры хранения позволяет дополнительно оптимизировать запросы. Под структурой хранения (англ. storage structure) понимается привязка структуры данных к её реализации, которая может быть другой структурой данных.

Проектирование структуры хранения затрагивает:

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

и т. п.

Таблицы и индексы баз данных обычно хранятся на жестком диске в одной из многочисленных форм, в пронумерованных / ненумерованных Flat-файлах, ISAM, «Кучах», Hash-корзинах или B+ деревьях. Наиболее часто используются B+ деревья и ISAM.

Пример

В Oracle Database Express Edition имеет структуры хранения на трёх уровнях:

• Логические структуры (tablespaces)
• Физические структуры (файлы данных, временные файлы, файлы конфигурации и файл с паролями)
• Структуры восстановления данных после сбоя (резервные копии файлов, логи и т. п.)

Неупорядоченное хранение

Неупорядоченное хранение — записи хранятся в порядке вставки, поэтому время вставки быстрое ($O\left(1\right)$). Поиск же, на первый взгляд, неэффективен (O(n)), но это, как правило, неважно, так как большинство баз данных используют индексы на первичных ключах, дающих сложность $O\left(\log n\right)$ или $O\left(1\right)$.

Упорядоченное хранение

Упорядоченное хранение — записи хранятся по порядку; вставка может потребовать увеличения размера файла и его переупорядочивания, что очень неэффективно. Но поиск здесь эффективнее, так как записи предварительно отсортированы, его сложность $O\left(\log n\right)$.

Структурированные файлы

«Кучи»

• Простейший метод
  • Делает эффективным добавление новых записей. Записи добавляются в конце файла — 'хронологический' порядок
  • Неэффективный поиск так как поиск должен быть линейным
  • Удаление — чтобы удалить помеченные записи, требуется периодическая реорганизация, если файл очень неустойчивый
• Преимущества
  • хорош для загрузки больших объёмов данных
  • хорош для относительно небольших отношений, так как избегаются излишние расходы при индексации
  • Подходит, когда извлечение привлекает большую часть записей
• Недостатки
  • Не эффективен для селективного поиска с помощью ключевых слов
  • Сортировка может вызывать затруднения
• Не подходит для ‘временных’ таблиц

Хеш-корзины

 → Хеш-таблица

Хеш-функции вычисляют адрес страницы, на которой будет храниться запись, на основе одного или более полей в записи

• функции хеширования выбираются так, чтобы обеспечить равномерное распределение адресов по адресному пространству
• заполнение, как правило, должно составлять 40–60% от общего размера файла
• уникальность адресов не гарантируется, поэтому используются механизмы определения и разрешения коллизий:
  • открытая адресация
  • цепочки переполнения

Плюсы и минусы:

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

B+-деревья

 → B+-дерево

Наиболее часто используются на практике.

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

ISAM

 → ISAM

Литература

• Adrienne Watt, Nelson Eng, Database Design - 2nd Edition
• Fry, J. P. (1970). Introduction to Storage Structure Definition. ACM SIGFIDET Workshop on Data Description and Access.
• McGee, W. C. (1972). Informal Definitions for the Development of a Storage Structure Definition Language. ACM SIGFIDET Workshop on Data Description and Access, 13-55.
• Emmanuel J. Yannakoudakis The Architectural Logic of Database Systems. — Springer Science & Business Media, 2012. — P. 87-90. — ISBN 978-1-4471-1616-5.

Ссылки

• Лекция 9: Физические модели данных (внутренний уровень), 9.3. Организация обмена между оперативной и внешней памятью, Академия Microsoft: Базы данных, Интуит
• Лекция 11: Хранение данных и доступ к ним, Модели и смыслы данных в Cache и Oracle, Интуит
• Лекция 11: Хранение данных и доступ к ним, Лекция 3: Теоретико-графовые модели данных, Интуит