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

Министерство образования и науки РФ

Новосибирский государственный университет экономики и управления

Кафедра экономической информатики

Учебная дисциплина: Базы данных

Тема контрольной (курсовой) работы: Использование Индексов в базе данных

Наименование специальности: Прикладная информатика (в экономике)

Выполнил: Остапенко М.В.

Проверил: Зав каф. ЭИ Пашков П.М.

Содержание

• Введение
• Индексирование в БД
• Индекс. Создание индекса
• Типы и виды индексов
• Индексация
• Структура индекса
• Индексы для последовательных файлов
• Методы доступа к файлам
• Неупорядоченные файлы
• Упорядоченные файлы
• Хеширование. Типы хеширования
• Связанная область переполнения
• Многократное хеширование
• Древовидные структуры
• В-деревья
• Структура В-дерева
• Бинарное дерево
• Древовидные структуры для многомерных данных
• Деревья квадрантов
• R-деревья
• Заключение
• Список используемой литературы
• Приложения

Введение

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

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

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

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

Индексирование в БД

База данных - это единое, вместительное хранилище разнообразных данных и описаний их структур. Хранимые данные организованы в совместно используемый набор и логически связаны между собой. [1, с.13] Если данных много, то найти нужную запись бывает очень трудно. Поиск данных производится методом перебора, то есть просматриваются все записи таблицы от первой записи до последней записи, что приводит к большим затратам времени, чтобы облегчить поиск данных в таблице, используют индексы. [2, с.47]

Индекс. Создание индекса

Индекс - структура данных определенного вида, которая предназначена для ускорения поиска записей файла данных.

В простейшем варианте, индекс представляет собой файл, записи которого содержат ключ (поле, содержащее одно или несколько атрибутов записи файла данных и предназначенное для осуществления поиска записей по этому критерию) и указатель (поле, содержащее адрес записи в файле данных). Поле адреса заполняется СУБД. Записи индекса упорядочиваются по ключевому полю. Файл данных, для которого существует индекс, называется индексированным, а поле индексированного файла, значения которого используется в индексе, называется индексным полем. Индекс можно создать как по одному полю, так и по нескольким полям, причем не обязательно относящимся к первичному ключу. [3, c.110] На рис.1 [3, c.110] изображена структура простого индекса.

Рис. 1. Структура простого индекса

Далее мы рассмотрим, как и какими способами можно создать индекс. Создать индекс можно двумя способами:

1) С помощью команды:

INDEX ON < индексное выражение > ТО < idx-файл>| TAG < имя тега>

[OF <cdx-файл>]

[FOR <условие>]

[COMPACT]

[DESCENDING]

[UNIQUE]

[ADDITIVE]

[NOOPTIMIZE]

Назначение опций:

<индексное выражение> - имя поля (или полей), по значениям которого надо построить индекс. При построении сложного индекса имена полей перечисляются через знак + (плюс). Если сложный индекс построен по:

• числовым полям, то индекс строится по сумме значений полей;

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

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

Длина индексного выражения не должна превышать 254 символа.

ТО <idx-файл> - указывается имя одноиндексного файла.

TAG <имя тега> [OF <cdx-файл>] - указывается имя тега в мультииндексном файле. Если используется опция [OF], то создаваемый тег помешается в указанный мультииндексный файл, а если требуемый мультииндексный файл отсутствует, то будет построен структурный мультииндексный файл. Если опция [OF <cdx-файл>] опущена, то созданный тег будет помещен в текущий мультииндексный файл.

FOR <условие> - устанавливает режим отбора в индекс тех записей таблицы, которые удовлетворяют <условию>.

COMPACT - управляет созданием компактного одноиндексного файла. В старших версиях FoxPro не используется.

DESCENDING - строит индекс по убыванию. По умолчанию используется построение индекса по возрастанию (ASCENDING). Для одноиндексных файлов можно построить индекс только по возрастанию. Если перед использованием команды INDEX ON. подать команду SET COLLATE, то можно построить одноиндексный файл по убыванию.

UNIQUE - строит уникальный индекс. Если индексное поле (поля) содержит повторяющиеся значения, то в индекс попадает только одна первая запись и остальные записи будут не доступны.

ADDITTVE - вновь создаваемый индексный файл не закрывает уже открытые к этому моменту времени индексные файлы. Если опция опушена, то вновь создаваемый индексный файл закрывает все ранее открытые индексные файлы.

NOOPTIMIZE - отключает использование технологии Rashmore для ускоренного доступа к данным. [2, c.48]

1) С помощью Главного меню

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

Чтобы создать индекс, щелкните правой кнопкой мыши на таблице, содержащей столбец, который вы хотите индексировать, выберите All Tasks (Все задачи), затем выберите Manage Indexes (Управление индексами). Откроется диалоговое окно, изображенное в левой части рис.2. Щелкните на кнопке New. (Новый.), и перед вами появится диалоговое окно, изображенное в правой части рис.2. На этом рисунке разработчик создает индекс по столбцу Zip таблицы CUSTOMER. Индекс, который называется CUSTOMER_Zip_Index, должен быть заполнен на 80% и отнесен к группе файлов PRIMARY. Перегрузка оставляет пространство в индексе открытым для вставок на всех уровнях, исключая самый нижний. Заполнение характеризует объем пустого пространства, оставляемого на нижнем уровне индекса.

Рис. 2. Создание индекса в графическом режиме [9]

В последнем диалоговом окне щелкните на кнопке Edit SQL. (Редактировать SQL.), и вы увидите диалоговое окно, изображенное на рис.3. Оно будет содержать текст SQL-оператора, введя который в окне анализатора запросов, можно было бы создать тот же самый индекс.

Рис. 3. SQL-код, создающий индекс [9]

SQL Server поддерживает два вида индексов: кластеризованные и некластеризованные. В кластеризованном индексе данные хранятся на нижнем уровне и в том же порядке, что и сам индекс. В некластеризованном индексе нижний уровень не содержит данных, но содержит указатели на данные. Поскольку строки могут быть отсортированы только в одном физическом порядке за один раз, для каждой таблицы допускается только один кластеризованный индекс. Кластеризованные индексы обеспечивают более быстрое получение данных, чем некластеризованные. Обычно они оказываются быстрее и при обновлении, но не в том случае, когда много обновлений происходит в одном и том же месте в середине отношения. За дальнейшей информацией обращайтесь к документации на SQL Server. [9 с.486]

Типы и виды индексов

Индексы можно классифицировать следующим образом:

1) по виду используемых полей записи данных:

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

Ш Candidat - это кандидат в первичный ключ или альтернативный ключ

Ш Unique (уникальный тип индекса) - это тип индекса, который допускает повторяющиеся значения в поле, по которому он построен, но на экран будет выводиться только одна первая запись из группы записей с одинаковым значением индексного поля

Ш Regular (регулярный тип индекса) - это тип индекса, который не накладывает никаких ограничений на значения индексного поля и на вывод записей, на экран

Ш Primary - это один из индексов, удовлетворяющий требованиям индекса типа Candidat может быть выбран в качестве первичного ключа; [2, с.47]

• вторичный индекс - индекс, построенный не по первичному ключу (см. рис.4) [6]. Позволяет ускорить операции выборки для запросов, выполняющих фильтрацию не по полям первичного ключа. Вторичных индексов может быть несколько (однако следует помнить, что чем больше индексов у файла данных, тем медленнее вставка в него данных - вторичные индексы должны строиться только для самых критичный и часто выполняемых запросов); значения ключей в индексе могут повторяться;

Рис. 4. Пример структуры с вторичным индексом

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

• обращенный (inverted) индекс - это индекс, который сочетает в себе все индексы и используется совместно с промежуточным уровнем групп - сегментов указателей; [6, с.635] На рисунке 5 [9] показан поиск документов с помощью обращенного индекса.

Рис. 5. Поиск документа с помощью обращенного индекса

2) по числу используемых полей записи данных, а также в зависимости от структуры и организации записи:

• несоставной - ключ индекса состоит только из одного поля записи;

• составной - ключ индекса состоит из нескольких полей записи, при этом сортировка ключа индекса выполняется в следующем виде: основной порядок сортировки задает первое поле ключа, дополнительный порядок сортировки (сортировка в группе) задает второе поле ключа, и т.п.; составной индекс по полям записи (f1,f2,f3,…,fn) может использоваться для поиска по полю f1 либо по комбинациям полей (f1, f2), (f1, f2, f3), (f1, f2, f3, f4), …, (f1,f2,f3,…,fn-1), (f1,f2,f3,…,fn) - т.е. один составной индекс может обслуживать ряд запросов, но поля, используемые при этом, должны располагаться с начала ключа индекса (т.к. они зададут порядок сортировки записей индекса) и без разрывов; [3, с.112]

• простой индекс - это индекс, построенный по значениям одного поля;

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

• интервальный индекс [interval index] - это индекс, значения которого определяются некоторой областью, например, диапазоном от 3 до 12;

3) по числу ссылок на данные:

• плотный - число индексных записей равно числу записей данных, одна индексная запись ссылается только на одну запись данных. На рисунке 6 [8] изображен пример плотного индекса;

Рис. 6. Пример плотного индекса

• неплотный - число индексных записей меньше числа записей данных, индекс указывает либо на первую запись в определенной группе, либо на страницу с определенной группой записей данных, записи данных при этом также должны быть упорядочены по некоторому полю. Например, если список сотрудников упорядочен по фамилии, то можно построить неплотный индекс, которых будет в качестве ключа содержать первую букву фамилии, и этот индекс будет ссылаться на записи данных следующим образом: "А" - > на первую фамилию в списке, начинающуюся на "А", "Б" - > на первую фамилию в списке, начинающуюся на "Б", и т.п. Поиск конкретного сотрудника по фамилии тогда можно осуществить следующим образом:

a) найти букву, на которую начинается фамилия сотрудника;

b) выполнить поиск фрагмента файла данных, отвечающего за размещение фамилий начинающихся на данную букву, с использованием неплотного индекса;

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

Рис. 7. Многоуровневый индекс [3, с.113]

4) по числу уровней индекса:

· одноуровневый - индекс, который непосредственно ссылается на данные, а не на другие индексные структуры;

· многоуровневый - индекс, состоящий из нескольких индексных файлов, при этом только индекс первого уровня ссылается на реальные данные (обычно это плотный индекс), а индексы более высоких уровней ссылаются на предыдущие уровни (эти индексы обязательно неплотные). Структура многоуровневого индекса за счет увеличения объема данных позволяет сократить время поиска записей, т.к. данные уже разбиты на фрагменты, которые бы получались, например, в результате бинарного поиска. Многоуровневый индекс вводится при наличии в файле данных большого числа записей, обычно при условии, что бинарный поиск в одноуровневом плотном индексе проводится за значительное число шагов. Поиск данных в многоуровневом индексе начинается с самого верхнего уровня и продолжается пока не будет достигнута запись данных, поиск ссылки на следующий уровень на текущем уровне проводится методом двоичного поиска в определенном диапазоне. На практике, число уровней многоуровневого индекса обычно не превышает трех; [3, с.114]

· в зависимости от характера используемой системы знаков:

· буквенный индекс [alphabetic code, alphabetic notation] - индекс, использующий отдельные буквы или сочетание букв алфавита;

· цифровой индекс [numerical code, numerical notation] - индекс, использующий отдельные цифры, числа, сочетания цифр или их комбинации;

· десятичный индекс [decimal code, decimal classification code] - цифровой индекс, составленный на основе десятичной системы счисления;

· алфавитно-цифровой индекс [alphanumeric code] - смешанный индекс, состоящий из букв и цифр;

· смешанный индекс [mixed code, mixed notation] - индекс, состоящий из разнородных знаков, например, из букв различных алфавитов, букв и цифр и т.п.

5) в зависимости от уровня приоритетности:

· гипериндекс [hyperindex] - высший уровень индекса индексной организации баз данных, принятый в некоторых СУБД (наряду с главным и нормальным индексами);

· главный (основной, первичный, старший) индекс [master index, primary index, main subject code, main classification number] - 1. Индекс высшего уровня в иерархической системе организации данных;

· 2. Индекс, отражающий главную тему содержания индексируемого текста, документа и т.п. и относящийся к основной принятой системе классификации;

· нормальный индекс [normal index] - подмножество ключей базы данных, соответствующих конкретному значению поля, объявленного дескриптором (признаком поиска). Используется в четырехуровневой системе индексов СУБД, например, - ADABAS;

· вспомогательный (дополнительный) индекс [additional index, auxiliary code, auxiliary classification number] - индекс, являющийся дополнением к главному (основному) и отражающий дополнительные признаки индексируемого текста, документа и т.п. или относящийся к вспомогательной системе классификации;

6) в зависимости от характера индексируемых объектов и/или назначения индекса различают:

· авторский знак [author mark, author notation, author number] - индекс, обозначающий автора произведения, используемый при расстановке и поиске книг в библиотеках;

· кеттерский знак [cutter number] - авторский знак, определяемый по "Авторской таблице" Ч. Кеттера;

· расстановочный индекс [location mark, location number] - индекс, используемый для расстановки и поиска книг, документов и т.п. в библиотеке или фонде;

· каталожный индекс [catalog classification mark, catalog classification number] - индекс, используемый для расстановки и поиска карточек в каталоге;

· индекс каталога [catalog index] - старший индекс в библиотечной организации данных;

· индекс массива [array index] - индекс, присваиваемый массиву документов или данных для его идентификации;

· индекс файла [index number] - в некоторых операционных системах (например, UNIX) номер индексного дескриптора файла и др. [7]

Преимущество всех перечисленных выше типов и видов индексов в том, что они значительно повышают производительность, и уменьшают скорость поиска.

Основной недостаток использования индексов - замедление обновления файла данных, т.к. при добавлении новой записи в файл данных требуется обновление индекса, а индекс представляет собой упорядоченный последовательный файл и обновляется медленно. [3]

Индексация

В указанных ниже определениях понятие "индексация" никоим образом не обозначает процесс и его нельзя смешивать с понятием "индексирование"!

ИНДЕКСАЦИЯ [subscripting, notation system, indexing] - 1. Метод, обеспечивающий возможность обращения к элементу массива с помощью указания массива и выражений, определяющих местоположение этого элемента в массиве;

2. Система (совокупность) индексов, используемая для индексирования и соответствующая определенной системе классификации.

Различаются следующие виды индексации:

· кумулятивная индексация [cumulative indexing] - индексация, предусматривающая присвоение одному адресу несколько индексов;

· однорядная индексация [pure notation system] - индексация, в которой использованы "однорядные" знаки: буквы одного алфавита, цифры одной системы счисления и т.п.:

· одноуровневая индексация - индексация с использованием одноуровневых индексов;

· многоуровневая индексация - индексация с использованием многоуровневых индексов;

· смешанная индексация [mixed notation system] - индексация, в которой использованы различные знаки: буквы, цифры и т.п.

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

Структура индекса

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

Структура индекса связана с определенным ключом поиска и содержит записи, состоящие из ключевого значения и адреса логической записи в файле, содержащей это ключевое значение. Файл, содержащий логические записи, называется файлом данных, а файл, содержащий индексные записи, - индексным файлом. Значения в индексном файле упорядочены по полю индексирования, которое обычно строится на базе одного атрибута. [8, c.1019]

Индексы для последовательных файлов

Одна из простейших индексных структур основывается на файле, отсортированном по значениям атрибутов индекса. Подобный файл называют последовательным (sequential file). Структура индекса для последовательного файла особенно полезна в тех случаях, когда ключ поиска совпадает с первичным ключом отношения. На рис. 8 [6] схематически изображено отношение, представленное в виде последовательного файла.

Кортежи отношения, хранимого в форме последовательного файла, отсортированы по значениям первичного ключа. Рисунок соответствует ситуации, когда ключами являются целочисленные значения; здесь показаны только ключевые поля и выдвинуто довольно нетипичное предположение о том, что каждый блок способен содержать только две записи. Например, в первом блоке размешены записи с ключами 10 и 20. Помимо того, в этом и многих других примерах в качестве ключевых значений используются последовательные целые числа, кратные 10, хотя, разумеется, на практике подобное требование не ставится - равно как и то, чтобы в индексе и файле данных присутствовали все значения, кратные 10, из определенного интервала.

На рис. 9 [6] изображены начальные блоки файла индекса для последовательного файла, приведенного на рис. 8 [6]. Для удобства мы полагаем, что значения ключей кратны 10, хотя на практике подобная закономерность встречается, конечно, весьма редко. Мы подразумеваем также, что блоки индексного файла содержат по четыре пары вида "ключ-указатель". Надо сказать, что и эта гипотеза далека от реальности - в типичном дисковом блоке могут уместиться сотни подобных пар.

Рис. 8. Пример последовательного файла

Рис. 9. Плотный индекс (слева) для последовательного файла данных (справа)

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

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

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

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

Размер файла индекса обычно существенно меньше объема файла данных.

Поскольку ключи хранятся в упорядоченном виде, для отыскания значения К уместно использовать алгоритм бинарного поиска. Если индекс содержит п блоков, системе придется обратиться только к log₂n из них.

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

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

Как показано на рис. 10 [6], разреженный индекс содержит только по одному указателю на каждый блок файла данных, а ключами индекса являются ключевые значения первых записей каждого блока данных.

Рис. 10. Разреженный индекс для последовательного файла

На рис. 11, [6] показан вариант разреженного индекса для файла данных. Этот индекс выглядит как обычно: он содержит пары "ключ-указатель", соответствующие значениям ключа поиска первых записей блоков данных.

Чтобы найти записи с заданным значением К ключа поиска в такой структуре, необходимо отыскать элемент индекса (назовем его Е₁) с наибольшим номером, обладающий значением ключа, меньшим или равным К. Затем надлежит перемещаться к началу индекса до тех пор, пока не будет достигнут первый элемент индекса либо элемент Е₂ со значением ключа, строго меньшим К (в частном случае, когда Е_х уже содержит значение ключа, строго меньшее К, Е₂ совпадает с Е₁). Блоки данных, способные содержать записи со значением К ключа поиска, адресуются элементами индекса с номерами из интервала от Е₂ до Е₁ включительно.

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

На рис. 12 [6] перечислены все действия, предпринимаемые в отношении файлов разреженных и плотных индексов при выполнении каждой из семи различных операций над файлами данных - создания/удаления пустых блоков переполнения или блоков последовательного файла, а также вставки, удаления и перемещения записей. Мы полагаем, что создаваться или изыматься могут только пустые блоки. В частности, если удалению подлежит блок, содержащий записи, прежде всего следует "избавиться" от записей этого блока - либо удалить их, либо перенести в другой блок.

Рис. 12. Как действия в отношении последовательного файла данных влияют на файл индекса

Рассмотрим операцию удаления записи из блока последовательного файла данных при наличии плотного индекса. Обратимся к структуре, изображенной на рис. 9 (см. с. 15), и предположим, что удалению подлежит запись с ключом 30. На рис. 13 [6] показан фрагмент той же структуры после выполнения операции удаления.

Рис. 13. Результат удаления записи с ключом 30 из структуры с плотным индексом

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

Далее из индекса изымается пара "ключ-указатель" со значением ключа 30. Внешние указатели на записи индекса наверняка отсутствуют и необходимости в использовании "обелиска" нет. Поэтому имеет смысл переместить оставшиеся записи в блоке индекса на одну позицию "вверх", чтобы консолидировать свободные участки внутри блока (если их несколько) в единую более крупную область.

Рис. 14. Результат удаления записи данных с ключом 30 из структуры с разреженным индексом, показанной на рис. 10

Результат удаления записи данных с ключом 30 схематически изображен на рис. 14 [6]. После удаления записи с ключом 30 следующая запись блока, обладающая ключом 40, смещена "вверх" с целью укрупнения свободной области внутри блока. Поскольку запись с ключом 40 теперь занимает первую позицию во втором блоке данных, необходимо обновить содержимое элемента ключа, ссылающегося на этот блок. На рис.14 показано, что значение ключа, которому отвечает указатель, адресующий второй блок данных, изменено с 30 на 40. [6]

Методы доступа к файлам

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

Существуют следующие основные типы организации файлов.

§ Неупорядоченная организация файла предусматривает произвольное неупорядоченное размещение записей на диске.

§ Упорядоченная (последовательная) организация предполагает размещение записей в соответствии со значением указанного поля.

§ В хешированием файле записи хранятся в соответствии со значением некоторой хеш-функции.

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

Метод доступа - действия, выполняемые при сохранении или извлечении записей из файла.

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

Неупорядоченные файлы

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

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

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

Упорядоченные файлы

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

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

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

Таким образом, вставка записи в начало большого файла может оказаться очень длительной процедурой. Для решения этой проблемы часто используется временный неотсортированный файл, который называется файлом переполнения (overflow file) или файлом транзакции (transaction file). При этом все операции вставки выполняются в файле переполнения, содержимое которого периодически объединяется с основным отсортированным файлом. Следовательно, операции вставки выполняются более эффективно, но выполнение операций извлечения данных немного замедляется. Если запись не найдена во время бинарного поиска в отсортированном файле, то приходится выполнять линейный поиск в файле переполнения. И наоборот, при удалении записи необходимо реорганизовать файл, чтобы удалить пустующие места.

Упорядоченные файлы редко используются для хранения информации баз данных, за исключением тех случаев, когда для файла организуется первичный индекс. [10]

Хеширование. Типы хеширования

В хешированном файле записи необязательно должны записываться в файл последовательно.

Вместо этого для вычисления адреса страницы, в которой должна находиться та или иная запись, используется хеш-функция (hash function), аргументами которой являются значения одного или нескольких полей этой записи. Подобное поле называется полем перемешивания (hash field), а если поле также является ключевым полем файла, то оно называется хеш-ключом (hash key). Записи в хешированном файле произвольным образом распределены по всему доступному для файла пространству. По этой причине хешированные файлы иногда называют файлами с произвольной структурой (random file) или файлами прямого доступа (direct file).

Хеш-функция выбирается таким образом, чтобы записи внутри файла были распределены максимально равномерно. Один из методов построения хеш-функции носит название свертка (folding) и основан на выполнении некоторых арифметических действий над различными частями поля перемешивания. При этом символьные строки преобразуются в целые числа с использованием некоторой кодировки - на основе расположения букв в алфавите или ASCIl-кодов символов. Например, можно преобразовать в целое число первых два символа поля номера сотрудника (атрибут Sno), а затем сложить полученное значение с остальной частью номера сотрудника. Вычисленная сумма используется в качестве адреса дисковой страницы, на которой будет храниться данная запись. Более популярный альтернативный метод основан на перемешивании на основе остатка от деления (division-remainder). В этом методе используется функция МОО, на вход которой передается значение поля. Функция делит полученное значение на некоторое предопределенное целое число, после чего остаток от деления использует в качестве адреса.

Проблема, связанная с использованием большинства хеш-функций, заключается в том, что они не могут гарантировать уникальность вычисляемого адреса, поскольку количество возможных значений поля перемешивания может быть гораздо больше количества доступных для записей адресов. Каждый вычисленный хеш-функцией адрес соответствует некоторой странице, или сегменту (bucket), с несколькими ячейками - слотами, - предназначенными для отдельных записей. В пределах одного сегмента записи размещаются в слотах в порядке поступления. Тот случай, когда один и тот же адрес генерируется для двух или более записей, называется конфликтом (collision), а подобные записи - синонимами. В этой ситуации новую запись необходимо вставить в другую позицию, поскольку место с вычисленным для нее хеш-адресом, уже занято. Разрешение конфликтов усложняет сопровождение хешированных файлов и снижает общую производительность их работы.

Для разрешения конфликтов можно использовать следующие методы:

открытую адресацию;

несвязанную область переполнения;

связанную область переполнения;

многократное хеширование.

Открытая адресация

При возникновении конфликта система выполняет линейный поиск первого доступного слота для вставки в него новой записи. После неудачного поиска пустого слота в последнем сегменте поиск продолжается с первого сегмента. При выборке записи используется тот же метод, который применялся при сохранении записи, за исключением того, что запись в данном случае рассматривается несуществующей, если до обнаружения искомой записи будет обнаружен пустой слот. Например, рассмотрим тривиальную хеш-функцию на основе остатка от деления по модулю 3 (МОD 3), как показано на рис.15 [8]. Каждый сегмент обладает двумя слотами, поэтому записи о сотрудниках 'SG5' и 'SG14' попадают в сегмент 2. При вставке записи 'SL41' хешфункция генерирует адрес, соответствующий сегменту 2. Но в сегменте 2 нет свободных слотов, поэтому следует найти первый свободный слот. Такой слот имеется лишь в сегменте 1, который и будет найден после продолжения линейного поиска с начала файла и безуспешного просмотра сегмента О.

Рис.15. Разрешение конфликта с помощью открытой адресации

Несвязанная область переполнения

Вместо поиска пустого слота для разрешения конфликтов можно использовать область переполнения, предназначенную для размещения записей, которые не могут быть вставлены по вычисленному для них адресу перемешивания. На рис.16 [8] показано, как в этом случае разрешается конфликтная ситуация, представленная на рис.15. В данном случае вместо поиска свободного слота для записи 'SL41' она сразу же помещается в область переполнения. На первый взгляд может показаться, что этот подход не дает большого выигрыша в производительности. Однако при более внимательном анализе обнаруживается. что при использовании открытой адресации конфликты, устраненные с помощью первого свободного слота, потенциально вызывают дополнительные конфликты с записями, которые будут иметь хеш-значение, равное адресу этого раньше свободного слота. Таким образом, количество конфликтов будет возрастать, а производительность - падать. С другой стороны, если количество конфликтов можно свести к минимуму, то линейный поиск в малой области переполнения будет выполняться достаточно быстро.

Рис. 16. Разрешение конфликта с помощью несвязанной области переполнения

Связанная область переполнения

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

Если указатель равен нулю, то никаких конфликтов нет. На рис.17 сегмент 2 указывает на сегмент переполнения 3, а указатели синонима сегментов 0 и 1 равны нулю, что означает, что в этих сегментах конфликтов нет.

Рис.17. Разрешение конфликта с помощью связанной области переполнения

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

Многократное хеширование

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

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

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

Различают статическое и динамическое хеширование.

Для статического хеширования, размер хеш-файла задается один раз при его создании и больше не изменяется (фиксируется пространство хеш-адресов).

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

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

вычисление адреса страницы с помощью хеш-функции и известного хеш-ключа;

извлечение данной страницы и последовательный поиск в ней заданной записи.

К недостаткам статических хеш-файлов относят следующие:

• физическая последовательность записей в файле почти всегда отличается от логической последовательности, последовательный перебор записей фактически не имеет смысла;

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

• возникновение коллизий - ситуаций, когда записи имеют одинаковые хеш-адреса и не вмешаются на адресуемую страницу.

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

Один из типов динамического хеширования называется расширяемое хеширование (см. рис.18). Основные принципы расширяемого хеширования:

1) В результате вычисления хеш-функции h для поля k записи r будет получен псевдоключ s. Псевдоключ используется не как адрес, а как косвенный указатель на место хранения записей.

2) Хеш-файл имеет каталог, имеющий глубину каталога d и содержащий 2^d указателей на страницы данных.

3) Если старшие d бит псевдоключа рассматривать как двоичное число b, то i-ый указатель в каталоге (1? i ?2^d) будет относиться к странице, на которой хранятся записи b=i-1

4) Каждая страница данных имеет заголовок с указанием локальной глубины (p < d) этой страницы (локальная глубина показывает, сколько указателей каталога могут на нее ссылаться - 2^d-p указателей). [3]

Рис. 18. Расширяемое хеширование

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

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

Древовидные структуры

Основной структурой, поддерживающей иерархическое представление информации, является дерево. Для моделирования информации с помощью древовидной структуры зачастую используется обобщенное дерево (general. tree), которое схематично изображено на рис. 19 [8]. На этом рисунке Показано абстрактное представление данной структуры, состоящей из узлов (nodes), соединенных связями, которые называются дугами (arcs) или ребрами (edge). Самый верхний узел называется корневым узлом (root node). Он может иметь нуль или несколько дочерних узлов (child nodes), которые, в свою очередь, также могут иметь нуль или несколько дочерних узлов. В результате подобная структура может быть определена рекурсивно. Все узлы дерева, за исключением корня, должны иметь родительский узел. Любая часть дерева, исходящая из одного узла (помимо корня дерева), называется поддеревом (subtree). С практической точки зрения, каждый узел может быть представлен либо в виде некоторого типа записи, где каждая связь является встроенным указателем (или адресом), либо с помощью некоторого физического упорядочения записей.

Рис. 19. Обобщенное представление древовидной структуры

Узлы представляют интересующие нас объекты, а связи между ними определяются самим расположением узлов и ребер, которые, соединяя узлы, образуют эту древовидную структуру. Объекты могут иметь одинаковый тип. [8]

В-деревья

Хотя многоуровневые индексы считаются неплохим инструментом ускорения процессов обработки запросов, существует более общая, гибкая и эффективная разновидность структур, находящих самое широкое применение в коммерческих СУБД. Речь идет о семействе структур, называемых В-деревьями (B-tree); наиболее распространенный вариант В-дерева известен как В⁺-дерево (B⁺-tree). Основные особенности В-деревьев таковы:

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

эффективное управление размером свободных областей внутри блоков (уровень заполнения блоков колеблется от 50% до 100%) и исключение потребности в использовании блоков переполнения.

Ниже мы будем обсуждать такие характеристики В-деревьев, которые полностью справедливы для В^{+ -} деревьев. Сведения о В-деревьях иных типов вынесены в упражнения.

Структура В-дерева

Как следует из названия структуры В-дерева, ее блоки организованы в виде древовидного графа (tree-like graph). В-дерево является сбалансированным (balanced) - в том смысле, что длины всех путей от корневой (root) вершины до любой из вершин-листьев (leaves) равны. Типичное В-дерево содержит три уровня: корневую вершину, промежуточные вершины и листья, - хотя способно включать и произвольное количество уровней. Чтобы получить начальное представление о В-деревьях, взгляните на рис.20 и 21 [6], описывающие отдельные вершины, и на рис.22 [6], изображающий небольшое полное В-дерево.

Рис. 20. Вершина-лист В-дерева

Рис. 21. Пример промежуточной вершины В-дерева

Рис.22. Пример В-дерева

Каждому В-древовидному индексу поставлен в соответствие параметр п, определяющий свойства компоновки блоков В-дерева. Каждый блок обладает пространством, достаточным для размещения п значений ключа поиска и п + 1 указателей. Блок В-дерева по существу схож с индексными блоками, за исключением того, что наряду с п парами вида "ключ-указатель" он содержит дополнительный, п + 1-й, указатель. Величина п выбирается таким образом, чтобы обеспечить возможность хранения в блоке п + 1 указателей и n ключевых значений. [6]

Бинарное дерево

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

Бинарное дерево - это индекс, состоящий из двух частей: последовательного набора (sequence set) и индексного набора (index set). (Эти термины используются в документации компании IBM, описывающей структуру VSAM-файла. Вам могут встретиться другие, синонимичные термины.) Последовательный набор представляет собой индекс, содержащий указатели на все записи в файле. Этот индекс физически упорядочен, обычно по значению первичного ключа. Такая структура позволяет обращаться к записям последовательно, считывая один за другим адреса записей из последовательного набора н по ним считывая сами записи.

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