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

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

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

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

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

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

Бинарное дерево поиска (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 подобные записи — синонимами. В этой ситуации новую запись необходимо вставить в другую позицию, поскольку место с вычисленным для нее хеш-адресом уже занято.

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

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


investicionnaya-privlekatelnost-otraslej-podotraslej-ekonomiki-i-otdelnih-regionov.html
investicionnaya-programma-i-finansovo-ekonomicheskij-analiz.html
    PR.RU™