Файл: Реферат Организация доступа к данным Страницы и файлы.docx
Добавлен: 08.11.2023
Просмотров: 32
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Индексы бинарного типа являются частным случаем древовидного индекса и состоят из двух частей: набора последовательностей и набора индексов.
Набор последовательностей представляет собой индекс, содержащий указатели на все записи в файле. Этот индекс физически упорядочен, обычно по значению первичного ключа. Это позволяет обращаться к записям последовательно, считывая один за другим адреса записей из последовательного набора и по ним считывая сами записи.
Набор индексов - это неплотный иерархический индекс для последовательного набора.
Бинарные деревья по определению являются сбалансированными, т.е., все записи находятся на одинаковом расстоянии от корневого уровня индексного набора, а справа от корневого значения находится столько же значений, сколько и слева. При изменении индексируемого множества применяется специальный алгоритм, который реорганизует все дерево и сделает его сбалансированным.
3. Хеширование
индексирование хеширование диск
Альтернативным и не менее эффективным способом ускорения доступа к данным является использование техники хеширования. Хешированием, хеш-адресацией или хеш-индексированием называется технология быстрого прямого доступа к хранимой записи на основе заданного значения некоторого поля. При этом не обязательно, чтобы поле было ключевым. Ниже перечислены основные черты этой технологии.
Каждая хранимая запись базы данных размещается по адресу (RID-указателю или номеру страницы), который вычисляется с помощью специальной хеш-функции на основе значения некоторого поля данной записи, называемого хеш-полем.
Для сохранения записи в СУБД сначала вычисляется хеш-адрес новой записи, а затем диспетчер файлов помещает эту запись по вычисленному адресу.
Для извлечения нужной записи по заданному значению хеш-поля в СУБД сначала вычисляется хеш-адрес, а затем диспетчеру файлов посылается запрос для извлечения записи по вычисленному адресу.
В качестве иллюстрации предположим, что у нас есть записи с данными о поставщиках с номерами 100, 200, 300, 400 и 500 (вместо П1, П2, ПЗ, П4, П5 в нашем примере), для хранения каждой из них предназначается отдельная страница, а в качестве хеш-функции используется следующая:
хеш-адрес (т.е. номер страницы или RID-указатель) = остаток от деления на 13 числа, содержащегося в поле П №
Это простейший пример общего класса хеш-функций типа деление / остаток (в качестве делителя следует выбирать простое натуральное число). В этом примере номерами страниц для заданных записей будут 9, 5, 1, 10 и 6 соответственно.
В общем случае, для определения адреса вместо хеш-функции можно было бы использовать непосредственно значение ключевого поля (если это поле имеет числовой тип данных). Однако такой способ нежелателен, поскольку диапазон возможных значений ключевого поля может быть гораздо шире диапазона имеющихся адресов. В нашем примере номера записей с данными о поставщиках находятся в диапазоне 000-500, тогда как в действительности может быть только несколько реальных поставщиков. Таким образом, во избежание неэффективного использования дискового пространства следует найти такую хеш-функцию, чтобы можно было сузить диапазон 000-500, например, до 0-9. Для того чтобы зарезервировать дополнительное пространство (рекомендуется 20% от исходной величины), диапазон 0-9 в нашем примере расширен до 0-12 за счет делителя 13.
В этом примере также наглядно проявляется недостаток хеширования. Физическая последовательность записей внутри хранимого файла почти всегда отличается от последовательности ключевого поля, а также любой другой логически заданной последовательности. К тому же, между последовательно размещенными записями могут быть промежутки неопределенной протяженности, т.к. страницы заполняются неравномерно. Практически всегда физическая последовательность записей в хранимом хешированном файле не имеет ничего общего с заданной в нем логической последовательностью.
Еще одним недостатком хеширования является возможность возникновения коллизий, т.е. ситуаций, когда две или более различных записи имеют одинаковые адреса. Допустим, что файл поставщиков из предыдущего примера (с поставщиками 100, 200 и т.д.) содержит также поставщика с номером 1400. При использовании хеш-функции типа «остаток от деления на 13» возникнет коллизия (по адресу 9) с записью 100. Ясно, что такая хеш-функция неадекватна и для устранения коллизий необходимо ее исправить.
Наиболее часто на практике для разрешения коллизий используется значение хеш-функции в качестве адреса не какой-либо записи с данными, а точки привязки. Точка привязки - это начальный адрес цепочки указателей (цепочки коллизий), связывающей вместе все записи или все страницы с записями, которые имеют одинаковый хеш-адрес. Внутри цепочки коллизий записи также могут быть упорядочены согласно хеш-полю для упрощения последующего поиска.
Еще один недостаток описанного выше способа хеширования - возрастание числа коллизий с увеличением размера хранимого файла. Это, в свою очередь, может привести к значительному увеличению среднего времени доступа, поскольку все больше и больше времени придется тратить на поиск записей в наборах конфликтующих записей. Однако этот недостаток можно устранить, если реорганизовать файл, т.е. выгрузить данный файл и загрузить его вновь, используя новую хеш-функцию. Для этого используют метод расширяемого хеширования, основанный на технологии B-деревьев с расщеплениями и слияниями, благодаря которой потребуется не более двух доступов к диску для поиска заданной записи (т.е., записи, имеющей заданное значение ключевого поля), а в некоторых случаях будет достаточно даже одного доступа независимо от размера файла.
Литература
1. Туманов, В.Е. Основы проектирования реляционных баз данных; Бином, 2012. - 420 c.
2. Уорден, К. Новые интеллектуальные материалы и конструкции. Свойства и применение; М.: Техносфера, 2012. - 456 c.
. Федоров, Алексей; Елманова, Наталья Введение в OLAP-технологии Microsoft; М.: Диалог-МИФИ, 2008. - 473 c.
. Фейерштейн, С.; Прибыл, Б. Oracle PL/SQL для профессионалов; СПб: Питер, 2012. - 540 c.
. Фуллер, Лори Ульрих; Кауфельд, Джон; Кук, Кен Microsoft Office Access 2007 для «чайников»; М.: Вильямс, 2012. - 384 c.
. Хаббард, Дж. Автоматизированное проектирование баз данных; М.: Мир, 2011. - 453 c.
. Хабрейкен, Джо; Хайден, Мэтт Освой самостоятельно сетевые технологии за 24 часа; М.: Вильямс, 2008. - 432 c.
. Шаймарданов, Р.Б. Моделирование и автоматизация проектирования структур баз данных; М.: Радио и связь, 2008. - 469 c.