Поиск в узле дерева CSB+

Question

Я читаю газету, делаю сознание кэша B+-деревьев в основной памяти. В разделе 3.1.2 авторы описывают несколько подходов к поиску в узле дерева CSB+.

Основной подход заключается в простом выполнении бинарного поиска с использованием обычного цикла while.

Единый подход заключается в расширении кода, разворачивая цикл while в if-then-else операторы, предполагающие использование всех ключей.

Авторы приводят следующий пример, демонстрирующий развертывание поиска узла с количеством ключей до 9. Число в узле представляет позицию ключа, используемого в if тестовое задание

              4
            /   \
           2     6
          / \   / \
         1   3 5   8
                  / \
                 7   9

Затем следует запутанная часть:

Если бы на самом деле присутствовало только 5 ключей, мы могли бы пройти по этому дереву точно с 3 сравнениями. С другой стороны, для развертывания, которое помещает самое глубокое поддерево слева вместо правого, потребуется 4 сравнения в некоторых ветвях.

Так зачем ему нужно больше сравнений в следующем дереве:

              6
            /   \
           4     8
          / \   / \
         2   5 7   9
        / \
       1   3

Более того,

если бы мы знали, что у нас всего пять действительных ключей, мы могли бы жестко закодировать дерево, которое в среднем использовало бы 2,67 сравнения, а не 3.

Как получается 2.67?

Любые советы будут оценены. Также была бы полезна ссылка, направляющая меня к знаниям по расширению кода.

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

Спасибо

Answer 1

Ключевым моментом здесь является следующая цитата из того же раздела:

мы дополняем все неиспользуемые ключи (keyList[nKeys..2d-1]) в узле с максимально возможным ключом

Также важно, что в дереве B+/CSB+ мы ищем не значения узлов, а интервалы между этими значениями. Набор возможных значений разделен на 5 ключей на 6 интервалов.

Поскольку большая часть правого поддерева заполнена максимально возможным ключом (L), нам нужно меньше сравнений, чем обычно:

              4
            /   \
           2     L
          / \   / \
         1   3 5   L
                  / \
                 L   L

Правый потомок корневого узла имеет максимально возможный ключ, нет необходимости проверять ни один узел справа от него. И точно 3 сравнения необходимы для каждого интервала:

interval   comparisons
up to 1    k>4, k>2, k>1
 1..2      k>4, k>2, k>1
 2..3      k>4, k>2, k>3
 3..4      k>4, k>2, k>3
 4..5      k>4, k>L, k>5
 5..L      k>4, k>L, k>5

Если мы поместим самое глубокое поддерево слева, у нас будет дерево, где непустые узлы расположены на один уровень глубже:

              L
            /   \
           4     L
          / \   / \
         2   5 L   L
        / \
       1   3

Поиск узла "1" в этом дереве требует сравнения ключа с 4 разными узлами: L, 4, 2 и 1.

Если мы знаем, что у нас есть только пять допустимых ключей, у нас есть следующее дерево:

              2
            /   \
           1     4
                / \
               3   5

Здесь мы можем организовать сравнение таким образом, чтобы в среднем было 2,67 сравнения:

interval   comparisons
up to 1    k>2, k>1
1..2       k>2, k>1
2..3       k>2, k>4, k>3
3..4       k>2, k>4, k>3
4..5       k>2, k>4, k>5
5..L       k>2, k>4, k>5

"Расширение кода" не является широко используемым термином, поэтому я не могу дать вам наиболее релевантную ссылку. Я думаю, это не очень отличается от "разматывания петли".