Физическая организация данных. Бинарное дерево. Поиск записи по бинарному дереву. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Физическая организация данных. Бинарное дерево. Поиск записи по бинарному дереву.



Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказвается меньше ключа, поиск продолжается в левом поддереве, а в случае когда больше ключа - в правом поддереве. Увеличив уровень на 1 повторяют сравнение, считая текущий узел корнем.

Пример: Пусть дан список студентов, содержащий их фамилии и средний бал успеваемости (см. таблицу 1.1). В качестве ключа используется фамилия студента. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычислятся как ([номер_записи] -1) * [длина_записи]. Пусть аргумент поиска "Петров". На рисунке 1.2 показаны одно из возможных для этого набора данных бинарных деревьев поиска и путь поиска.

 

Таблица 1.1.
Студент Балл
Васильев 4,2
Иванов 3,4
Кузнецов 3,5
Петров 3,2
Сидоров 4,6
Тихомиров 3,8

 


Рис. 1.2.Поиск по бинарному дереву.

Заметим, что здесь используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.

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

Определение: Бинарное дерево называют сбалансированным (balanced), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1.

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


Трехуровневая архитектура банка данных (БнД).

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

Концептуальный уровень. Структурный уровень БД, определяющий логическую схему БД.

Внешний уровень - составляет пользовательские представления данных БД.

Каждый пользователь или группа пользователей имеет свое собственное представление данных в БД.

Каждое такое представление дает ориентированное на пользователя описание элементов данных и отношений между ними. Совокупность всех пользовательских представлений и составляет внешний уровень данных.

Внешний уровень. Структурный уровень БД, определяющий пользовательские представления данных.

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

Внутренний уровень. Структурный уровень базы данных, определяющий физический вид базы данных.

Трехуровневая архитектура обеспечивает логическую (между уровнем 1 и2) и физическую (между 2 и 3) независимость при работе с данными.

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

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

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



Поделиться:


Последнее изменение этой страницы: 2017-01-25; просмотров: 137; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.90.205.166 (0.019 с.)