Главная Промышленная автоматика.

11.4. Внешние деревья поиска

Древовидные структуры данных, которые обсуждались в главе 5 в качестве средства представления множеств, можно использовать для представления внешних файлов. В-дерево, являюшееся обобшением 2-3 дерева (см. главу 5), особенно удачно подходит для представления внешней памяти и стало стандартным способом организации индексов в системах баз данных. В этом разделе мы познакомим читателей с базовыми методами поиска, вставки и удаления информации в В-деревьях.

Разветвленные деревья поиска

Обобшением дерева двоичного поиска является от-арное дерево, в котором каждый узел имеет не более т сыновей. Так же, как и для деревьев двоичного поиска, будем считать, что выполняется следуюшее условие: если и пг являются двумя сьшовьями одного узла и Пу находится слева от пз, тогда все элементы, исходяшие вниз от пу, оказываются меньше элементов, исходяших вниз от Лз- Операторы MEMBER, INSERT и DELETE для m-арного дерева поиска реализуются путем естественного обобшения тех операций для деревьев двоичного поиска, которые обсуждались в разделе 5.1.

Однако в данном случае нас интересует проблема хранения записей в файлах, когда файлы хранятся в виде блоков внешней памяти. Правильным применением идеи разветвленного дерева является представление об узлах как о физических блоках. Внутренний узел содержит указатели на своих от сыновей, а также т - 1 ключевых значений, которые разделяют потомков этих сыновей. Листья также являются блоками; эти блоки содержат записи основного файла.

Если бы мы использовали дерево двоичного поиска из п узлов для представления файла, храняшегося во внешней памяти, то для поиска записи в таком файле нам потребовалось бы в среднем loggn обрашений к блокам. Если бы вместо дерева двоичного поиска мы использовали для представления файла т-арное дерево поиска, то для поиска записи в таком файле нам потребовалось бы лишь iog„n обращений к блокам. В случае и = 10 дерево двоичного поиска потребовало бы примерно 20 обрашений к блокам, тогда как 128-арное дерево поиска потребовало бы лишь 3 обрашения к блокам.

Однако мы не можем сделать т сколь угодно большим, поскольку чем больше т, тем больше должен быть размер блока. Более того, считывание и обработка более крупного блока занимает больше времени, поэтому сушествует оптимальное значение т, которое позволяет минимизировать время, требующееся для просмотра внешнего ffi-арного дерева поиска. На практике значение, близкое к такому минимуму, получается для довольно широкого диапазона величин т. (См. упражнение 11.18.)

В-деревья

В-дерево - это особый вид сбалансированного от-арного дерева, который позволяет нам выполнять операции поиска, вставки и удаления записей из внешнего файла с гарантированной производительностью для самой неблагоприятной ситуации. Оно представляет собой обобшение 2-3 дерева, которое обсуждалось в разделе 5.4. С формальной точки зрения В-дерево порядка т представляет собой от-арное дерево поиска, характеризующееся следующими свойствами.

1. Корень либо является листом, либо имеет по крайней мере двух сыновей.

2. Каждый узел, за исключением корня и листьев, имеет от [т/2] до т сыновей.

3. Все пути от корня до любого листа имеют одинаковую длину.

Обратите внимание: каждое 2-3 дерево является В-деревом порядка 3, т.е. 3-арным. На рис. 11.7 показано В-дерево порядка 5, здесь предполагается, что в блоке листа умешается не более трех записей.




Рис. 11.7. В-дерево порядка 5

В-дерево можно рассматривать как иерархический индекс, каждый узел в котором занимает блок во внещней памяти. Корень В-дерева является индексом первого уровня. Каждый нелистовой узел на В-дереве имеет Сроршу(Pf,,k,p,k,.....КРп) >

где Pi является указателем на i-ro сына, О < i < п, а ki - ключ, 1 < \ < п. Ключи в узле упорядочены, поэтому ki< кг < ... < k„. Все ключи в поддереве, на которое указываетро. меньще, чем ky. В случае 1 < i < п все ключи в поддереве, на которое указывает Pi, имеют значения, не меньщие, чем fe,, и меньщие, чем й,. Все ключи в поддереве, на которое указываетр„, имеют значения, не меньщие, чем k„.

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

Поиск записей

Если требуется найти запись г со значением ключа х, нужно проследить путь от корня до листа, который содержит г, если эта запись вообще существует в файле. Мы проходим этот путь, последовательно считывая из внещней памяти в основную внутренние узлы (ро, fe„ pi, к„, р„) и вычисляя положение х относительно ключей ki, Й2. kn- Если ki< X < тогда в основную память считывается узел, на который указывает Pi, и повторяется описанный процесс. Если х < ky, для считывания в основную память используется указатель ро; если х > k„, тогда используется р„. Когда в результате этого процесса мы попадаем на какой-либо лист, то пытаемся найти запись со значением ключа х. Если количество входов в узле невелико, то в этом узле можно использовать линейный поиск; в противном случае лучще воспользоваться двоичным поиском.

Вставка записей

Вставка в В-дерево подобна вставке в 2-3 дерево. Если требуется вставить в В-дерево запись г со значением ключа х, нужно сначала воспользоваться процедурой поиска, чтобы найти лист L, которому должна принадлежать запись г. Если в L есть место для этой записи, то она вставляется в Е в требуемом порядке. В этом случае внесение каких-либо изменений в предков листа Е не требуется.

Если же в блоке листа L нет места для записи г, у файловой системы запращива-ется новый блок Lи перемещается последняя половина записей из Z, в L, вставляя г в требуемое место в L или L. Допустим, узел является родителем узла L. Р известен, поскольку процедура поиска отследила путь от корня к листу L через узел Р. Теперь можно рекурсивно применить процедуру вставки, чтобы разместить в Р ключ

Эта стратегия представляет собой простейший из возможных вариантов реакции на ситуацию, когда необходимо "расщепить" блок. Некоторые другие варианты, обеспечивающие более высокую среднюю заполненность блоков за счет выполнения дополнительных действий при вставке каждой записи, упоминаются в упражнениях.

7617



kи указатель Iта. L; кvs. Г вставляются сразу же после ключа и указателя для листа/,. Значение йявляется наименьщим значением ключа в I/.

Если Р уже имеет тп указателей, вставка йи Г в Р приведет к расщеплению Р и потребует вставки ключа и указателя в узел родителя Р. Эта вставка может произвести "эффект домино", распространяясь на предков узла L в направлении корня (вдоль пути, который уже был пройден процедурой поиска). Это может даже привести к тому, что понадобится расщепить корень (в этом случае создается новый корень, причем две половины старого корня выступают в роли двух его сыновей). Это единственная ситуация, при которой узел может иметь менее т/2 потомков.

Удаление записей

ЕСЛИ требуется удалить запись г со значением ключа х, нужно сначала найти лист L, содержащий запись г. Затем, если такая запись существует, она удаляется из L. Если г является первой записью в L, мы переходим после этого в узел Р (родителя листа L), чтобы установить новое значение первого ключа для L. Но если L является первым сыном узла Р, то первый ключ L не зафиксирован в Р, а появляется в одном из предков Р. Таким образом, надо распространить изменение в наименьщем значении ключа L в обратном направлении вдоль пути от L К корню.

Если блок листа L после удаления записи оказывается пустым, он отдается файловой системе. После этого корректируются ключи и указатели в Р, чтобы отразить факт удаления листа L. Если количество сыновей узла Р оказывается теперь мень-щим, чем т/2, проверяется узел Р, расположенный в дереве на том же уровне непосредственно слева (или справа) от Р. Если узел Римеет по крайней мере [т/2] + 2 сыновей, ключи и указатели распределяются поровну между Р и Ртак, чтобы оба эти узла имели по меньщей мере ]т/2] потомков, сохраняя, разумеется, упорядочение записей. Затем надо изменить значения ключей для Р и Рв родителе Р и, если необходимо, рекурсивно распространить воздействие внесенного изменения на всех предков узла Р, на которых это изменение отразилось.

Если у Р имеется ровно ]т/2] сыновей, мы объединяем Р и Р в один узел с 2]т/2] - 1 сыновьями. Затем необходимо удалить ключ и указатель на Риз родителя для Р. Это удаление можно выполнить с помощью рекурсивного применения процедуры удаления.

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

Пример П.5. Рассмотрим В-дерево порядка 5, показанное на рис. 11.7. Вставка записи со значением ключа 23 порождает В-дерево, показанное на рис. 11.8. Чтобы вставить эту запись, надо расщепить блок, содержащий записи с ключами 22, 23, 24 и 26, поскольку предполагаем, что в один блок помещается не более трех записей. Два меньщих остаются в этом блоке, а два больщих помещаются в новый блок. Пару "указатель-ключ" для нового узла нужно вставить в родителя, который в таком случае расщепляется, поскольку не может содержать щесть указателей. Корень принимает пару "указатель-ключ" для нового узла, однако корень не расщепляется, поскольку он располагает достаточной емкостью.

Удаление записи с ключом 10 из В-дерева, показанного на рис. 11.8, приводит к В-дереву, показанному на рис. 11.9. В этом случае блок, содержащий запись с ключом 10, отбрасывается. У его родителя теперь оказывается только два

Чтобы предотвратить возможное полное опустошение блоков листов, можно применять различные стратегии. В частности, ниже мы описываем схему предотвращения опустошения внутренних узлов более чем наполовину. Этот метод можно применить и к листьям.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 [106] 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002