11. Особенности крупномасштабных деревьев
 

Бинарные деревья находят широкое применение, однако есть области ин-форматики, где невозможно ограничиваться только бинарными деревьями. Одной из таких областей является управление данными, размещенными на ВЗУ. Для этого формируются и используются крупномасштабные деревья поиска, в которых необходимы и включения, и удаления элементов. Если идеально сбалансированное бинарное дерево включает 1млн элементов, то для двоичного поиска элемента потребуется в среднем около 20 шагов (Iog₂10⁶) поиска. Поскольку дерево находится на ВЗУ, то каждый шаг включает обращение к ВЗУ для чтения, и желательна такая организация хранения данных, которая потребует меньше обращений.

Эту проблему можно было бы решить следующим образом. Бинарное дерево поиска, размещенное на ВЗУ, логически разделяется на страницы. Каждая страница включает одно поддерево с несколькими узлами (обычно десятки и сотни узлов). На ВЗУ страница размещается в блоке памяти, который считывается с устройства или записывается на него за одно обращение. Следовательно, резко сокращается количество обращений к ВЗУ. Дальнейший поиск нужного узла в пределах страницы осуществляется в оперативной памяти. Таким образом, общее число обращений к уздам дерева в процессе поиска остается прежним, но их большая часть осуществляется в оперативной памяти, поэтому время поиска значи-тельно сокращается. Схема разбиения на страницы рассмотрим на примере.

Если теперь в том же дереве с 1 млн элементов каждая страница будет включать поддерево с 100 узла ми, то средняя длина поиска будет log₁₀₀10⁶ = 3 обращениям к страницам при условии, что дерево «случайное» и потому почти сбалансировано.

Однако в наихудшем случае, когда дерево сильно перекошено число обращений может стать чрезмерно большим, а многие блоки будут заполнены только частично. Поэтому в случае крупномасштабных деревьев почти всегда требуется управление их ростом, что при большом количестве узлов вызывает затруднения.

Реальное воплощение нашла другая схема реализации крупнономасштабных деревьев, так называемые сильно ветвящиеся деревья, у которых каждый узел содержит несколько (>2) элементов данных (ключей) и имеет несколько потомков. Один узел (страница) такого дерева размещается в одном блоке внешней памяти и считывается в оперативную память за один прием. Очевидно что и в этом случае необходимо поддерживать сбалансированность дерева.