Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 108
Текст из файла (страница 108)
Если объект находится в оперативной памяти компьютера, то мы обращаемся к его полям обычным способом — например, йеу [х]. Если же обьект, к которому мы обращаемся посредством х, находится на диске, то мы должны выполнить операцию Р1зк Кель(х) для чтения объекта х в оперативную память перед тем, как будем обращаться к его полям. (Считаем, что если объект х уже находится в оперативной памяти, то операция Р[зк КеАп(х) не требует обращения к диску.) Аналогично, для сохранения любых изменений в полях объекта х выполняется операция 01зк %к~те(х). Таким образом, типичный шаблон работы с объектом х имеет следующий вид: х +- указатель на некоторый объект 0!зк КеА0(х) Операции, обращающиеся и/или изменяющие поля х Рвк %иге(х) [> Не требуется, если поля х не изменялись Прочие операции, не изменяющие поля х Глава 18.
В-деревья 519 лзю* П '„!000 72,'~~ ' Г!000 ' ' 1000 ; Г1000 +;~-;-ч;5..-у.~-,'~~!-~ Ф:,~ л к !0!10 ! ! !00!З ' ... ! !00! ! узел, !000 ключей !00! узел, ! 00! 000 ключей 100200! узел, ! 00200! 000 ключей Рис. 18.3. В-дерево, хранящее более миллиарда ключей 18.1 Определение В-деревьев Для простоты предположим, как и в случае бинарных деревьев поиска и красно-черных деревьев, что сопутствующая информация, связанная с ключом, хранится в узле вместе с ключом.
На практике вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопугствующую информацию для данного ключа. Псевдокод в данной главе неявно подразумевает, что при перемещении ключа от узла к узлу вместе с ним перемещается и сопутствующая информация или указатель на нее. В распространенном варианте Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц.
Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций с диском Р!зк Кплп и Р!зк %к!ть, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице.
Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы. Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между 50 и 2000, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа.
На рис. 18.3 показано В-дерево высота которого равна 2, а степень ветвления — 1001; такое дерево может хранить более миллиарда ключей. При этом, поскольку корневой узел может храниться в оперативной памяти постоянно, для поиска ключа в этом дереве требуется максимум два обращения к диску! 520 Часть Ч. Сложные структуры данныи В-дерева, который называется В+-деревам, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. В-дерево Т представляет собой корневое дерево (корень которого гоос [Т]), обладающее следующими свойствами.
1. Каждый узел х содержит следующие поля: а) тз [х], количество ключей, хранящихся в настоящий момент в узле х. б) Собственно ключи, количество которых равно тз [х] и которые хранятся в невозрастающем порядке, так что зсеут [х] < Йеуз [х] « . < /сеун~ ~ [х]. в) Логическое значение 1еа1 [х], равное тане, если х является листом, и рАьзб, если х — внутренний узел. 2.
Кроме того, каждый внутренний узел х содержит и [х] + 1 указателей с1 [х], сз [х],..., с„[ 1+з [х] на дочерние узлы. Листья не имеют дочерних узлов, так что их поля с; не определены. 3. Ключи йеуе [х] разделяют поддиапазоны ключей, хранящихся в поддеревьях: если йе — произвольный ключ, хранящийся в поддереве с корнем с, [х], то Йз < алеут [х] < lсз < Йеуз [х] « . Йеуп[е[ [х] < зс„[в[+г. 4. Все листья расположены на одной и той же глубине, которая равна высоте дерева 1ь 5.
Имеются нижняя и верхняя границы количества ключей, которые могут содержаться в узле. Эти границы могут быть выражены с помощью одного фиксированного целого числа 1 > 2, называемого минимальной степенью (пйпппшп деагее) В-дерева: а) Каждый узел, кроме корневого, должен содержать как минимум 1 — 1 ключей. Каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум г дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ. б) Каждый узел содержит не более 2г — 1 ключей. Таким образом, внутренний узел имеет не более 2т дочерних узлов. Мы говорим, что узел заполнен (ззз!1), если он содержит ровно 2т — 1 ключей'.
Простейшее В-дерево получается при з = 2. При этом каждый внутренний узел может иметь 2, 3 или 4 дочерних узла, и мы получаем так называемое 2-3- 4-дереао (2-3-4 атее).Однако обычно на практике используются гораздо большие значения с. 'Друзой распространенный вариант В-дерева под названием В -дерева, требует, чтобы каждый внутренний узел был заполнен как минимум на две трети, а не наполовину, как в случае В-дерева.
Глава 18. В-деревья 521 количество тлуаиив утлое тке ! Т| Х~+АУ .к .'в ~~Енсу~ уНЬЧ~ Ь','стМ Мд9', У ) 1 ! 2 2 2т 1 2!! Рис. 18.4. В-дерево, высота которого равна 3, с минимально возможным количеством ключей Высота В-дерева Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте.
Проанализируем высоту В- дерева в наихудшем случае. Теорема 18.1. Высота В-дерева Т с и > 1 узлами и минимальной степенью 1 > 2 не пРевышает 1обе (и + 1)/2. л л ,г л и > 1+(2 1)~) '221-~ 1+2(Ф 1) ~ ) 21 1 ~1-1)- в=1 Простейшее преобразование дает нам неравенство 2л < (и+ 1)/2. Теорема доказывается путем логарифмирования по основанию 2 обеих частей этого неравенства.
к! Здесь мы видим преимущества В-деревьев над красно-черными деревьями. Хотя высота деревьев растет как О (18и) в обоих случаях (вспомним, что 1— константа), в случае В-деревьев основание логарифмов имеет гораздо большее значение. Таким образом, В-деревья требуют исследования примерно в 181 раз Доказав!власа!во. Пусть В-дерево имеет высоту и. Корень дерева содержит как минимум один ключ, а все остальные узлы — как минимум по Ф вЂ” 1 ключей. Таким образом, имеется как минимум 2 узла на глубине 1, как минимум 22 узлов на глубине 2, как минимум 2сз узлов на глубине 3 и тд., до глубины Ь, на которой имеется как минимум 21л 1 узлов (пример такого дерева, высота которого равна 3, показан на рис.
18.4). Следовательно, число ключей и удовлетворяет следующему неравенству: 522 Часть Ч. Сложные структуры данньп меньшего количества узлов по сравнению с красно-черными деревьями. Поскольку исследование узла дерева обычно требует обращения к диску, юличество дисковых операций при работе с В-деревьями оказывается существенно сниженным. Упражнения 18.1-1.
Почему минимальная степень В-дерева не может быть равна 1? 18.1-2. Для каких значений здерево карис. 18.1 является корректным В-деревом? 18.1-3. Изобразите все корректные В-деревья с минимальной степенью 2, представляющие множество (1, 2, 3, 4, 5). 18.1-4. Чему равно максимальное количество ключей, которое может храниться в В-дереве высотой Ь, выраженное в виде функции от минимальной степени дерева 1? 18.1-5.
Опишите структуру данных, которая получится, если в красно-черном дереве каждый черный узел поглотит красные дочерние узлы, а их потомки станут дочерними узлами этого черного узла. 18.2 Основные операции с В-деревьями В этом разделе мы более подробно рассмотрим операции В Тккп Зплксн, В Ткни Скнлтн и В Ткнп 1нзнкт. При рассмотрении этих операций мы примем следующие соглашения. ° Корень В-дерева всегда находится в оперативной памяти, так что операция 01зк Кнлп для чтения юрневого узла не нужна; однако при изменении корневого узла требуется выполнение операции Р|зк %итп, сохраняющей внесенные изменения на диске.
° Все узлы, передаваемые в качестве параметров, уже считаны с диска. Все представленные здесь процедуры выполняются за один нисходяший проход по дереву. Поиск в В-дереве Поиск в В-дереве очень похож на поиск в бинарном дереве поиска, но с тем отличием, что если в бинарном дереве поиска мы выбирали один из двух путей, то здесь предстоит сделать выбор из большего количества альтернатив, зависящего от того, сколько дочерних узлов имеется у текущего узла. Точнее, в каждом внутреннем узле х нам предстоит выбрать один из и 1х) + 1 дочерних узлов. Операция В Ткпп Бплксн представляет собой естественное обобщение процедуры Ткпп Бплксн, определенной для бинарных деревьев поиска.
В качестве параметров процедура В Ткпн Зклксн получает указатель на корневой узел Глава 18. В-дереаья 523 х поддерева и ключ /с, который следует найти в этом поддереве. Таким образом, вызов верхнего уровня для поиска во всем дереве имеет вид В ТКЕЕ БеАксн(гоос [т), /с). если ключ /с имеется в В-дереве, процедура В ткее БеАксн вернет упорллоченную пару (у,1), состоящую из узла у и индекса г, такого что Леу, [у) = /с. В противном случае процедура вернет значение нп..
В ТКЕЕ БЕАКСН(х, /с) 1 г< — 1 2 зтЫ1е г < п[х] и /с > Йеус[х] 3 с1ог+ — 1+1 4 Н г < п[х] и /с = /сеу;[х] 5 гиен ге$цгп (х,1) б П 1еа/'[х) 7 Ф/зев гегигп нп. 8 е!ае 13!Як ВеАп(с,[х]) 9 ге1пгв В Ткее БеАксн(с;[х),Л) В строках 1-3 выполняется линейный поиск наименьшего индекса г, такого что /с < /сеу; [х] (иначе 1 присваивается значение и [х]+ 1). В строках 4-5 проверяется, не найден ли ключ в текущем узле, и если он найден, то выполняется его возврат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
