Ключи концевых узлов (листьев) упорядочены внутри дерева, что позволяет уменьшить время сканирования, поскольку этот процесс выполняется не последовательно. Листья связаны между собой с помощью указателей, ссылающихся друг на друга.
Примечание
Ключами служат имена файлов. Нижняя строка на прямоугольниках содержит ключ для каждого файла в каталоге — это концевые узлы. Выше над ними расположены промежуточные узлы, ключи которых выбираются системой таким образом, чтобы ускорить поиск.
- Чтобы найти файл resolv.conf, начинаем анализ с корня дерева, сканируя его последовательно. Поскольку ключа, большего, чем resolv.conf не найдено, используем последний указатель.
- Переходим к другому промежуточному узлу. Повторяем поиск. После анализа ключей узла, становится ясно, что securetty больше, чем resolv.conf. Используем соседний указатель.
- Переходим к концевому узлу. Теперь выполняем анализ ключей в узле в порядке возрастания. Найдя, наконец, требуемый ключ, будем использовать соответствующий ему указатель на файл с именем resolv.conf.
