Файл: Систем управления.pdf

называют обменом данными между внешней и оперативной памятью. Такой обмен называется чтением блока, а в обратном направлении – записью блока.
При чтении блока, последний помещается в оперативной памяти в специально отведенный
(буферный) участок памяти. Может отводиться участок под несколько буферов (буферный пул). Чем больше буферный пул, тем эффективнее обработка данных. При считывании другого блока из внешней памяти в тот же самый буфер предыдущее содержимое буфера теряется. При внесении изменений в блок вначале блок считывается в буфер, затем выполняются изменения и далее блок записываются во внешнюю память.
Для организации каждого файла в зависимости от его размера во внешней памяти ему выделяется от одного до п блоков, где размещаются записи файла. Предположим, что в одном блоке размещаются записи только одного файла. В зависимости от соотношения объемов записей и блоков может оказаться, что в одном блоке размещается либо одна, либо несколько записей файла, либо одна запись размещается в нескольких блоках. Обычно запись занимает несколько десятков байт.
Каждый байт в блоке пронумерован: О, 1, 2, ..., х. Номер байта блока, с которого начинается запись, определяет относительный адрес записи файла в блоке.
В качестве адресов записей файла во внешней памяти используют: машинный адрес, относительный
адрес, ключ записи [17].
В качестве относительного адреса записи файла используют ее номер по порядку (внутрисистемный номер) в файле либо комбинацию таких составляющих адреса, как номер блока и относительный адрес в блоке, либо номер блока и значение ключа. В последнем случае, после считывания блока в буфер оперативной памяти, доступ к записи в буфере осуществляется в помощью какого-либо метода поиска
записей в файле по значению ключа.
При чтении записи из блока, который уже находится в буфере, обмен с внешней памятью не выполняется. Во многих системах при вводе записи ей присваивается уникальный системный идентификатор – ключ базы данных.
Запись обычно состоит из:
1) служебных полей, в которых хранятся указатели, реализующие связи с другими записями, и другая информация, необходимая для организации управления файлом,
2) полей хранимых данных.
Записи могут быть фиксированной и переменной длины. Записи размещаются в блоках плотно, без промежутков, последовательно одна за другой. В блоке часть памяти отводится также для служебной информации о блоке: относительные адреса свободных участков памяти, указатели на следующий блок и т.д.
Если файл базы данных состоит из записей фиксированной длины, то в одном блоке может разместиться k записей:
где


– обозначает целую часть числа; V
бл.
и V
з.
– соответственно объем блока и записи в байтах.
Однако обычно блоки заполняются не полностью, например, наполовину. Оставшаяся область блока остается некоторое время при работе системы незаполненной (зарезервированной). В дальнейшем эта область заполняется при расширении (увеличении) записей, хранящихся в блоке, или при поступлении в систему новых записей, которые в соответствии со значениями их ключей или по другим условиям необходимо поместить в одном блоке с уже хранящимися записями. По истечении некоторого времени блок заполняют полностью.
Для хранения поступающих данных, которые должны были бы попасть в этот блок, выделяется дополнительный блок памяти в области переполнения. Записи, которые должны были размещаться в одном блоке, связываются специальными указателями в одну цепь.
Процесс выделения дополнительных блоков в области переполнения можно было бы не ограничивать, если бы при этом не снижалась эффективность (по временному критерию) обработки хранимых данных. Снижение эффективности обработки данных связано с тем, что система непроизводительно затрачивает время на поиск записей в области переполнения, что сказывается на увеличении общего времени поиска требуемых записей (по сравнению со случаем, когда область переполнения еще не была использована и все записи были размещены в основной области).
Поэтому периодически файл реорганизуется: при необходимости файлу добавляется требуемой
76

количество блоков в основной области памяти и выполняется требуемая перекомпоновка записей. При этом исходят из расчета, чтобы можно было освободить область переполнения, а все записи разместить в блоках основной области, причем, в каждом блоке разместить записи последовательно и в таком количестве, чтобы r-я часть блока осталась незаполненной. В этом случае требуемое количество блоков где r < 1 – незаполненная часть блока; N
з.
– количество записей в файле.
Считается, что все блоки каждого файла пронумерованы: 1, 2, ..., β, ..., N и система определяет требуемый блок по имени файла и номеру блока. Если файл состоит из записей фиксированной длины, записи организованы последовательно и имеют внутри файла системный номер, то по этому номеру вычисляют номер блока, в котором находится запись:
Среднее время выполнения операций обмена зависит от типа устройства внешней памяти (от его характеристик) и от размера блока:
где t
o
– среднее время выполнения операции обмена; t
p
– время считывания, приведенное к одному байту (т.е. время считывания одного байта); t
подг.
– время подготовки устройства к выполнению операции обмена.
Время поиска данных в файле где t
п
– время выполнения операции поиска; t
с
– среднее время выполнения в процессоре одной операции сравнения; Х
о
– количество операций обмена; Х
с
– количество операций сравнения.
Если t
c
<< t
o
, то время поиска в основном определяется временем, затрачиваемым на обмен с внешней памятью. Поэтому при составлении алгоритмов поиска данных в файле стремятся к сокращению количества операций обмена.
На скорость поиска данных в файле наибольшее влияние оказывают следующие характеристики файла и технических устройств внешней памяти, использованных для его организации [17]:

объем блока;

объем байта;

количество записей в блоке файла п
з.бл.
;

количество записей в блоке индекса;

количество блоков в файле данных n
бл.ф.
;

доля резервируемой части блока r (при начальной организации данных в файле);

длина поля, отведенного для указателя;

количество записей в файле п
з.ф.
;

число полей в записи n
п.з.
;

размер записи V
з.
;

длина ключевого поля в записи;

число записей файла, удовлетворяющих условию поиска Q;

среднее число блоков переполнения на один блок файла;

среднее время обмена t
o
На рис. 3.7 изображен файл со следующими характеристиками: n
з.ф.
= 10; n
з.бл.
= 4; r = 0,5. Записи файла описываются схемой: F(А
1
, А
2
, А
3
, А
4
), т.е. n
п.з.
= 4. При начальной загрузке при таких характеристиках для организации файла требуется 5 блоков.
77

3.3. Методы поиска и индексирования данных
При рассмотрении последующего учебного материала используются модели, приведенные в разд.3.1,
3.2.
3.3.1. Последовательный поиск
Последовательный поиск заключается в последовательной проверке всех записей файла на их соответствие условию поиска Q [17]. Записи, значения полей которых удовлетворяют условию Q,
выдаются в качестве результата поиска.
Рис. 3.7. Пример организации файла при начальной загрузке
Поиск по равенству К = а, где К – значение ключевого поля. Алгоритм поиска заключается в последовательном просмотре записей файла и проверке условия К = а. Если запись найдена, то алгоритм заканчивает свою работу (удачный поиск). В противном случае поиск заканчивается просмотром последней записи файла (неудачный поиск).
Если ключ К сравной вероятностью может принимать любое из заданных значений, то в среднем для выполнения поиска требуется время
Поиск по интервалу значений ключа а ≤ К ≤ b. Алгоритм поиска заключается в последовательном просмотре всех записей файла, так как зарание неизвестно, какие записи удовлетворяют условию Q, а какие не удовлетворяют.
Требуемое время на поиск
Поиск по множеству значений K = a
i
, i = 1, 2, ..., п, где a
i
принимает значения из множества {а
1
, а
2
, ...,
а
i
, ..., а
п
}.Алгоритм поиска заключается в последовательном просмотре всех записей файла, при чем для каждой записи осуществляется п проверок по равенству: К = а
i
, где i = 1, 2, ..., п.
Основным достоинством последовательного поиска данных при последовательной организации файла является простота его реализации.
3.3.2. Бинарный поиск
78

Записи в файле можно упорядочить, например, по возрастанию или убыванию значения первичного ключа соответственно:
В этом случае можно построить более эффективные алгоритмы поиска, поскольку после сравнения значения а (условие поиска Q: К = а) со значением ключа i-й записи файла ясно, в какой части файла продолжать поиск [17].
Методы поиска записей в упорядоченном файле различаются друг от друга стратегией выбора очередной записи из фала для выполнения операции сравнения ключа в соответствии с заданным условием Q. Метод бинарного поиска основан на делении интервала поиска пополам.
Поиск по равенству К = а. Алгоритм поиска заключается в следующем. Файл считают упорядоченным по возрастанию ключа. Сравнивают значения ключа средней записи K
i
, где i =

n
з.ф.
/2
 со значением а. Если К = а то поиск удачный и алгоритм заканчивает свою работу. Если К
i
< а, то для продолжения поиска выбирается средняя запись правой половины файла: з
i
, ..., з
j
, ..., з
пз.
, где
Если К
i
> а, то для продолжения поиска выбирается средняя запись левой половины файла: з
1
, з
2
, ...,
з
j
, ..., з
i
, где
Процесс деления интервала пополам продолжается до тех пор, пока не будет найдена искомая запись
(К
i
= а), либо пока в интервале не останется всего одна запись. Если значение ее ключа не удовлетворяет условию поиска, то поиск неудачный и искомой записи в файле нет.
Бинарный поиск можно выполнять, работая с блоками файла, а не с записями. При считывании блока в оперативную память поиск записи в блоке может быть последовательным. В этом случае в качестве характеристик блока используются граничные значения ключей записей, находящихся в блоке.
Поиск по интервалу значений а ≤ К ≤ b. Алгоритм поиска следующий. Вначале выполняется бинарный поиск записи, значение ключа которой удовлетворяет условию К
i
= а, либо, если такой записи нет в файле, то значение ключа которой является наиболее близким к а по условию а ≤ К
i
. Далее последовательно читаются записи в блоках файла до тех пор, пока не будет нарушено условие: К
i
≤ b.
3.3.3. Индекс - «бинарное дерево»
Любой бинарный алгоритм поиска в упорядоченном файле БД можно представить с помощью соответствующего бинарного дерева [17]. Это бинарное дерево можно реализовать в виде самостоятельного файла (или индекса). При этом операции поиска будут освобождены от необходимости каждый раз вычислять адреса записей (они будут сформированы один раз при начальной загрузке файла БД и при последующих добавлениях в файл новых записей).
На рис. 3.8 представлено бинарное дерево, построенное для файла из 15 записей [17]. Запись бинарного дерева состоит из поля ключа записи и двух полей указателей. Один указатель для левого поддерева, другой – для правого поддерева. Листовые записи бинарного дерева содержат указатели на блоки файла основных записей (файла данных). Для уменьшения количества операций обмена с внешней памятью при выполнении поиска соседние записи в бинарном дереве объединяются в блоки.
На слайде объединяемые в один блок записи бинарного дерева очерчены штриховой линией.
Записи бинарного дерева обычно меньше по объему памяти записей основного файла V
з.б.д.
< V
з.
, так как содержат только одно поле данных (поле ключа) и два служебных поля для хранения индексов, то при одинаковых размерах блоков количество записей в блоке бинарного дерева больше, чем в блоке основного файла. Это позволяет еще больше сократить количество обращений к внешней памяти.
79

Рис. 3.8. Пример бинарного дерева
Реализация бинарного дерева позволяет сократить время поиска данных по сравнению с бинарным поиском, однако возрастает требуемый объем внешней памяти [17].
3.3.4. Неплотный индекс
Пусть основной файл F упорядочен по полю ключа К. Построим дополнительный файл FD (рис. 3.9) по правилу [17]:
1) записи файла FD имеют формат FD(K, Р), где К – поле,принимающее значение ключа первой записи блока основного файла F; Р – указатель на этот блок;
2) записи файла FD упорядочены по полю К.
Рис. 3.9. Пример неплотного индекса
Полученный файл FD называется неплотным индексом. Количество записей файла FD равно количеству блоков основного файла F. Для организации файла FD требуется дополнительная внешняя
80

память.
Рис. 3.10. Пример структуры типа В-дерево
Поиск вначале выполняется в индексе для нахождения адреса блока основного файла, а за тем этот блок считывает в оперативную память и в нем, например, с помощью последовательного поиска, определяется требуемая запись.
В-дерево. Так как неплотный индекс упорядочен по ключевому полю, то над ним можно построить еще один неплотный индекс (неплотный индекс неплотного индекса) и т.д., пока на самом последнем, верхнем уровне не останется всего один блок (рис. 3.10).
Полученная структура называется В-деревом порядка т, где т – количество записей в блоке индекса.
Такое дерево должно иметь в каждом узле не менее т / 2зависимых узлов и все листья должны располагаться на одном уровне.
Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа. Поиск в В-дереве выполняется так же, как и в неплотном индексе.
Удачный и неудачный поиск записи в В-дереве требует h обменов, где h – число уровней В-дерева.
При поиске по интервалу значений а ≤ К ≤ b вначале выполняется поиск по К = а в В-дереве, а затем
– последовательный поиск по условию К ≤ b в блоках 1-го уровня В-дерева.
3.3.5. Плотный индекс
Пусть по каким-либо причинам невозможно упорядочить основной файл F по ключу К. Построим дополнительный файл FD по правилу [17]:
1) записи файла FD имеют формат FD(K, Р), где К – поле, принимающее значение ключа записи основного файла F; Р – указатель на эту запись;
2) записи файла FD упорядочены по полю К.
Полученный файл называется плотным индексом. Он строится почти так же, как и неплотный индекс. Различие заключается в том, что для каждого значения ключа К в файле FD имеется отдельная запись, а в неполном индексе - только для значения ключа первой записи блока.
Пример плотного индекса представлен на рис. 3.11. Над плотным индексом можно также построить
В-дерево.
81

Рис. 3.11. Пример плотного индекса
3.3.6. Инвертированный файл
В рассмотренных выше способах индексирования данных расчет делался на поиск по значению ключевого поля. Но часто требуется осуществить выборку данных по значениям неключевых полей. В этом случае неключевые поля также должны быть проиндексированы (т.е. для каждого из них строится особый индекс). Индексы, построенные для неключевых полей используются при организации многоаспектного поиска. Широко распространены на практике методы многоаспектного поиска по
инвертированным файлам. Пусть имеется основной файл F, упорядоченный либо неупорядоченный по значениям вторичного ключа К
i
. Строится дополнительный файл FD
i
по правилу [17]:
1) записи файла FD
i
имеют формат FD
i
(K
i
, P) где K
i
– поле, принимающее значение вторичного ключа К
i
записи основного файла; Р – указатели на записи основного файла F, имеющие данное значение вторичного ключа К
i
;
2) записи файла FD
i
упорядочены по полю K
i
.
Построенный дополнительный файл FD. Называется инвертированным. В этом случае об основном файле F говорят, что он инвертирован по полю К
i
. Количество записей в инвертированном файле FD
i
определяется количеством значений вторичного ключа К
i
в записях основного файла F. Пример инвертированного файла по полю К
2
для основного файла F приведен на рис. 3.12. Рассмотренный способ организации инвертированного файла предполагает использование записей переменной длины.
Инвертированный файл можно организовать и с помощью записей фиксированной длины, если в каждой записи инвертированного файла выделять фиксированное число полей для указателей Р. Если фиксированного числа поле для некоторых записей окажется недостаточно, то организуется еще дополнительный служебный файл для хранения неуместившихся цепочек указателей.
82

Рис. 3.12. Пример инвертированного файла
Поскольку записи инвертированного файла упорядочены по значению ключа K
i
, то для поиска записей можно использовать любой из рассмотренных выше методов поиска в упорядоченном файле
(например, бинарный поиск или В-дерево). Чтобы выполнить многоаспектный поиск по n ключам, необходимо построить п инвертированных файлов [17].