Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-06-19 | 289 |
5.00
из
|
Заказать работу |
|
|
Значения ключей физических записей необязательно находятся в логической последовательности. Метод применяется только для выборки данных.
Использование структуры данных типа «дерево»:
очевидно ианалогично вопросу бинарные деревья.
Поиск информации в БД с использованием структуры типа «бинарное дерево».
Бинарное де́рево — древовидная структура данных, в которой каждый узел имеет не более двух потомков. Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.
Бинарное дерево поиска (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 подобные записи — синонимами. В этой ситуации новую запись необходимо вставить в другую позицию, поскольку место с вычисленным для нее хеш-адресом уже занято.
|
Для разрешения конфликтов можно использовать следующие методы:
При возникновении конфликта система выполняет линейный поиск первого доступного слота для вставки в него новой записи.
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!