В большинстве случаев индекс строится в виде многоуровневого дерева. Дерево из трех уровней, представленное на рис.1, является полностью сбалансированным, т.е. заняты все элементы всех узлов. При поиске сначала просматривается узел самого высокого уровня, который ссылается на узлы следующего уровня. Узел второго уровня ссылается на самый нижний уровень. Поиск каждого узла может производиться при помощи, например, блочного поиска.
Древовидная организация индекса, подобная изображенной на рис.1, требует больше памяти, чем одноуровневый индекс, поскольку наибольший (или наименьший) ключ каждого узла повторяется и в узле более высокого уровня. Но поиск в таком дереве может требовать меньшего числа испытаний, чем в большинстве других методов, и при этом сокращается число обращений к внешней памяти. Важно выбрать оптимальное число уровней и оптимальное число элементов в одном узле.
Рис.1. Полностью сбалансированное индексное дерево.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2025) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление