Многосписочные структуры на физическом уровне базы данных

Размещено на http://www.allbest.ru/

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра программного обеспечения информационных технологий

Факультет ЗВиДО

Специальность ПОИТ

Контрольная работа №1

по дисциплине «Базы данных.ч.1»

Вариант № 6

Выполнил студент: Цыбулько А.А.

группа 491051

Вопрос 1. Многосписочные структуры на физическом уровне базы данных

Представим некоторую группу студентов, данные о которых сохранены в виде следующей таблицы:

Рисунок 1 - Простейший пример сохраняемой таблицы

Поле Номер зачётной книжки является первичным ключом для каждого экземпляра записи. Предположим, что у нас возникла потребность сохранить эти данные. Самым простым способом будет создание файла для хранения, содержащего по одному экземпляру записи для каждого студента. Однако, при увеличении количества записей существенно возрастёт объём занимаемой памяти.

Если мы воспользуемся методом факторизации по значению поля то получим результат, показанный на рисунке 2.

Рисунок 2 - Метод факторизации по значению поля

В данном случае у нас есть два хранимых файла: файл студентов и файл факультетов с указателями из первого во второй. Эти указатели представляют собой адреса хранимых записей. При использовании данного метода указатель занимает меньше памяти, чем название факультета, что позволит сэкономить некоторый объём памяти. Однако, данный метод не лишён недостатков.

Запрос на поиск всех студентов, обучающихся на определённом факультете, будет содержать большее число операций доступа.

В случае использования способа индексирования по полям также есть два хранимых файла: файл студентов и файл факультетов, но в этом случае указатели установлены из второго файла (факультетов) в первый (студентов).

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

Рисунок 3 - Метод индексирования по полям

Следует заметить, что файл «Факультеты» служит индексом для файла «Студенты». Он управляется СУБД, но не методом доступа. Фактически это т.н. «плотный вторичный индекс» («плотный» означает, что индекс содержит отдельную запись для каждого экземпляра хранимой записи индексируемого файла, «вторичный» означает, что индексируемое поле не является первичным ключом). В этом случае (поскольку индекс - плотный) индексируемый файл не должен содержать индексируемое поле (в этом примере файл «Студенты» не включает поле Факультеты).

После рассмотрения вышеописанных способов естественным логическим выводом будет решение соединить два предыдущих варианта представления, чтобы получить преимущество каждого за счёт потери большего объёма памяти и за счёт необходимости прилагать больше усилий для поддержания указателей при изменениях. Это комбинация простых представлений, показанная на рисунке 4.

Рисунок 4 - Комбинация простых представлений

Однако и данный способ обладает существенным недостатком. Это непредсказуемое число указателей в каждом элементе индекса, т.е. в каждом экземпляре хранимой записи в индексе. Это усложняет работу СУБД при изменениях в базе данных.

Наиболее перспективным является использование многосписочных структур. Вариант представления, изображенный на рисунке 5 (использующий цепочки указателей), является простым примером многосписочной организации.

Рисунок 5 - Простой пример многосписочной организации (использование цепочек указателей)

Здесь каждый экземпляр хранимой записи файла студентов или файла факультетов содержит только один указатель. Каждая запись файла факультетов указывает на запись первого студента на этом факультете. Эта запись студента указывает на запись второго студента того же самого факультета, которая в свою очередь указывает на запись третьего и т.д. до записи последнего, которая содержит указатель на запись факультета. Таким образом, для каждой записи факультета у нас есть цепочка записей всех студентов на этом факультете. Достоинство этого варианта представления состоит в простоте внесения изменений. Недостатком является то, что для данного факультета единственным способом доступа к n-му студенту является последовательное прохождение по цепочке от первого ко второму и т.д. до (n-1)-го студента. Если каждая операция доступа включает операцию поиска, то время доступа к n-му студенту может стать достаточно большим.

Решением данной проблемы является использование двунаправленных цепочек, где каждый экземпляр хранимых записей содержит строго два указателя. Один указывает на предыдущий экземпляр записей, другой - на следующий. Также, с помощью дополнительных указателей, можно организовать список студентов, имеющих одинаковое значение поля Средняя успеваемость. На рисунке 6 изображён вариант пример многосписочной организации с использованием вышеописанных улучшений.

Рисунок 6 - Пример улучшенной многосписочной организации (использование двунаправленных цепочек указателей)

Вопрос 2. Алгоритмы хеширования: преобразование основания системы счисления

Процедура преобразования ключа в адрес (алгоритм хэширования) обычно выполняется в три этапа.

1. Если ключ не цифровой, он преобразуется в соответствующее цифровое представление таким образом, чтобы, исключить потерю информации, содержащейся в ключе. Например, буквенные знаки должны переводиться в цифровой код; допускается также представление символьного ключа в виде строки битов.

2. Ключи (в цифровом или битовом представлении) преобразуются в совокупность произвольно распределённых чисел, значения которых имеют тот же порядок, что и значения адресов основной области памяти. Желательно, чтобы набор ключей был распределён как можно равномернее в диапазоне, переводимом в допустимые адреса.

3. Полученные числа умножаются на константу, что позволяет разместить их строго в диапазоне значений адресов основной области. Например, пусть в результате выполнения этапа 2 мы получаем трёхзначные числа, а в основной области имеется 400 пакетов. Тогда трёхзначные числа следует умножать на 0.4, что позволит распределить получаемые адреса в интервале от 000 до 399. Этот относительный номер участка преобразуется в машинный адрес участка.

Рассмотрим такой алгоритм хеширования, как преобразование основания системы счисления.

У нас есть ключ, равный 3417. Переводим в двенадцатиричную систему счисления:

Младшие разряды: 79

Выравнивание адреса: 79*0.4 = 31

Вопрос 3.Факторы эффективности хеширования

хеширование поле метод алгоритм

На эффективность метода хеширования влияют следующие факторы.

Размер участка записей.

Определённое число областей адресуемого пространства памяти, которое может быть доступно за одно обращение к внешнему запоминающему устройству, называется первичным участком записей. Такой участок может содержать одну или несколько записей. Выбирая размер участка, и зная длину записи, можно определить число записей, помещающихся на одном участке.

Предположим, что в рулетке находится 100 шариков, которые будут направлены колесом рулетки в гнёзда. (Шарики в данном случае эквивалентны записям, а гнёзда - первичным участкам записи.)Допустим также, что можно изменять объём гнезда (т.е. можно изменять число шариков, которое помещается в каждое гнездо).

Тогда, задав объём гнезда (размер участка), установим следующий порядок игры в рулетку: если шарик направлен в какое-нибудь гнездо, а оно уже заполнено до отказа, то этот шарик направляется в область переполнения. Если в рулетке находится 100 шариков и имеется 100 гнезд, т.е. объем каждого гнезда равен 1, то шарики часто будут попадать в область переполнения. Если число гнёзд равно 10 и объём каждого гнезда также равен 10, то в область переполнения будет попадать значительно меньшее число шариков, чем в первом случае. Можно построить график, отражающий зависимость числа шариков (в процентном отношении к общему числу), попадающих в среднем в область переполнения, от объёма гнезда.

Рисунок 7

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

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

Плотность заполнения, т.е. число участков записей определенного размера, используемых для размещения файла заданного объёма.

Число записей, направляемых в область переполнения, зависит от плотности заполнения первичных участков памяти: чем выше плотность заполнения первичных участков, тем выше вероятность того, что вновь поступающие записи будут направлены в область переполнения.

Можно изменять время доступа и объём памяти, затрачиваемый на хранение файла, задавая то или иное значение плотности заполнения основной области. Сделав допущение о том, что алгоритм преобразования ключа в адрес направляет записи в участки случайным образом, можно найти зависимость числа записей, попадающих в область переполнения, от плотности заполнения основной области.

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

Организация работы с областями переполнения.

Существуют два подхода к организации хранения записей, направляемых в область переполнения.

При первом подходе записи располагаются в области переполнения, отделенной от основной области. Зависимости, приведенные на рис. 5.4, справедливы лишь в том случае, если записи хранятся в отдельной области переполнения.

Второй подход заключается в хранении записей переполнения в пределах основной области.

Отдельная область переполнения может быть организована для каждого участка основной области, или записи могут быть объединены в ней независимо от того, из какого участка основной области они были направлены. Ниже описаны различные методы работы с областями переполнения.

Цепочки участков переполнения.

Для связи основой области памяти с областью переполнения используются цепочки адресов. Т.е. пакет в основной области хранит адреспакета (записи) в области переполнения.

Метод распределенной области переполнения.

Пакеты переполнения размещены через определенные интервалы среди первичных пакетов. Если первичный пакет переполнен, направленная в него запись направляется в ближайший пакет переполнения, следующий за данным первичным пакетом. Достоинства -- пакеты переполнения располагаются в непосредственной близости к первичным пакетам -- отпадает необходимость в частом перемещении головок чтения-записи дискового устройства. Алгоритмы перемешивания (хеширования) осуществляют преобразование ключа к номеру первичного пакета. Однако алгоритм, преобразующий номер первичного пакета в его машинный адрес, должен учитывать наличие пакетов переполнения между первичными пакетами.

Если каждый 10-й пакет -- пакет переполнения, то адрес текущего N-го пакета записей будет определяться по формуле:

Адрес пакета = B0 + B(N+[N/9]) , где

B0 -- адрес первого байта;

B -- размер пакета в байтах;

N -- номер пакета, полученный на выходе алгоритма хеширования.

Метод открытой адресации (Петерсона).

Происходит рассеивание записей переполнения в основной области.

Если пакет переполнен, то запись помещается в следующий за ним пакет.

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

Справочник свободных пакетов.

Организуется специальный справочник, который содержит сведения о том, какие пакеты еще не заполнены. Если первичный пакет заполнен, то с помощью справочника определяется свободный пакет и после занесения в него записи в первичный пакет заносится ссылка на него. Необходимость в справочнике возрастает в случае частой модификации файлов. В качестве справочника может использоваться простой список заполнения пакетов. Метод эффективен, если размер пакета более 20 записей. Оптимизация предполагает загрузку файла, когда в основной области помещаются наиболее часто используемые записи.

Размещено на Allbest.ru