Внутренняя организация дерева с двоичным основанием

Внутренняя организация дерева с двоичным основанием

Внутренняя форма хранения дерева с двоичным основанием оптимизирована как с точки зрения производительности, так и занимаемого пространства. Первая базовая структура для дерева с двоичным основанием была создана инженером Филом Хо-вардом (Phil Howard) в 70-х годах. В его схеме правый и левый потомки тестового узла вместе с возможным общим текстом объединены в кластер. Такие кластеры располагались в памяти один за другим, и для ссылки на кластер использовалось его положение в цепочке. Это устраняло необходимость учета адресов для ссылки на следующий узел.

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

Чтобы найти следующий узел дерева, операция XOR выполняется над значением, хранящимся в текущем узле, и позицией предыдущего узла. Ясно, что значение, хранящееся в текущем узле, — результат XOR над позициями следующего и предыдущего узлов. Таким образом, чтобы вычислить местоположение следующего узла, нужно знать лишь текущее значение и позицию предыдущего узла. Предположим, что мы хотим пройти по дереву в обратном направлении. Выполнив операцию XOR над значением в текущем узле и позицией следующего узла, мы получаем позицию предыдущего узла. Таким образом, из любой точки дерева, зная предыдущую, текущую и следующие позиции, а также содержимое текущего узла, можно перемещаться вверх и вниз без ссылок. Для хранения нужных нам трех позиций годится простой стек.

Реализация дерева с двоичным основанием минимизирует число страничных ошибок путем разделения дерева на поддеревья. Формально, такую структуру следовало бы называть фрагментированным деревом с двоичным основанием. При переполнении страницы, выше по дереву выполняется разделение, и к индексу добавляются новые поддеревья.

Предположим, мы решили разделить дерево из нашего примера на рисунке 6.7. Разумно поместить на одну страницу все терминальные узлы от Baker до Peters вместе с их тестовыми узлами, а на вторую — терминальные узлы от Smith до Wu, а также один указывающий на них тестовый узел.

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

Другое преимущество фрагментирования — то, что, попав в процессе поиска на некоторую страницу памяти, содержащую фрагмент дерева, мы остаемся на ней на всех уровнях тестирования. Перед переходом на следующую страницу все тестовые узлы данной страницы на пути поиска будут просмотрены. Кроме того, поскольку для поиска в очень больших индексах требуется относительно немного проверок (вспомните, что при поиске в индексе из миллиона записей требуется, в среднем, только 20 проверок), то лишь в редких случаях придется затронуть более одной-двух страниц. В результате, данная схема обеспечивает наивысшую производительность по сравнению со всеми иными известными схемами индексации.