База-данных «ИС Аэропорт»

1.6. Индексные файлы.

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

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

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

1.6.1. Файлы с плотным индексом, или индексно-прямые файлы.

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

Значение ключа

Номер записи

Здесь значение ключа — это значение первичного ключа, а номер записи – это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.

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

где N – число элементов.

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

В соответствии с формулой число обращений к диску при поиске записи определится следующим образом:

где – число индексных блоков, в которых размещаются все записи.

Учитывая что после поиска записи в индексном блоке нужно еще раз обратиться к основной области, в формуле, добавилась единица (+1).

В табл. 1 представлена схема организации такого файла на дисковом пространстве (фоном выделены свободные зоны).

Таблица 1
Схема организации файла с плотным индексом
Блок	Ключи	Ссылки на № записи	Свободная зона	Области
Блок 1	01-10/01	3		Индексная область
	02-20/02	4
	03-20/00	5
Блок 2	06-40/00	7
	07-50/01	8
	08-30/01	9
Блок 3	10-44/01	1
	11-44/02	2
	09-35/01	6
Блок 4	17-20/03
	18-40/02
	20-35/02
Номер записи	Ключ	Содержание		Основная область
1	10-44/01	Математика
2	11-44/02	Физика
3	01-10/01	Информатика
4	02-20/02	Теория информации
5	03-20/00	Базы данных
6	09-35/01	Интерфейс АСОиУ
7	06-40/00	Защита информации
8	07-50/01	АСТПП и САПР
9	08-30/01	Языки программирования
10	17-20/03	Операционные системы
11	18-40/02	Цифровые сети интегрального обслуживания
12	20-35/02	Технологии программирования

 

Из табл. 1 видно, что файл организован в виде двух областей — основной и индексной. В основной области хранятся значения ключевых полей, номера и содержание записей. В индексной области хранятся значения ключевых полей и ссылки на номер записи в основной области.

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

Такой прием организации индексной области позволяет без нарушения системы вводить новые типы изделий и присваивать им соответствующие буквенно-цифровые коды.

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

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

Тn = log2 Nинд. обл. + 1 + 1 + 1.

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

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

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

1.6.2. Файлы с неплотным индексом, или индексно-последовательные файлы

Структура записей данных в таких файлах имеет вид, представленный на рис. 4.

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

• определяется номер блока основной области, в который необходимо поместить новую запись;
• найденный блок считывается в оперативную память;
• в оперативной памяти производится корректировка блока;
• откорректированный блок записывается на диск на прежнее место.

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

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

1.6.3. Организация индексов в виде В-дерева — многоуровневой иерархической структуры

Данное направление совершенствования организации файловой структуры связано с преобразованием индексной области файлов с неплотным индексом, который изначально предполагает описание этой области как одного упорядоченного списка, в вид иерархического симметрического поискового дерева. В таких деревьях число узлов на каждом уровне одинаково. Теоретические основы организации машинной памяти при построении таких иерархических систем были изложены в 1967 г. автором языка ассоциативного программирования АЛГЭМ, преподавателем Московского энергетического института А. И. Китовым.

Однако в современной литературе по теории баз данных иерархическую поисковую структуру принято называть B-деревом (читается: «Б-деревом») (от англ. B-tree – сбалансированное дерево).

На рис. 5 показан пример организации файловой структуры в виде В-дерева.

1.7. Способы организации памяти для хранения данных

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

• иерархическая организации памяти;
• организация кэш-памяти;
• организация основной памяти;
• виртуальная память – как средство организации защиты данных.

1.7.1. Иерархическая организация памяти

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

Успешное или неуспешное обращение к более высокому уровню называются соответственно попаданием (hit) или промахом (miss). Попадание есть обращение к объекту в памяти, который найден на более высоком уровне, в то время как промах означает, что он не найден на этом уровне. Доля попаданий (hit rate), или коэффициент попаданий (hit ratio), есть доля обращений, найденных на более высоком уровне. Иногда она выражается в процентах. Доля промахов (miss rate) есть доля обращений, которые не найдены на более высоком уровне.

Чтобы описать некоторый уровень иерархии памяти, надо ответить на четыре вопроса.

1.7.2. Организация кэш-памяти

Концепция кэш-памяти возникла раньше, чем архитектура IBM/360. Сегодня кэш-память имеется практически в любом классе компьютеров, а в некоторых компьютерах – во множественном числе.

Рассмотрим организацию кэш-памяти более детально, отвечая на поставленные выше вопросы об иерархии памяти.

Где может размещаться блок в кэш-памяти? Принципы размещения блоков в кэш-памяти определяют три основных типа их организации:

• если каждый блок основной памяти имеет только одно фиксированное место, на котором он может появиться в кэш-памяти, то такая кэш-память называется кэшем с прямым отображением (direct mapped). Это наиболее простая организация кэш-памяти, при которой для отображения адресов блоков основной памяти на адреса кэш-памяти просто используются младшие разряды адреса блока. Таким образом, все блоки основной памяти, имеющие одинаковые младшие разряды в своем адресе, попадают в один блок кэш-памяти, т.е. (адрес блока кэш-памяти) = (адрес блока основной памяти)×mod (число блоков в кэш-памяти);
• если некоторый блок основной памяти может располагаться на любом месте кэш-памяти, то кэш называется полностью ассоциативным (fully associative);
• если некоторый блок основной памяти может располагаться на ограниченном множестве мест в кэш-памяти, то кэш называется множественно-ассоциативным (set associative).

Блок может размещаться на любом месте данного множества.

Как найти блок, находящийся в кэш-памяти? У каждого блока в кэш-памяти имеется адресный тег, указывающий, какой блок в основной памяти данный блок кэш-памяти представляет. Эти теги обычно одновременно сравниваются с выработанным процессором адресом блока памяти. Кроме того, необходим способ определения того, что блок кэш-памяти содержит достоверную или пригодную для использования информацию.

Какой блок кэш-памяти должен быть замещен при промахе? При возникновении промаха контроллер кэш-памяти должен выбрать подлежащий замещению блок. Как правило, для замещения блоков применяются две основные стратегии: случайная и Least-Recently Used (LRU). В первом случае, чтобы иметь равномерное распределение, блоки-кандидаты выбираются случайно. В некоторых системах, чтобы получить воспроизводимое поведение, которое особенно полезно но время отладки аппаратуры, используют псевдослучайный алгоритм замещения.