Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево

Организация работы базы данных с помощью сбалансированных В-деревьев: принципы, методы добавления, поиска, удаления элементов из структуры. Процедуры, производящие балансировку и слияние записей в блоке. Реализация программы в Научной библиотеке ОрелГТУ.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Очевидно, что физическое упорядочение записей индекса имеет те же недостатки, что и физическое упорядочение самих записей основного файла: необходимость реорганизации файла при операциях вставки, удаления, модификации. Следовательно, для организации индекса должен использоваться некоторый вариант кучи. Однако при этом недостаточно иметь простую структуру типа двунаправленного списка, поскольку придется при каждой модификации индекса выполнять сортировку. При этом также следует иметь ввиду, что количество записей в индексе может быть очень велико (размеры файла могут во много раз превышать доступную оперативную память), таким образом, применение обычных методов сортировки, которые ориентируются на размещение всех сортируемых элементов, может быть невозможно.
В оперативной памяти упорядоченные структуры, допускающие эффективную вставку, удаление и модификацию данных обычно организуются в виде сбалансированных деревьев (AVL-деревьев). Сбалансированные деревья - это двоичные деревья, для которых постоянно поддерживается равномерное распределение вершин между поддеревьями. При этом достигается близкая к теоретической (для двоичного поиска) эффективность поиска (порядка шагов, где - общее количество элементов, среди которых происходит поиск) при приемлемых затратах на балансировку.
Однако использование таких структур для организации индексов во внешней памяти оказывается крайне неэффективным из-за больших затрат на ввод вывод. Действительно, поскольку теперь вершины располагаются не в оперативной памяти, а на внешних устройствах, то каждое обращение к вершине (при поиске или в ходе балансировки) требует отдельной операции чтения или записи. Таким образом, если дерево содержит, например 1000000 вершин, то в среднем может потребоваться около 20 операций обращения к внешней памяти. Количество таких обращений будет больше, если происходит балансировка.
Естественным подходом к преодолению данной проблемы является группировка нескольких вершин дерева в один блок ввода-вывода. При этом в древовидную структуру организуются блоки, а не отдельные вершины. Несмотря на то, что возникает необходимость производить поиск внутри блока, количество обращений к устройству внешней памяти сокращается.
Весьма распространенный в настоящее время подход к организации упорядоченных индексов был предложен в 1970г. Р. Бэйером и Э. Мак-Kрейтом. Предложенные ими структуры получили название В-деревьев. В-дерево представляет собой сильно ветвящееся дерево, обладающее следующими свойствами:
- Каждая вершина может содержать не более 2n ключей.
- Каждая вершина за исключением, может быть, корневой содержит не менее n ключей (корневая вершина, если она не является листом, содержит не менее двух потомков).
- Каждая вершина либо представляет собой лист и не имеет потомков, либо имеет в точности m+1 потомка, где m - количество ключей в вершине.
- Все листовые вершины располагаются на одном уровне.
В-дерево может быть построено следующим образом. Последовательность записей, соответствующая записям исходной таблицы, упорядочивается по значениям первичного ключа. Логические записи объединяются в блоки. Значением ключа блока является минимальное значение ключа у записей, входящих в блок. Последовательность блоков представляет собой последний уровень В-дерева. Строится индекс предыдущего уровня. Записи этого уровня содержат значение ключа блока следующего уровня и указатель - адрес связи соответствующего блока ; записи этого уровня также объединяются в блоки. Затем аналогично строится индекс более высокого уровня и т.д., пока количество записей индекса на определенном уровне будет не более установленного числа записей в блоках.
В В-дереве не должно быть блоков, заполненных меньше, чем наполовину. Значение ключа первой записи индексного блока пропускается.
Каждая нелистовая вершина Б-дерева имеет вид:

Здесь p i представляет собой указатель на i -го потомка, а k i - значение ключа поиска (указатели на записи основного файла ради простоты не указаны). Для любого i в диапазоне [1, m-1] все ключи, расположенные в поддереве, на которое указывает указатель p i , находятся в диапазоне [k i , k i +1 ]. Соответственно, все ключи поддерева p 0 будут меньше k 1 , а все ключи поддерева p m - больше k m .
Поиск некоторого k ключа в Б-дереве происходит следующим образом. Начиная с корневой вершины выполняется следующая последовательность действий:
Просматриваются ключи k 1 , k 2 , , k m , Если искомый ключ k найден, то по соответствующему указателю извлекается запись основного файла. Для поиска ключа в вершине может использоваться либо простой последовательный поиск, если m невелико, или двоичный поиск, для достаточно больших m.
Если k i < k< k i +1 для i в диапазоне [1, m-1], то поиск продолжается на странице p i .
Если k< k 1 , то поиск продолжается на странице p 0 .
Если k>k m , то поиск продолжается на странице p m .
При вставке ключа сначала происходит поиск соответствующей вершины (очевидно, что это будет листовая вершина). Затем происходит следующие операции:
Если найденная вершина содержит менее 2*n ключей, то ключ просто добавляется к данной вершине.
Если страница уже заполнена, то она разделяется на две. При этом 2*n из 2*n+1 ключей пополам (с учетом порядка) распределяются между получившимися вершинами. Центральный ключ (по значению) помещается в родительскую вершину. При этом может произойти ее разделение.
Когда происходит разделение корневой вершины, Б-дерево вырастает на один уровень.
При удалении из Б-дерева происходит балансировка и слияние страниц. Процедуру удаления можно описать следующим образом:
Если удаляемый ключ находится на листовой вершине, то он просто удаляется.
Если удаляемый ключ находится на промежуточной вершине, то он заменяется на смежный элемент, который расположен на листовой вершине.
Если в результате удаления количество ключей вершины стало меньше n, то выполняется балансировка - ключи поровну распределяются между данной, родительской и смежной вершинами.
Если количество ключей на смежной вершине равно n, то балансировка невозможна, но можно слить данную и смежную вершины, заняв один ключ из родительской. Это может привести в свою очередь к балансировке или слиянию на следующем уровне.
Обычно В-дерево храниться в файле по вершинам - каждая вершина занимает виртуальный блок файла, а значит, требует одной операции ввода/вывода. Порядок дерева зависит от размера блока и от размера ключа поиска. Чем больше количество ключей располагается в блоке, тем меньше будет операции ввода/вывода, однако больше операций потребуется для обработки отдельного блока (например, при поиске). Уменьшение количества ключей в блоке приводит к увеличению операций ввода/вывода. На практике критическим местом обычно является именно ввод/вывод, соответственно стремятся увеличивать количество ключей в блоке. Это тем более важно, потому, что доступ к блокам происходит в порядке близком к случайному.
В программе использованы следующие типы данных:
- Key: array [1..KEYS] of integer - массив, хранящий ключи записей.
- Child: array [0..KEYS] of TBTreeNode - массив указателей на другие записи.
Сразу можно заметить, что массив Key можно сделать типом record и задать ему тем самым любую структуру. В виду острой нехватки времени был выбран именно просто массив ключей, с которым работать намного быстрее. В соответствующих местах в коде программы, при изменении типа массива Key и соблюдении соответствующих индексов, остается лишь необходимым прописать заполнение и обработку соответствующих полей.



1. Род Стивенс, Delphi. Готовые алгоритмы: Переводс англ.- М.: ДМК Пресс, 2001.-384с: ил.
2. Карпатов Д.С. Базы данных в Delphi 7.Самоучитель . СПб.-Наука и техника, 2006.
Описание процедуры выбора структуры хранения данных. Программная реализация одномерного неоднородного массива. Представление бинарного дерева в виде динамической структуры данных. Изучение способов поиска в упорядоченном дереве. Содержание базы данных. практическая работа [850,0 K], добавлен 16.04.2015
Организация данных с помощью бинарных деревьев. Определение бинарного дерева. Упорядоченное двоичное дерево поиска и его свойства. Программная реализация добавления данных в упорядоченное двоичное дерево с использованием динамических структур данных. курсовая работа [459,0 K], добавлен 09.08.2012
Сбалансированные многоходовые деревья поиска. Исследование структуры B+-дерева, её основные операции. Доказательство их вычислительной сложности. Утверждение о высоте. Поиск, вставка, удаление записи, поиск по диапазону. B+-деревья в системах баз данных. курсовая работа [705,5 K], добавлен 26.12.2013
Рассмотрение нелинейных динамических структур данных в виде бинарного дерева. Построение дерева двоичного поиска. Реализация трех обходов дерева, выведение обходов на экран компьютера. Разработка текста программы. Симметричноправая прошивка дерева. контрольная работа [81,6 K], добавлен 14.12.2011
Обоснование выбора языка и среды программирования. Обзор и анализ существующих программных решений. Разработка графического и пользовательского интерфейса. Алгоритм бинарного поиска. Методы добавления, удаления элемента из дерева и вывода на экран. курсовая работа [1,3 M], добавлен 31.05.2016
Реализация программы в виде класса, используя для хранения информации контейнеры стандартной библиотеки шаблонов (STL) языка C++. Создание новой базы данных. Вывод информации о всех компьютерах. Удаление элементов контейнера, их поиск по критериям. курсовая работа [97,4 K], добавлен 10.01.2015
Типы ограничений, поддерживающие целостность в реляционной модели данных. Определение значения поля первичного ключа с помощью генератора. Добавление, изменение и удаление записей в таблицу базы данных "Библиотека" на языке программирования SQL. лабораторная работа [30,5 K], добавлен 10.10.2012
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево курсовая работа. Программирование, компьютеры и кибернетика.
Реферат по теме В-лимфоциты. Рецепторы и маркеры. Участие в иммунном ответе
Курсовая работа по теме Локальная вычислительная сеть
Реферат по теме Взаимосвязь некоторых признаков у кормовых бобов
Традиции И Обряды В Культуре Реферат
Реферат На Тему Таламус И Гипоталамус: Строение, Важнейшие Свойства
Реферат: Планирование тренировочных нагрузок по плаванию в современном пятиборье
Дипломная работа по теме Исследование финансового состояния ОСАО 'РЕСО-Гарантия'
Курсовая Работа На Тему Стили Государственного Управления
Учебное пособие: Методические указания к разделу Общевоинские уставы
Курсовая работа по теме Очистка вентиляционных газов от паров ацетона методом абсорбции
Сочинение Про Картину Герасимова После Дождя
Болезнь Нервной Системы Реферат
Реферат Күренекле Сәяхәтчеләр География 5 Сыйныф
Реферат: Как возникли деньги. Скачать бесплатно и без регистрации
Методичка По Написанию Магистерской Диссертации 2022
Курсовая работа по теме Особенности сестринской помощи при раке желудка
Реферат: Фунции управления
Реферат: Новая экономическая политика (НЭП). Скачать бесплатно и без регистрации
Произведения По Итоговому Сочинению
Реферат по теме Криминалистика 1
Диагностика и ремонт лазерного принтера - Программирование, компьютеры и кибернетика курсовая работа
Составление плана по результатам топографических съемок - Геология, гидрология и геодезия курсовая работа
Организация как открытая система управления - Менеджмент и трудовые отношения курсовая работа