А. Записи хранимого файла

Индекс

Включение и удаление записей.

Например, нам необходимо включить запись с адресом с=9 с ключевым реквизитом q=35. Среди имеющихся записей отыскиваются такие, что q_i-1<q_i<q_i+1 (31<35<40)/ Затем в поле указателя предыдущей записи (с ключом 31) поместить ссылку на новую запись - 9, а ссылку на следующий элемент цепи, ранее находящуюся в предыдущей записи (с ключом 31) – 8 поместить в поле новой.

3-й учебный вопрос: Индексно-последовательная организация файла.

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

Рис. Индексно-последовательная организация файла

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

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

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

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

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

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

На каждом уровне (для нашего случая) индекса и данных осуществляется поиск нужного элемента с использованием известных методов поиска (бинары, блочи последовательного …).

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

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

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

4-й учебный вопрос: Хеширование (произвольного доступа).

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

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

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

Пример.

Предположим, что значениями ключей S является S100, S200; S300; S400; S500.

Рассмотрим хеш – функцию: адрес хранимой записи равен остатку от деления значения ключей на 13.

Значение ключей	Значение хеш – функции – «деление/остаток»

Адресами хранимых записей в данном случае будут 9; 5; 1; 10; 6 соответственно, обеспечивая представление, изображенное на рис. А, (где мы предположим, что значения адреса хранимой записи представляют собой позиции в пределах хранимого файла).

Рис. А Организация на основе хеш – адресации.

Для чего необходима хеш – функция?

Теоретически возможно использование первичного ключа в качестве адреса хранимой записи, однако как правило, этот вариант не приемлем, так как диапазон значений первичного ключа намного шире доступных адресов хранимых записей (т.е. того количества, которое имеется на практике). Например, предположим, что номера поставщиков являются трехзначными, т.е. теоретически допускается 1000 поставщиков, а на практике их можешь быть 10. В целях экономии памяти необходимо, чтобы хеш – функция переводила любые значения из диапазона 0-999 в другой диапазон значений.

Мы практически выбрали функцию, которая генерирует значения в диапазоне 0-12.

Основным требованием к хеш – функции является равномерное распределение значений свертки. RS (чтобы меньше было незаполненных ячеек. См. рис. А)

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

Значения ключей, которые имеют одно и тоже значение хеш – функции называются синонимами.

Главным ограничением этого метода является фиксированный размер таблицы (основной области), после заполнения которой возникают цепочки переполнения.

Следовательно при использовании хеширования как метода доступа следует:

1. Выбрать хеш – функцию

2. Выбрать метод разрешения коллизии.

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

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

Заключение

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

Хранение ссылок на блоки уменьшает в N раз размер индекса по сравнению с хранением ссылок на отдельные записи, N – число элементов в каждом индексном блоке.

Время доступа к записи соответственно уменьшается.

Каждое значение ключа в индексе уровня i представляет собой наибольшее (наименьшее) значение ключа в блоке индекса на (i+1) уровне. В нашем случае наибольшее.

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

Дата добавления: 2014-01-04