Таблицы и индексы базы данных могут храниться на диске в одной из нескольких форм, включая упорядоченные/неупорядоченные плоские файлы , ISAM , файлы кучи, хэш-корзины или деревья B+ . Каждая форма имеет свои собственные преимущества и недостатки. Наиболее часто используемые формы — это B-деревья и ISAM. Такие формы или структуры являются одним из аспектов общей схемы, используемой ядром базы данных для хранения информации.
Неупорядоченный
Неупорядоченное хранилище обычно хранит записи в порядке их вставки. Такое хранилище обеспечивает хорошую эффективность вставки ( ), но неэффективное время извлечения ( ). Однако обычно это время извлечения лучше, поскольку большинство баз данных используют индексы на первичных ключах , что приводит к времени извлечения или для ключей, которые совпадают со смещениями строк базы данных в системе хранения. [ необходима цитата ]
Заказано
Упорядоченное хранилище обычно хранит записи по порядку и может быть вынуждено переупорядочивать или увеличивать размер файла при вставке новой записи, что приводит к снижению эффективности вставки. Однако упорядоченное хранилище обеспечивает более эффективное извлечение, поскольку записи предварительно сортируются, что приводит к сложности . [ необходима цитата ]
Структурированные файлы
Куча файлов
Файлы кучи — это списки неупорядоченных записей переменного размера. Несмотря на схожее название, файлы кучи сильно отличаются от куч в памяти . Кучи в памяти упорядочены, в отличие от файлов кучи.
- Самый простой и базовый метод
- эффективная вставка, при этом новые записи добавляются в конец файла, обеспечивая хронологический порядок
- извлечение эффективно, когда дескриптор памяти является адресом памяти
- поиск неэффективен, так как поиск должен быть линейным
- удаление осуществляется путем пометки выбранных записей как «удаленных»
- требуется периодическая реорганизация, если файл очень изменчив (часто изменяется)
- Преимущества
- эффективен для массовой загрузки данных
- эффективно для относительно небольших отношений, поскольку избегаются накладные расходы на индексацию
- эффективно, когда извлечение данных затрагивает большую часть хранимых записей
- Недостатки
- неэффективно для выборочного поиска с использованием ключевых значений, особенно если они большие
- сортировка может занять много времени
- не подходит для изменчивых таблиц
Хэш-ведра
- Хэш-функции вычисляют адрес страницы, на которой должна быть сохранена запись, на основе одного или нескольких полей в записи.
- функции хеширования, выбранные для обеспечения равномерного распределения адресов по всему адресному пространству
- «заполняемость» обычно составляет от 40% до 60% от общего размера файла.
- уникальность адреса не гарантируется, поэтому требуются механизмы обнаружения и разрешения коллизий
- Открытая адресация
- Связанное/несвязанное переполнение
- Плюсы и минусы
- эффективно для точных совпадений по ключевому полю
- не подходит для извлечения диапазона, требующего последовательного хранения
- вычисляет, где хранится запись, на основе полей в записи
- хэш-функции обеспечивают равномерное распределение данных
- возможны столкновения, поэтому требуется обнаружение и восстановление столкновений
Деревья B+
Они наиболее часто используются на практике.
- Время, необходимое для доступа к любой записи, одинаково, поскольку выполняется поиск по одинаковому количеству узлов.
- Индекс является полным индексом, поэтому файл данных не нужно упорядочивать.
- Плюсы и минусы
- универсальная структура данных – как последовательный, так и произвольный доступ
- доступ быстрый
- эффективно поддерживает точное, диапазонное, частичное совпадение ключей и совпадение по шаблону.
- Изменяемые файлы обрабатываются эффективно, поскольку индекс является динамическим — расширяется и сжимается по мере увеличения и уменьшения таблицы.
- менее подходит для относительно стабильных файлов – в этом случае ISAM более эффективен
Ориентация данных
Большинство традиционных реляционных баз данных используют «строчно-ориентированное» хранилище, что означает, что все данные, связанные с данной строкой, хранятся вместе. Напротив, столбчато-ориентированные СУБД хранят все данные из данного столбца вместе, чтобы быстрее обслуживать запросы в стиле хранилища данных . Корреляционные базы данных похожи на строковые базы данных, но применяют слой косвенности для сопоставления нескольких экземпляров одного и того же значения одному и тому же числовому идентификатору.
Смотрите также
