Алгоритмы - построение и анализ (1021735), страница 106
Текст из файла (страница 106)
В типичном приложении, использующем В-деревья, количество обрабатываемых данных достаточно велико, и все они не могут одновременно разместиться в оперативной памяти. Алгоритмы работы с В-деревьями копируют в оперативную память с диска только некоторые выбранные страницы, необходимые для работы, и вновь записывают на диск те из них, которые были изменены в процессе работы.
Алгоритмы работы с В-деревьями сконструированы таким образом, чтобы в любой момент времени обходиться только некоторым постоянным количеством страниц в основной памяти, так что ее объем не ограничивает размер В- деревьев, с которыми могут работать алгоритмы. В нашем псевдокоде мы моделируем дисковые операции следующим образом.
Пусть х — указатель на объект. Если объект находится в оперативной памяти компьютера, то мы обращаемся к его полям обычным способом — например, йеу [х]. Если же обьект, к которому мы обращаемся посредством х, находится на диске, то мы должны выполнить операцию Р1зк Кель(х) для чтения объекта х в оперативную память перед тем, как будем обращаться к его полям. (Считаем, что если объект х уже находится в оперативной памяти, то операция Р[зк КеАп(х) не требует обращения к диску.) Аналогично, для сохранения любых изменений в полях объекта х выполняется операция 01зк %к~те(х). Таким образом, типичный шаблон работы с объектом х имеет следующий вид: х +- указатель на некоторый объект 0!зк КеА0(х) Операции, обращающиеся и/или изменяющие поля х Рвк %иге(х) [> Не требуется, если поля х не изменялись Прочие операции, не изменяющие поля х Глава 18.
В-деревья 519 лзю* П '„!000 Г!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', ! 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
