Цепь подобных записей

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2

Рандомизация

Этот метод доступа имеет несколько названий: перемешивание, рандомизация, хэширование. Общая схема представлена на рисунке.

Алгоритм рандомизации

Бакет 1   Бакет 2 ....... Бакет N_max

К₁

К₂

К₃

Область размещения записей файла

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

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

Алгоритм рандомизации состоит из следующих шагов:

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

(1)

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

Тогда, например, ключ Сидоров запишется как 8945752 (различие прописных и строчных букв игнорируется). Очевидно, такая замена может привести к тому, что разные нечисловые значения будут иметь одинаковые числовые замены. Это одна из причин потери информации при выполнении алгоритмов рандомизации;

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

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

8945752 Þ 80026478845504 Þ 4788;

средняя часть числа,

состоящая из 4 цифр

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

8945752 Þ 894 Þ (13)(16)92 Þ 4792;

5752

старшие младшие совмещенные результат окончательный

разряды разряды разряды сложения результат совмещенных разрядов

Ø метод складывания: ключ делится на 3 части, средняя из которых по количеству цифр равна требуемому порядку. Первая и третья части налагаются на среднюю часть и совмещенные цифры складываются. Например, для числа 8945752 такое преобразование будет иметь вид:

8945752 Þ 9457 Þ (17)47(12) Þ 8473.

8 25

средняя результат окончательный

часть наложенные сложения результат

части числа

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

3) полученное на предыдущем шаге число умножается на константу С, которая рассчитывается как отношение максимального номера бакета N_max к максимальному n-разрядному числу, где n – порядок максимального номера бакета. Это позволяет сформировать реальные номера бакетов. Например, пусть максимальный номер бакета – 7000 (это N_max). Очевидно, n = 4. Тогда упомянутая константа С имеет значение:

С=7000/9999=0,7.

Рассчитаем реальный номер бакета для результата предыдущего шага, полученного методом складывания: 8473*0,7=5931.

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

Пусть основной файл имеет вид:

сотрудник

№ п/п	ФИО	ученая степень	научное звание	контактные данные	название (кафедры)	название (должности)
	Иванов И.И.	к.т.н.	доцент		СУиВТ	доцент
	Петров П.П.	к.т.н.	нет		ТАМ	доцент
	Сидоров С.С.	нет	нет		СУиВТ	ассистент
	Яковлев Я.Я.	д.т.н.	профессор		ТАМ	профессор

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

ученая степень	ссылки		научное звание	ссылки		название (кафедры)	ссылки		название (должности)	ссылки
д.т.н.			доцент			СУиВТ			ассистент
к.т.н.			нет			ТАМ			доцент
нет			профессор						профессор

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

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

сотрудник

№ п/п	ФИО	ученая степень	№ п/п	научное звание	№ п/п	контактные данные	название (кафедры)	№ п/п	название (должности)	№ п/п
	Иванов И.И.	к.т.н.		доцент	-		СУиВТ		доцент
	Петров П.П.	к.т.н.	-	нет			ТАМ		доцент	-
	Сидоров С.С.	нет	-	нет	-		СУиВТ	-	ассистент	-
	Яковлев Я.Я.	д.т.н.	-	профессор	-		ТАМ	-	профессор	-

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

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

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

2) по полю ссылки выясняется номер записи основного файлас искомым ключом доступа – это запись с номером 3;

3) в основном файле выбирается третья запись. Выводится фамилия и инициалы сотрудника – это Сидоров С.С.;

4) в соответствии со значением поля № п/п для поля название (должности) в основном файле определяется номер следующей записи основного файла с аналогичным значением вторичного ключа – поскольку данное поле не содержит ссылки, это означает, что цепочка записей закончилась, следовательно, список сотрудников сформирован; алгоритм заканчивает работу.

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

Например, основной список представлен таблицей:

сотрудник

№ п/п	ФИО	ученая степень	№ п/п	научное звание	№ п/п	контактные данные	название (кафедры)	№ п/п	название (должности)	№ п/п
	Иванов И.И.	к.т.н.		доцент	-		СУиВТ		доцент
	Петров П.П.	к.т.н.	-	нет			ТАМ		доцент	-
	Сидоров С.С.	нет	-	нет	-		СУиВТ	-	ассистент	-
	Яковлев Я.Я.	д.т.н.	-	профессор	-		ТАМ	-	профессор	-

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

ученая степень

ссылки

длина цепочки

научное звание

ссылки

длина цепочки

название (кафедры)

ссылки

длина цепочки

название (должности)

ссылки

длина цепочки

д.т.н.

доцент

СУиВТ

ассистент

к.т.н.

нет

ТАМ

доцент

нет

профессор

профессор

Значения полей длина цепочки – это количество записей основного файла с соответствующим значением вторичного ключа.

Пусть надо определить, какие сотрудники работают в должности доцентов и не имеют ученой степени. Очевидно, К_доступ=< название (должности) = доцент, ученая степень = нет). Задача решается следующим образом:

1) в индексах для вторичных ключей название (должности) и ученая степень ищутся записи со значениями полей доцент и нет: это, соответственно, записи с номерами 2 и 3;

2) анализируется, для какого индекса поле длина цепочки имеет минимальное значение: очевидно, длина цепочки для ключа со значением нет короче, чем для ключа со значением доцент, поэтому для поиска в основном файле определяется ключ ученая степень со значением нет;

3) в соответствии со значением поля ссылки выбранного ключа осуществляется обращение к элементу с номером 3 основного файла;

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

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

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