Тема Структуры данных и алгоритмы
Вид материала | Конспект |
- Программа дисциплины «Структуры данных», 88.1kb.
- Программа курса Алгоритмы программирования, 47.59kb.
- Цель любой программы обработка данных, т е. надо грамотно построить структуры данных, 165.23kb.
- Borland Turbo Pascal, знать простые основные алгоритмы работы с простыми типами данных, 316.19kb.
- Об использовании структур представления данных для решения возникающих задач; знать, 116.73kb.
- Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.
- Программа дисциплины структуры и алгоритмы компьютерной обработки данных для специальности, 506.16kb.
- Введение Предмет "Программирование", 19.2kb.
- Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
- Ю. А. Самарский 10 июня 2008 г. Программа, 97.03kb.












36 48 75 112 142 188 205 301 410























































Рис.7.2. B+-дерево порядка 5
Указатель A[i] в нелистовом узле является адресом узла-потомка, в котором расположены ключи, меньшие, чем ключ K[i], точнее – ключи в интервале К[i-1]<=k
Чрезвычайно существенным является то обстоятельство, что заполненность узлов дерева может изменяться в пределах, заданных условием 1. Это дает возможность реализовать операции вставки и удаления для . B+-дерева весьма эффективно. При вставке находится листовой узел, в который должна вставляться новая запись. Если в узле еще есть свободное место, то запись просто вставляется в лист и на этом операция заканчивается. Если свободного места в листе уже нет, то лист расщепляется на 2 листа, и записи из заполненного листа перераспределяются между двумя листами, каждый из которых оказывается заполненным наполовину. Расщепление приводит к тому, что в узел-предок необходимо вставить новую пару значений ключ-указатель. Если в узле предке еще есть свободное место, то новая пара вставляется на свободное место, и на этом операция заканчивается. Если свободного места в узле уже нет, то узел расщепляется на 2 узла и т.д.
При удалении если удаление записи из листа не приводит к тому, что лист окажется заполненным менее, чем наполовину, запись удаляется в листе и на этом операция заканчивается. Если же лист оказывается заполненным менее, чем наполовину, то выполняется перераспределение записей между ним и соседним листом (и соответствующая коррекция ключей-указателей в узле-предке). Если в соседнем узле m/2 записей, то два соседних узла сливаются в один (его заполненность будет m-1 записей). Слияние узлов приводит к удалению пары значений ключ-указатель в узле-предке. Если удаление пары из узла не приводит к тому, что узел окажется заполненным менее, чем наполовину, пара удаляется в узле, и на этом операция заканчивается. Если же узел оказывается заполненным менее, чем наполовину … и т.д.
Таким образом, за счет того, что имеется значительный “допуск” на заполненность узлов/листьев дерева, изменение в подавляющем большинстве случаев удается локализовать в том узле/листе, к которому они непосредственно относятся. Поскольку порядок дерева может быть выбран достаточно большим, глубина дерева оказывается незначительной и путь к любому листу дерева включает в себя прохождение небольшого числа узлов (а каждое прохождение узла – чтение записи с диска). Последовательный же доступ к записям обеспечивается тем, что листья дерева связываются через специальные указатели в линейный список. На рис.7.1. эти связи показаны пунктирными стрелками. Линейный список получается упорядоченным по возрастанию ключей.
Как и для случая файлов прямого доступа, хранение данных в B+-дереве предполагает наличие индекса, который собственно и является B+-деревом и области данных – неупорядоченного последовательного файла. Для одной и той же области данных могут создаваться несколько индексов для различных ключей.
Литература
- Далека В.Д., Деревянко А.С., Кравец О.Г., Тимановская Л.Е. Структуры и организация данных. – Харьков:ХГПУ, 2000.
- Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. - М.:Мир, 1976.
- Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. - М.:Мир, 1976.
- Костин Е.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах.- М.: Высш. школа, 1987.
- Трамбле Ж., Соренсон П. Введение в структуры данных.- М.: Машиностроение, 1982.
- Salzberg B. File Structures. An analityc approach. – Prentice-Hall:NJ,1988