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

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

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

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

Заказал

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

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

Файлы кучи

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

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

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

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

B + деревья

Основная статья: B + дерево

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

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

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

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

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