В-деревья

Лекция 9

Структуры данных.

СЛОЖНЫЕ СТРУКТУРЫ ДАННЫХ

• Динамические деревья (dynamic trees), разработанные Слитором (Sleator) и Таржаном (Tarjan) [281, 292], поддерживают лес из непересекающихся деревьев. Каждое ребро каждого дерева имеет некоторую стоимость, выраженную действительным числом. Динамические деревья поддерживают запросы поиска родителя, корня, стоимости ребра и минимальной стоимости ребра на пути от узла к корню. У деревьев могут удаляться ребра, может изменяться стоимость на пути от узла к корню, корень может связываться с другим деревом, а также делать узел корнем дерева, в котором он находится. Имеется реализация динамических деревьев, которая обеспечивает амортизированное время работы каждой операции, равное О (lgn); другая, более сложная реализация обеспечивает время работы О (lg n) в наихудшем случае.

• Расширяющиеся деревья (splay trees), также разработанные Слитором (Sleator) и Таржаном (Tarjan) [282, 292], представляют собой версию бинарных деревьев поиска, в которых операции поиска имеют амортизированное время работы О (lgn). Одно из применений расширяющихся деревьев — упрощение реализации динамических деревьев.

• Перманентные структуры (persistent data structures), которые обеспечивают возможность выполнения запроса о предшествующих версиях структуры данных, а иногда и их обновления. Соответствующие методы с малыми затратами времени и памяти были предложены в работе [82] Дрисколлом (Driscoll), Сарнаком (Sarnak), Слитором (Sleator) и Таржаном (Tarjan). В задаче 13-1 приведен простой пример перманентного динамического множества.

• Динамические графы (dynamic graph) поддерживают различные запросы, позволяя структуре графа изменяться в процессе операций добавления или удаления вершин или ребер. Примеры поддерживаемых запросов включают связи вершин [144], связи ребер, минимальные связующие деревья [143], двусвязность и транзитивное замыкание [142].

В-деревья

В-деревья представляют собой сбалансированные деревья поиска, разработанные специально для хранения информации на дисках. Поскольку дисковые операции существенно медленнее, чем работа с оперативной памятью, производительность В-деревьев определяется не только временем, необходимым для проведения вычислений, но и количеством необходимых дисковых операций. Для каждой операции с В-деревом количество обращений к диску растет с ростом высоты В-дерева, так что мы должны поддерживать ее невысокой.

В-деревья представляют собой сбалансированные деревья поиска, созданные специально для эффективной работы с дисковой памятью (и другими типами вторичной памяти с непосредственным доступом). В-деревья отличаются более высокой оптимизацией дисковых операций ввода-вывода. Многие СУБД используют для хранения информации именно В-деревья (или их разновидности).

В-деревья представляют собой естественное обобщение бинарных деревьев поиска. На рис. показан пример простого В-дерева. Если внутренний узел В дерева содержит n [х] ключей, то у него n [х] + 1 дочерних узлов. Ключи в узле х используются как разделители диапазона ключей, с которыми имеет дело данный узел, на n[х] + 1 поддиапазонов, каждый из которых относится к одному из дочерних узлов х. При поиске ключа в В-дереве мы выбираем один из n [х] + 1 дочерних узлов путем сравнения искомого значения с n [х] ключами узла х.

Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к внешней памяти выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц (pages) одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра, и каждая операция чтения или записи работает сразу с несколькими страницами.

Количество обращений к диску измеряется в терминах количества страниц информации, которое должно быть считано с диска или записано на него. Заметим, что время обращения к диску не является постоянной величиной, поскольку зависит от расстояния между текущей дорожкой и дорожкой с интересующей нас информацией, а также текущего угла поворота диска.

В типичном приложении, использующем В-деревья, количество обрабатываемых данных достаточно велико, и все они не могут одновременно разместиться в оперативной памяти. Алгоритмы работы с В-деревьями копируют в оперативную память с диска только некоторые выбранные страницы, необходимые для работы, и вновь записывают на диск те из них, которые были изменены в процессе работы. Алгоритмы работы с В-деревьями сконструированы таким образом, чтобы в любой момент времени обходиться только некоторым постоянным количеством страниц в основной памяти, так что ее объем не ограничивает размер Вдеревьев, с которыми могут работать алгоритмы.

Дисковые операции моделируем следующим образом.

Пусть х — указатель на объект. Если объект находится в оперативной памяти компьютера, то мы обращаемся к его полям обычным способом — например, key [x].

Если же объект, к которому мы обращаемся посредством х, находится на диске, то мы должны выполнить операцию Disk_Read(x) для чтения объекта х в оперативную память перед тем, как будем обращаться к его полям. (Считаем, что если объект х уже находится в оперативной памяти, то операция Disk_Read(х) не требует обращения к диску.) Аналогично, для сохранения любых изменений в полях объекта х выполняется операция Disk_Write(x). Таким образом, типичный шаблон работы с объектом х имеет следующий вид:

Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно.

Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций с диском Disk_Read и Disk_Write, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы.

Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между 50 и 2000, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. На рис. показано В-дерево высота которого равна 2, а степень ветвления — 1001; такое дерево может хранить более миллиарда ключей. При этом, поскольку корневой узел может храниться в оперативной памяти постоянно, для поиска ключа в этом дереве требуется максимум два обращения к диску!

Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте.

Теорема. Высота В-дерева Т с n>=1 узлами и минимальной степенью t>=2 не превышает log_t[(n + 1)/2].

Имеются нижняя и верхняя границы количества ключей, которые могут содержаться в узле. Эти границы могут быть выражены с помощью одного фиксированного целого числа t >= 2, называемого минимальной степенью (minimum degree) В-дерева.

Простейшее В-дерево получается при t = 2. При этом каждый внутренний узел может иметь 2, 3 или 4 дочерних узла, и мы получаем так называемое 2-3-4-дерево (2-3-4 tгее). Однако обычно на практике используются гораздо большие значения t.

Поиск в В-дереве очень похож на поиск в бинарном дереве поиска, но с тем отличием, что если в бинарном дереве поиска мы выбирали один из двух путей, то здесь предстоит сделать выбор из большего количества альтернатив, зависящего от того, сколько дочерних узлов имеется у текущего узла. Точнее, в каждом внутреннем узле х нам предстоит выбрать один из n[х] + 1 дочерних узлов.