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

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

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

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

Заказал

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

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

Куча файлов

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

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

Хеш-корзины

Основная статья: Хэш-таблица

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

Деревья B+

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

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

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

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

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

См. также

• Индекс базы данных
• ИСАМ