Поиск в сбалансированном дереве

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

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

Рис.1. Полностью сбалансированное индексное дерево.

Дата добавления: 2014-01-11