Структуры хранения базы данных - Database storage structures

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

Неупорядоченный

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

Упорядоченный

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

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

Файлы кучи

Файлы кучи - это списки неупорядоченных записей переменного размера. Несмотря на то, что они имеют схожее имя, файлы кучи сильно отличаются от куч в памяти . Кучи в памяти упорядочены, а не файлы кучи.

  • Самый простой и самый простой способ
    • эффективная вставка, с добавлением новых записей в конец файла в хронологическом порядке
    • поиск эффективен, когда дескриптор памяти является адресом памяти
    • поиск неэффективен, так как поиск должен быть линейным
    • удаление осуществляется путем пометки выбранных записей как «удаленных»
    • требует периодической реорганизации, если файл очень изменчив (часто меняется)
  • Преимущества
    • эффективен для массовой загрузки данных
    • эффективен для относительно небольших отношений, поскольку исключаются накладные расходы на индексацию
    • эффективен, когда поиск включает большую часть хранимых записей
  • Недостатки
    • неэффективен для выборочного поиска с использованием ключевых значений, особенно если они большие
    • сортировка может занять много времени
    • не подходит для летучих таблиц

Хеш-сегменты

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

B + деревья

Основная статья: B + tree

Это наиболее часто используемые на практике.

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

Ориентация на данные

В большинстве обычных реляционных баз данных используется «строковое» хранилище, что означает, что все данные, связанные с данной строкой, хранятся вместе. В отличие от этого, СУБД с ориентацией на столбцы хранят все данные из одного столбца вместе, чтобы быстрее обслуживать запросы в стиле хранилища данных. Базы данных корреляции похожи на базы данных на основе строк, но применяют уровень косвенности для сопоставления нескольких экземпляров одного и того же значения с одним и тем же числовым идентификатором.

Смотрите также