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

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

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

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

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

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

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

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

«Кучи»[править | править исходный текст]

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

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

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

B+ деревья[править | править исходный текст]

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

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

ISAM[править | править исходный текст]