Структуры данных и алгоритмы (1021739), страница 88
Текст из файла (страница 88)
ХРАНЕНИЕ ДАННЫХ В ФАЙЛАХ32911.4. Внешние деревья поискаДревовидные структуры данных, которые обсуждались в главе 5 в качестве средства представления множеств, можно использовать для представления внешних файлов. В-дерево, являющееся обобщением 2-3 дерева (см. главу 5), особенно удачноподходит для представления внешней памяти и стало стандартным способом организации индексов в системах баз данных.
В этом разделе мы познакомим читателей сбазовыми методами поиска, вставки и удаления информации в В-деревьях.Разветвленные деревья поискаОбобщением дерева двоичного поиска является m-арное дерево, в котором каждый узел имеет не более т сыновей. Так же, как и для деревьев двоичного поиска,будем считать, что выполняется следующее условие: если п г и п2 являются двумясыновьями одного узла и П] находится слева от п2, тогда все элементы, исходящиевниз от n l t оказываются меньше элементов, исходящих вниз от п2. ОператорыMEMBER, INSERT и DELETE для тп-арного дерева поиска реализуются путем естественного обобщения тех операций для деревьев двоичного поиска, которые обсуждались в разделе 5.1.Однако в данном случае нас интересует проблема хранения записей в файлах, когда файлы хранятся в виде блоков внешней памяти.
Правильным применением идеиразветвленного дерева является представление об узлах как о физических блоках.Внутренний узел содержит указатели на своих от сыновей, а также т - 1 ключевыхзначений, которые разделяют потомков этих сыновей. Листья также являются блоками; эти блоки содержат записи основного файла.Если бы мы использовали дерево двоичного поиска из п узлов для представленияфайла, хранящегося во внешней памяти, то для поиска записи в таком файле нампотребовалось бы в среднем Iog2n обращений к блокам. Если бы вместо дерева двоичного поиска мы использовали для представления файла /га-арное дерево поиска, тодля поиска записи в таком файле нам потребовалось бы лишь logmn обращений кблокам.
В случае п = 10е дерево двоичного поиска потребовало бы примерно 20 обращений к блокам, тогда как 128-арное дерево поиска потребовало бы лишь 3 обращения к блокам.Однако мы не можем сделать т сколь угодно большим, поскольку чем больше т,тем больше должен быть размер блока. Более того, считывание и обработка болеекрупного блока занимает больше времени, поэтому существует оптимальное значениет, которое позволяет минимизировать время, требующееся для просмотра внешнего/n-арного дерева поиска. На практике значение, близкое к такому минимуму, получается для довольно широкого диапазона величин т. (См.
упражнение 11.18.)В-деревьяВ-дерево — это особый вид сбалансированного от-арного дерева, который позволяет нам выполнять операции поиска, вставки и удаления записей из внешнего файлас гарантированной производительностью для самой неблагоприятной ситуации. Онопредставляет собой обобщение 2-3 дерева, которое обсуждалось в разделе 5.4. С формальной точки зрения В-дерево порядка т представляет собой от-арное дерево поиска, характеризующееся следующими свойствами.1. Корень либо является листом, либо имеет по крайней мере двух сыновей.2. Каждый узел, за исключением корня и листьев, имеет от [т/2] до т сыновей.3. Все пути от корня до любого листа имеют одинаковую длину.Обратите внимание: каждое 2-3 дерево является В-деревом порядка 3, т.е.
3арным. На рис. 11.7 показано В-дерево порядка 5, здесь предполагается, что в блокелиста умещается не более трех записей.330ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИЯ!! I104 6 81212 14 16 1820 22 24 26 28 30 32 3436 38 40 42Рис.
11.7, В-дерево порядка 5В-дерево можно рассматривать как иерархический индекс, каждый узел в котором занимает блок во внешней памяти. Корень В-дерева является индексом первогоуровня. Каждый нелистовой узел на В-дереве имеет форму(р„,fe,,д,k 2 ,р 2 ,...,й„,р а ),где PI является указателем на i-ro сына, 0 < i < n, a kt — ключ, 1 < i < п. Ключи в узле упорядочены, поэтому ki < k2 < ... < kn. Все ключи в поддереве, на которое указывает ро, меньше, чем Л]..
В случае 1 < i < n все ключи в поддереве, на которое указывает р^ имеют значения, не меньшие, чем kt, и меньшие, чем ftj+1. Все ключи в поддереве, на которое указывает р„, имеют значения, не меньшие, чем А„.Существует несколько способов организации листьев. В данном случае мы предполагаем, что записи основного файла хранятся только в листьях. Предполагаетсятакже, что каждый лист занимает один блок.Поиск записейЕсли требуется найти запись г со значением ключа х, нужно проследить путь откорня до листа, который содержит г, если эта запись вообще существует в файле.Мы проходим этот путь, последовательно считывая из внешней памяти в основнуювнутренние узлы (р0, felt рг, ..., kn, рп) и вычисляя положение х относительно ключейhi, k2, ..., k^ Если ki £ х < ki+i, тогда в основную память считывается узел, на который указывает pt, и повторяется описанный процесс.
Если х < /г ь для считывания восновную память используется указатель р0; если х 2 А„, тогда используется рп. Когда в результате этого процесса мы попадаем на какой-либо лист, то пытаемся найтизапись со значением ключа х. Если количество входов в узле невелико, то в этом узле можно использовать линейный поиск; в противном случае лучше воспользоватьсядвоичным поиском.Вставка записейВставка в В-дерево подобна вставке в 2-3 дерево.
Если требуется вставить в Вдерево запись г со значением ключа х, нужно сначала воспользоваться процедуройпоиска, чтобы найти лист L, которому должна принадлежать запись г. Если в L естьместо для этой записи, то она вставляется в L в требуемом порядке. В этом случаевнесение каких-либо изменений в предков листа L не требуется.Если же в блоке листа L нет места для записи г, у файловой системы запрашивается новый блок Z/и перемещается последняя половина записей из L в £', вставляя гв требуемое место в L или I/.1 Допустим, узел Р является родителем узла L.
P известен, поскольку процедура поиска отследила путь от корня к листу L через узел Р.Теперь можно рекурсивно применить процедуру вставки, чтобы разместить в Р ключ1Эта стратегия представляет собой простейший из возможных вариантов реакции на ситуацию, когда необходимо "расщепить" блок. Некоторые другие варианты, обеспечивающиеболее высокую среднюю заполненность блоков за счет выполнения дополнительных действийпри вставке каждой записи, упоминаются в упражнениях.11.4. ВНЕШНИЕ ДЕРЕВЬЯ ПОИСКА331К'та. указатель I'на L'; й'и l'вставляются сразу же после ключа и указателя для листа L.
Значение ft'является наименьшим значением ключа в Z/.Если Р уже имеет m указателей, вставка ft'и Г в Р приведет к расщеплению Ри потребует вставки ключа и указателя в узел родителя Р. Эта вставка можетпроизвести "эффект домино", распространяясь на предков узла L в направлениикорня (вдоль пути, который уже был пройден процедурой поиска). Это можетдаже привести к тому, что понадобится расщепить корень (в этом случае создается новый корень, причем две половины старого корня выступают в роли двухего сыновей).
Это единственная ситуация, при которой узел может иметь менеет/2 потомков.Удаление записейЕСЛИ требуется удалить запись г со значением ключа х, нужно сначала найтилист L, содержащий запись г. Затем, если такая запись существует, она удаляется изL. Если г является первой записью в L, мы переходим после этого в узел Р (родителялиста L), чтобы установить новое значение первого ключа для L. Но если L являетсяпервым сыном узла Р, то первый ключ L не зафиксирован в Р, а появляется в одномиз предков Р.
Таким образом, надо распространить изменение в наименьшем значении ключа L в обратном направлении вдоль пути от L К корню.Если блок листа L после удаления записи оказывается пустым, он отдается фай1ловой системе. После этого корректируются ключи и указатели в Р, чтобы отразитьфакт удаления листа L. Если количество сыновей узла Р оказывается теперь меньшим, чем т/2, проверяется узел Р', расположенный в дереве на том же уровне непосредственно слева (или справа) от Р.
Если узел Р' имеет по крайней мере [т/2] + 2сыновей, ключи и указатели распределяются поровну между Р и Р' так, чтобы обаэти узла имели по меньшей мере [т/2] потомков, сохраняя, разумеется, упорядочение записей. Затем надо изменить значения ключей для Р и Р' в родителе Р и, еслинеобходимо, рекурсивно распространить воздействие внесенного изменения на всехпредков узла Р, на которых это изменение отразилось.Если у Р' имеется ровно [т/2] сыновей, мы объединяем Р и Р' в один узел с2[т/2] - 1 сыновьями. Затем необходимо удалить ключ и указатель на Р' из родителя для Р'. Это удаление можно выполнить с помощью рекурсивного примененияпроцедуры удаления.Если "обратная волна" воздействия удаления докатывается до самого корня, возможно, нам придется объединить только двух сыновей корня. В этом случае новымкорнем становится результирующий объединенный узел, а старый корень можновернуть файловой системе.
Высота В-дерева уменьшается при этом на единицу.Пример 11.5. Рассмотрим В-дерево порядка 5, показанное на рис. 11.7. Вставказаписи со значением ключа 23 порождает В-дерево, показанное на рис. 11.8. Чтобывставить эту запись, надо расщепить блок, содержащий записи с ключами 22, 23, 24и 26, поскольку предполагаем, что в один блок помещается не более трех записей.Два меньших остаются в этом блоке, а два больших помещаются в новый блок. Пару"указатель-ключ" для нового узла нужно вставить в родителя, который в таком случае расщепляется, поскольку не может содержать шесть указателей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
