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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

и т. п.

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

Пример[править | править вики-текст]

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

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

Неупорядоченное хранение[править | править вики-текст]

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

Упорядоченное хранение[править | править вики-текст]

Упорядоченное хранение — записи хранятся по порядку; вставка может потребовать увеличения размера файла и его переупорядочивания, что очень неэффективно. Но поиск здесь эффективнее, так как записи предварительно отсортированы, его сложность .

Структурированные файлы[править | править вики-текст]

«Кучи»[править | править вики-текст]

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

Хеш-корзины[править | править вики-текст]

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

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

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

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

B+-деревья[править | править вики-текст]

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

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

ISAM[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Новиков Борис. Настройка приложений баз данных. — БХВ-Петербург, 2006. — С. 55–56. — ISBN 978-5-94157-840-5.
  2. Oxfordreference
  3. About the Database Storage Structures , 2 Day DBA, 2006, Oracle

Литература[править | править вики-текст]

  • 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.

Ссылки[править | править вики-текст]