Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 115
Текст из файла (страница 115)
Информация разделяется на несколько слгралил (райеб) одинаювого размера, которые хранятся последовательно одна за другой в пределах одной дорожки, и каждая операция чтения или записи работает с одной или несколькими страницами. Для типичного диска размер страницы может составлять 2г1-2г4 байт. После того как головка позиционируется на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, операции чтения и записи выполняются очень быстро. Зачастую обработка прочитанной информации длится меньше времени, чем ее поиск и чтение с диска. По этой причине в данной главе мы отдельно рассматриваем два компонента времени работы алгоритма: количество обращений к диску; время вычислений (процессорное время).
Количество обращений к диску измеряется в количествах страниц информации, юторое должно быть считано с диска или записано на него. Заметим, что время обращения к диску не является постоянной величиной, поскольку зависит от расстояния между текущей дорожкой и дорожкой с интересующей нас информацией, а также от текущего угла поворота диска.
Мы будем игнорировать это обстоятельство и в качестве первого приближения времени, необходимого для 'На момент написаниа «инги на потребительским рынок стали акгиано выходить таердогельные ншюпнтели. Хстл они и быстрее дисюных, они отличаниел более аысокой стоимостью а пересчете на гигабайт н меньшей емносгью, чем традипионные магнитные диски. Часть К Слалсиые структуры даииык обращения к диску, будем использовать просто количество считываемых или записываемых страниц.
В типичном приложении, использующем В-деревья, количество обрабатываемых данных так велико, что все они не могут одновременно разместиться в оперативной памяти. Алгоритмы работы с В-деревьями копируют в оперативную память с диска толью некоторые выбранные страницы, необходимые для работы, и вновь записывают на диск те нз ннх, которые были изменены в процессе работы. Алгоритмы работы с В-деревьями сконструированы таким образом, чтобы в любой момент времени обходиться только некоторым постоянным количеством страниц в основной памяти, так что ее объем не ограничивает размер В-деревьев, с которыми могут работать алгоритмы. В нашем псевдокоде мы моделируем дисковые операции следующим образом. Пусть х — указатель на объект. Если объект находится в оперативной памяти компьютера, то мы обращаемся к его атрибугам обычным способом, например как к к.йеу.
Если же объект, к которому мы обращаемся посредством х, находится на диске, то мы должны выполнить операцию Р1$к-кеАц(х) для чтения объекта х в оперативную память перед тем, как будем обращаться к его полям. (Считаем, что если объект х уже находится в оперативной памяти, то операция Р1ЕК-КЕАгэ(х) не требует обращения к диску.) Аналогично для сохранения любых изменений в полях объекта х выполняется операция Р1зк-%к1те(х). Таким образом, типичный шаблон работы с объектом х имеет следующий вид.
х = а ро)пгег го зогпе оЬ)есг Р1ЕК-КЕАЮ(Х) Операции, обращающиеся к атрибутам х и!илн изменяющие их 01зк-%к1те(х) // Не выполняется, если никакие // атрибуты х не были изменены Прочие операции, обращающиеся к атрибутам х, но не изменяющие их Система в состоянии поддерживать в процессе работы в оперативной памяти толью некоторое ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит, в первую очередь, от количества выполняемых операций с диском Р1ЕК-КЕАП и Р1ЗК-%К1тЕ, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации.
Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы. Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между 50 и 2000, в зависимости от размера ключа относительно размера страницы.
Большая степень ветвления резко снижает как высоту дерева, 525 Глава йй Л-деревьв Т. пюг 1 узел, 1000 й 1001 узел, 1001000 ключей 1002001 узел, 1 002001 000 ключей Рис. 1йЗ. В-дерево высотой 2, содерлщщсе более миллиарда ключей. В кюкдом узле к показан атрибут х. н, количество ключей в х. Кюкдый внутренний узел и лист содержат 1000 ключей. Данное В-дерево имеет 1001 узел иа глубине ! и более миллиона листьев на глубине 2. так и количеспю обращений к диску для поиска ключа. На рис. 18.3 показано В-дерево, высота которого равна 2, а степень ветвления — 1001; такое дерево может хранить более миллиарда ключей. При зтом, поскольку корневой узел может храниться в оперативной памяти постоянно, для поиска ключа в зтом дереве требуется максимум два обращения к диску.
18.1. Определение В-деревьев Для простоты предположим, как и в случае бинарных деревьев поиска и красно-черных деревьев, что сопутствующая информация, связанная с ключом, хранится в узле вместе с юиочом. На практике вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Псевдокод в данной главе неявно подразумевает, что при перемещении ключа от одного узла к другому вместе с ним перемещается и сопутствующая информация или указатель на нее.
В распространенном варианте В-дерева, который называется В+-деревом, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом, удается получить максимально возможную степень ветвления во внутренних узлах. В-дерево Т представляет собой корневое дерево (корень которого Т. гоо1), обладающее следующими свойствами. 1. Каждый узел х содержит следующие атрибуты: а) х. и, количество ключей„хранящихся в настояпщй момент в узле х; б) собственно х. п ключей, х.
)се1г„х. Мерз,..., х. кеу „, хранящихся в неубывающем порядке, так что х. кеу! < х. не!12 « х. кер в) булево значение х.1еаУ, равное ткиб, если х представляет собой лист, и ря!.БЕ, если х является внутренним узлом. Часта и Сложные структуры данказт 526 2. Кроме того, каждый внутренний узел х содержит х, и+1 указателей х.см х. сз, ..., х.с „ез на дочерние узлы. У листьев дочерних узлов нет, так что значения их атрибутов с, не определены. 3.
Ключи х, зсеу, разделяют поддиапазоны ключей, хранящихся в поддеревьях: если Йй является произвольным ключом, хранящимся в поддереве с корнем х.с„ то 5су ( х.йеуз ( )сз ( х.1сеуз ( .. ( х.йеу, „ ( (с~ „.ез 4. Все листья расположены на одной и той же глубине, которая равна высоте дерева 5з. 5. Имеются нижняя и верхняя границы количества ключей, которые могут содержаться в узле.
Эти границы могут быть выражены с помощью одного фиксированного целого числа с > 2, называемого минимальной степенью (пппппшп дейтее) В-дерева: а) каждый узел, кроме корневого, должен содержать как минимум г — 1 ключей, Каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум с дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ; б) каждый узел содержит не более 2г — 1 ключей.
Таким образом, внутренний узел имеет не более 2г дочерних узлов. Мы говорим, что узел заполнен (йуН), если он содержит ровно 2г — 1 ключейз. Простейшее В-дерево получается при г = 2. При этом каждый внутренний узел может иметь 2, 3 или 4 дочерних узла, и мы получаем так называемое 2-3-4- дереео (2-3-4 пес).
Однако обычно на практике используются гораздо большие значения 1. Высота В-дерева Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае. Теорема 1й.1 Если и > 1, то для любого В-дерева Т с и ключами, высотой Ь и минимальной степенью г > 2 и+1 тз ( 1обз 2 злрутой распространенный вариант В-дерева под названием В -дерпт требует, чтобы каждый внутренний узел быа заповнен как минимум на две трети, а не напоковину, как в евучае В-дерева.
Глава ГД В-деревьв Г. плл ~1 ~ачаСс, аЪ'. ~'1'-:1.,;! ....з-.1 ~ Н~„'"",У~' У~:(зЯ~ (азз)М "'З;т1,~... '~;-З ~ Гззз'.1 'З;-,. 1„,* (1-,1;! (Ф ~-"; ('~,.''-;,1'", "(Л; —:'1 ~ Глубнна Коанчсссю узлов о Рнс. 18.4. Н-дерево высотой 1, содерлсплее мнннмально аозмоююе количество ключей. В кюкдом узле х показано значенне х.п. и > 1+ (1 1) ~у у211-1 = 1+ 2(Ф вЂ” 1) = 2с~ — 1 Простейшее преобразование дает нам неравенспю 1ь ( (и + 1)(2. Теорема дока- зывается путем логарифмирования по основанию 1 обеих частей зтого неравен- ства. Здесь мы видим преимущества В-деревьев над красно-черными деревьями. Хотя высота деревьев растет как 0()8 и) в обоих случаях (вспомним, что 1 — константа), в случае В-деревьев основание логарифмов имеет гораздо большее значение. Таким обраюм, В-деревья требуют исследования примерно в 181 раз меньшего количества узлов по сравнению с красно-черными деревьями.
Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным. Упражнения 1е.1.1 Почему минимальная степень В-дерева не может быть Ф = 12 Доклзалзельслзва Корень В-дерева Т содержит как минимум один ключ, а все остальные узлы — как минимум по Ф вЂ” 1 ключей. Таким образом, у В-дерева Т, глубина которого равна Ь, имеется как минимум 2 узла на глубине 1, как минимум 21 узлов на глубине 2, как минимум 2сз узлов на глубине 3 и так до глубины 6, на юзторой имеется как минимум 21Ь ' узлов (пример такого дерева, высота мзторого равна 3, показан на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
