Инвертированный (метод вторичного индексирования)

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

Использование структуры данных типа «дерево»:

очевидно ианалогично вопросу бинарные деревья.

 

 

Поиск информации в БД с использованием структуры типа «бинарное дерево».

Бинарное де́рево — древовидная структура данных, в которой каждый узел имеет не более двух потомков. Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

Бинарное дерево поиска (binary search tree, BST) — это бинарное дерево, для которого выполняются дополнительные условия:

· Оба поддерева — левое и правое, являются двоичными деревьями поиска.

· У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных узла X.

· У всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных узла X.

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

Пример:

Таблица 2 Таблица учеников, где № - ключевое поле

№	Фамилия	Имя	Класс	№	Фамилия	Имя	Класс
	Попов	Егор	2 класс		Попов	Мужик	2 класс
	Омельченко	Сева	4 класс		Веселовский	Ян	4 класс
	Бабаев	Слава	5 класс		Бабаев	Слава	5 класс
	Олегов	Олег	7 класс		Матвеев	Слава	7 класс
	Самойлов	Ян	1 класс		Омельченко	Сева	2 класс
	Самойлов	Стас	3 класс		Матвеев	Мужик	4 класс
	Калинина	Натали	2 класс				7 класс

 

Рисунок 1 Двоичное дерево поиска для таблицы учеников

 

 

Методы хеширования для реализации доступа к данным по ключу.

Статическое хеширование

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

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

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

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

• открытая адресация;
• несвязанная область переполнения;
• связанная область переполнения;
• многократное хеширование.
• Открытая адресация

При возникновении конфликта система выполняет линейный поиск первого доступного слота для вставки в него новой записи.