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

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

Произвольное хранение

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

Последовательное хранение

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

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

«Кучи»

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

Hash корзины

• Хэш-функции вычисляют адрес страницы, на которой будет храниться запись, на основе одного или более полей в записи
  • Функции хэширования, выбираются для того, чтобы обеспечить равномерное распределение адресов через адресное пространство
  • ‘размещение’ как правило, 40 % — 60 % от общего размера файла
  • уникальный адрес не гарантируется этим методом, поэтому необходимы механизмы определения столкновений и механизмы исправления столкновений

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

B+ деревья

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

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

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.