А.С.Деревянко

А.С.Деревянко

по курсу “Организация и структуры данных”

131217

36 48 75 112 142 188 205 301 410

13 28 38 41 46 80 92 134 140 208 211 213 215 220 254 278 420 480

50 56 63 72 115 123 129 145 157 170 191 203 304 405

Рис.7.2. B⁺-дерево порядка 5

Указатель A[i] в нелистовом узле является адресом узла-потомка, в котором расположены ключи, меньшие, чем ключ K[i], точнее – ключи в интервале К[i-1]<=k<K[i]. Указатель A[M], для которого нет соответствующего ключа в массиве ключей, является адресом узла-потомка, в котором расположены ключи, болшие, чем ключ K[M]. Алгоритм поиска по ключу в . B⁺-дереве является очевидным.

Чрезвычайно существенным является то обстоятельство, что заполненность узлов дерева может изменяться в пределах, заданных условием 1. Это дает возможность реализовать операции вставки и удаления для . B⁺-дерева весьма эффективно. При вставке находится листовой узел, в который должна вставляться новая запись. Если в узле еще есть свободное место, то запись просто вставляется в лист и на этом операция заканчивается. Если свободного места в листе уже нет, то лист расщепляется на 2 листа, и записи из заполненного листа перераспределяются между двумя листами, каждый из которых оказывается заполненным наполовину. Расщепление приводит к тому, что в узел-предок необходимо вставить новую пару значений ключ-указатель. Если в узле предке еще есть свободное место, то новая пара вставляется на свободное место, и на этом операция заканчивается. Если свободного места в узле уже нет, то узел расщепляется на 2 узла и т.д.

При удалении если удаление записи из листа не приводит к тому, что лист окажется заполненным менее, чем наполовину, запись удаляется в листе и на этом операция заканчивается. Если же лист оказывается заполненным менее, чем наполовину, то выполняется перераспределение записей между ним и соседним листом (и соответствующая коррекция ключей-указателей в узле-предке). Если в соседнем узле m/2 записей, то два соседних узла сливаются в один (его заполненность будет m-1 записей). Слияние узлов приводит к удалению пары значений ключ-указатель в узле-предке. Если удаление пары из узла не приводит к тому, что узел окажется заполненным менее, чем наполовину, пара удаляется в узле, и на этом операция заканчивается. Если же узел оказывается заполненным менее, чем наполовину … и т.д.

Таким образом, за счет того, что имеется значительный “допуск” на заполненность узлов/листьев дерева, изменение в подавляющем большинстве случаев удается локализовать в том узле/листе, к которому они непосредственно относятся. Поскольку порядок дерева может быть выбран достаточно большим, глубина дерева оказывается незначительной и путь к любому листу дерева включает в себя прохождение небольшого числа узлов (а каждое прохождение узла – чтение записи с диска). Последовательный же доступ к записям обеспечивается тем, что листья дерева связываются через специальные указатели в линейный список. На рис.7.1. эти связи показаны пунктирными стрелками. Линейный список получается упорядоченным по возрастанию ключей.

Как и для случая файлов прямого доступа, хранение данных в B⁺-дереве предполагает наличие индекса, который собственно и является B⁺-деревом и области данных – неупорядоченного последовательного файла. Для одной и той же области данных могут создаваться несколько индексов для различных ключей.

 

 

Литература

 

1. Далека В.Д., Деревянко А.С., Кравец О.Г., Тимановская Л.Е. Структуры и организация данных. – Харьков:ХГПУ, 2000.

2. Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. - М.:Мир, 1976.

3. Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. - М.:Мир, 1976.

4. Костин Е.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах.- М.: Высш. школа, 1987.

5. Трамбле Ж., Соренсон П. Введение в структуры данных.- М.: Машиностроение, 1982.

6. Salzberg B. File Structures. An analityc approach. – Prentice-Hall:NJ,1988