Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 107
Текст из файла (страница 107)
ством (1,2,...,и]. Фредман (РтесЬпап) и Виллард (ЪЧ11!ап1) [99] предло. жили использовать деревья сяияиий (1пз)оп тгеез), которые были первыми структурами данных, обеспечивавшие повышение скорости словарных операций за счет ограничения пространства целыми числами. Они показала, как можно реализовать эти операции, чтобы их время работы составляло 0 (1бтт/1Е1бтт). Ряд других структур данных, включая экспонеяциаяьние деревья поиска (ехропепйа1 зеагсЫгеез) [16], также обеспечивают улучшение всех (или некоторых) словарных операций и упоминаются в заключительных замечаниях в некоторых главах книги. ° Динамические графы (т[упаппс агарЬ) поддерживают различные запросы, позволяя структуре графа изменяться в процессе операций добавления нля удаления вершин или ребер.
Примеры поддерживаемых запросов включают связи вершин [144], связи ребер, минимальные связуюшие деревья [143], двусвязность и транзитивное замыкание [142]. В заключительных замечаниях к различным главам данной книги упоминают. ся, помимо описанных, некоторые другие структуры данных. ГЛАВА 18 В-деревья В-деревья представляют собой сбалансированные деревья поиска, созданные специально для эффективной работы с дисковой памятью (и другими типами вторичной памяти с непосредственным доступом).
В-деревья похожи на красно- черные деревья (см. главу 13), но отличаются более высокой оптимизацией дисковых операций ввода-вывода. Многие СУБД используют для хранения информации именно В-деревья (или их разновидности). В-деревья отличаются от красно-черных деревьев тем, что узлы В-дерева могут иметь много дочерних узлов — до тысяч, так что степень ветвления В-дерева может быть очень большой (хотя обычно она определяется характеристиками используемых дисков).
В-деревья схожи с красно-черными деревьями в том, что все В-деревья с и узлами имеют высоту О (18п), хотя само значение высоты В- дерева существенно меньше, чем у красно-черного дерева за счет более сильного ветвления. Таким образом, В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время О (18п). В-деревья представляют собой естественное обобщение бинарных деревьев поиска. На рис. 18.1 показан пример простого В-дерева.
Если внутренний узел В- дерева содержит п [х] ключей, то у него п [х] + 1 дочерних узлов. Ключи в узле х используются как разделители диапазона ключей, с которыми имеет дело данный узел, на п [х] + 1 поддиапазонов, каждый из которых относится к одному из дочерних узлов х. При поиске ключа в В-дереве мы выбираем один из п [х] + + 1 дочерних узлов путем сравнения искомого значения с и [к] ключами узла х. Структура листьев В-дерева отличается от структуры внутренних узлов; мы рассмотрим эти отличия в разделе 18.1. Часть Ч. Сложные структуры данньк 516 юн (7 Рис. 18.1. В-дерево с согласными английского алфавита в качестве ключей В разделе 18.1 приведено точное определение В-деревьев и доказан логарнф. мический рост высоты В-дерева в зависимости от количества его узлов.
В разделе 18.2 описаны процессы поиска в В-дереве и вставки элемента в В-дерево, а в разделе 18.З вЂ” процесс удаления. Однако перед тем как приступить к работе с В- деревьями, давайте выясним, почему структуры данных, созданные для работы с дисковой памятью, так отличаются от структур, предназначающихся для работы с оперативной памятью. Структуры данных во вторичной памяти Имеется несколько видов используемой компьютером памяти. Основная, иля олеративиая, памятмь (рпшагу, шаш гпепюгу) представляет собой специализированные микросхемы и обладает более высоким быстродействием и существенно более высокой ценой, чем магнитные носители, такие как магнитные диски иля ленты. Большинство компьютеров, помимо первичной памяти„оснащены вторичной памятью (зесопдагу зтогайе) на базе магнитных дисков.
Цена такой памяти на пару порядков ниже, чем первичной, а ее суммарный обьем в типичной вычислительной системе на те же пару порядков превышает обьем первичной памяти. На рис. 18.2а показан типичный дисковый накопитель, состоящий из нескольких дисков (р!ацегз), вращающихся с постоянной скоростью на общем итпинделе (зр1пд!е). Поверхность каждого диска покрыта магнитным материалом.
Каждый диск читается и записывается при помощи магнитной головки (леад), расположенной на специальном рычаге. Все рычаги с головками собраны в единый пакет, который позволяет перемещать головки вдоль радиуса по направлению к шпинделю или от него к краю дисков. Когда головки находятся в зафиксированном состоянии, поверхность, проходящая под ними при вращении дисков, называется дорожкой (пася).
Поскольку головки оказываются выровнены по вертикали благодаря общей системе рычагов, так что обращение к набору дорожек (называющемуся милимдрам (су!шдег) и показанному на рис. 18.2б) выполняется одновременно. Глава 18. В-деревья 517 Шлввавлв диск --во доосскка Головка .' всолвяалаовсв доро ккв, авлв; до Рне. 18.2.
Типичный дисковый накопитель Хотя диски существенно дешевле оперативной памяти и имеют высокую емвэсть, они гораздо, гораздо медленнее оперативной памяти. Механическое движение головки относительно диска определяется двумя компонентами — перемещением головки по радиусу и вращением дисков.
Когда писались эти строки, типичная скорость вращения дисков составляла 5400 — 15000 оборотов в минуту (~рш), с наиболее распространенной скоростью 7200 грш. Хотя такая скорость может показаться очень большой, один оборот требует примерно 8.33 мс, что почти на 5 порядков превышает время обращения к оперативной памяти (которое составляет примерно 100 нс). Другими словами, пока мы ждем оборота диска, чтобы считать необходимые нам данные, из оперативной памяти мы могли бы получить зти данные почти 100000 раз! В среднем приходится ждать только половину оборота диска, ио это практически ничего не меняет. Радиальное перемещение головок тоже требует времени. Одним словом, когда писались эти строки, наиболее распространенное время доступа к дисковой памяти составляло от 3 до 9 миллисекунд.
Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам„хранящимся на диске. Информация разделяется на несколько страныц (райез) одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра, и каждая операция чтения или записи работает сразу с несколькими страницами. Типичный размер страницы — от 2" до 2ы байтов. После того как головка позиционирована на нужную 518 Часть Ч. Сложные структуры данных дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, операции чтения и записи выполняются очень быстро.
Зачастую обработка прочитанной информации занимает меньше времени, чем ее поиск и чтение с диска. По этой причине в данной главе мы отдельно рассматриваем два компонента времени работы алгоритма: ° количество обращений к диску; ° время вычислений (процессорное время). Количество обращений к диску измеряется в терминах количества страниц информации, которое должно быть считано с диска или записано на него. Заметим, что время обращения к диску не является постоянной величиной, поскольку зависит от расстояния между текущей дорожкой и дорожкой с интересующей нас информацией, а также текущего угла поворота диска.
Мы будем игнорировать это обстоятельство и в качестве первого приближения времени, необходимого для обращения к диску, будем использовать просто количество считываемых иля записываемых страниц. В типичном приложении, использующем В-деревья, количество обрабатываемых данных достаточно велико, и все они не могут одновременно разместиться в оперативной памяти. Алгоритмы работы с В-деревьями копируют в оперативную память с диска только некоторые выбранные страницы, необходимые для работы, и вновь записывают на диск те из них, которые были изменены в процессе работы.
Алгоритмы работы с В-деревьями сконструированы таким образом, чтобы в любой момент времени обходиться только некоторым постоянным количеством страниц в основной памяти, так что ее объем не ограничивает размер В- деревьев, с которыми могут работать алгоритмы. В нашем псевдокоде мы моделируем дисковые операции следующим образом. Пусть х — указатель на объект.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
