Операторы на В-дереве

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

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

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

Если в блоке листа L нет места для записи r, у файловой системы запрашивается новый блок L` и из L в L` перемещается последняя половина записей. При этом r вставляется в требуемом порядке в L или L`. Допустим, узел Р является родителем узла L. Р известен, поскольку процедура поиска отследила путь от корня к листу L через узел Р. Теперь можно рекурсивно применить процедуру вставки, чтобы разместить в Р ключ k` и указатель l` на L`. k` и l` вставляются сразу же после ключа и указателя для листа L. Значение k` является наименьшим значением ключа в L`.

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

Удаление записей. Если требуется удалить запись r со значением ключа х, нужно сначала найти лист L, содержащий запись r. Затем, если такая запись существует, она удаляется из L. Если r является первой записью в L, после этого выполняется переход в узел P – родителя листа L, чтобы установить новое значение первого ключа для L. Если L является первым сыном узла P, то первый ключ L не зафиксирован в P, а появляется в одном из предков P. Таким образом, надо распространить изменение в наименьшем значении ключа L в обратном направлении вдоль пути от L к корню.

Если блок листа L после удаления записи оказывается пустым, он отдается файловой системе. После этого корректируются ключи и указатели в P, чтобы отразить факт удаления листа L. Если количество сыновей узла P оказывается теперь меньшим, чем m/2, проверяется узел P`, расположенный в дереве на том же уровне непосредственно слева или справа от P. Если узел P` имеет хотя бы m/2+2 сыновей, ключи и указатели распределяются поровну между P и P` так, чтобы оба эти узла имели хотя бы по m/2 потомков, сохраняя упорядоченность записей. Затем необходимо изменить значения ключей для P и P` в родителе P и, если необходимо, рекурсивно распространить воздействие внесенного изменения на всех предков узла P, на которых это изменение отразилось.

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

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

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

Рис. 53 – В-дерево после вставки в него записи

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

Рис. 54 – В-дерево послед удаления записи

Сравнение методов

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

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

Разреженный индекс для файла, состоящего из n записей, позволяет выполнять операции с файлами, ограничиваясь использованием примерно обращений к блокам в случае двоичного поиска, где b – количество записей, помещающихся в один блок, а b` – количество пар ключ-указатель, помещающихся в один блок для индексного файла. В-деревья позволяют выполнять операции с файлами с использованием примерно обращений к блокам, где m – максимальное количество сыновей у внутренних узлов, что приблизительно равняется b`. Как разреженные указатели, так и В-деревья допускают обращение к записям в отсортированной последовательности.

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

Не нашли, что искали? Воспользуйтесь поиском: