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

Примечание

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

  1. Чтобы найти файл resolv.conf, начинаем анализ с корня дерева, сканируя его последовательно. Поскольку ключа, большего, чем resolv.conf не найдено, используем последний указатель.
  2. Переходим к другому промежуточному узлу. Повторяем поиск. После анализа ключей узла, становится ясно, что securetty больше, чем resolv.conf. Используем соседний указатель.
  3. Переходим к концевому узлу. Теперь выполняем анализ ключей в узле в порядке возрастания. Найдя, наконец, требуемый ключ, будем использовать соответствующий ему указатель на файл с именем resolv.conf.

    Поделитесь материалом с коллегами и друзьями