Как с учетом заданного набора ключей изменить порядок клавиш так, чтобы минимальное количество узлов использовалось при вставке в B-Tree?

Ответ 1

Алгоритм ниже должен работать для B-деревьев с минимальным количеством ключей в node= d и maximum = 2 * d. Предположим, что он может быть обобщен для ключей 2 * d + 1 max, если известен способ выбора медианного.

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

Метод основан на идее положить ключи в любой не полный лист или если все листы заполнены, чтобы поставить ключ под наименьшим не полным node.

Точнее, дерево, генерируемое предложенным алгоритмом, удовлетворяет следующим требованиям: Он имеет минимально возможную высоту; На каждом уровне он имеет не более двух нечетных узлов. (Это всегда два самых правильных узла.)

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

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

Вот почти рабочий (псевдо) код, массив нужно сортировать:

PushArray(BTree bTree, int d, key[] Array)
{
    List<int> counters = new List<int>{0};
    //skip list will contain numbers of nodes to skip 
    //after filling node of some order in half
    List<int> skip  = new List<int>();
    List<Pair<int,int>> skipList = List<Pair<int,int>>();

    int i = -1;
    while(true)
    {     
       int order = 0;
       while(counters[order] == d) order += 1;
       for(int j = order - 1; j >= 0; j--) counters[j] = 0;

       if (counters.Lenght <= order + 1) counters.Add(0);
       counters[order] += 1;

       if (skip.Count <= order)
              skip.Add(i + 2);    
       if (order > 0)
           skipList.Add({i,order}); //list of skipped parts that will be needed later
       i += skip[order];

       if (i > N) break;

       bTree.Push(Array[i]);
    }

    //now we need to add all skipped keys in correct order
    foreach(Pair<int,int> p in skipList)
    {
        for(int i = p.2; i > 0; i--)
            PushArray(bTree, d, Array.SubArray(p.1 + skip[i - 1], skip[i] -1))
    }
}

Пример:

Вот как номера и соответствующие счетчики должны быть расположены для d = 2, а сначала проходят через массив. Я пометил клавиши, которые вперёд вошли в B-Tree во время первого прохода (до цикла с рекурсией) с "o" и пропустили "x".

                                                              24
        4         9             14             19                            29 
0 1 2 3   5 6 7 8   10 11 12 13    15 16 17 18    20 21 22 23    25 26 27 28    30 ...
o o x x o o o x x o  o  o  x  x  x  x  x  x  x  x  x  x  x  x  o  o  o  x  x  o  o ...
1 2     0 1 2     0  1  2                                      0  1  2        0  1 ...
0 0     1 1 1     2  2  2                                      0  0  0        1  1 ...
0 0     0 0 0     0  0  0                                      1  1  1        1  1 ...
skip[0] = 1 
skip[1] = 3 
skip[2] = 13

Поскольку мы не перебираем пропущенные ключи, у нас есть O (n) временная сложность без добавления к самому B-Tree и для отсортированного массива;

В этой форме может быть непонятно, как это работает, когда не хватает клавиш для заполнения второй половины node после пропущенного блока, но мы также можем избежать пропусков всех клавиш [order], если общая длина массива меньше ~ я + 2 * пропустить [порядок] и пропустить для пропущенных [порядок - 1] ключи вместо этой строки после смены счетчиков, но до изменения переменной я можно добавить:

while(order > 0 && i + 2*skip[order] > N) --order;

это будет правильная причина, если общее количество клавиш на текущем уровне меньше или равно 3 * d, они все равно расщепляются правильно, если добавить их в исходном порядке. Это приведет к несколько иной перестановке ключей между двумя последними узлами на некоторых уровнях, но не нарушит каких-либо описанных требований, и, возможно, это упростит понимание поведения.

Может быть разумно найти какую-то анимацию и посмотреть, как она работает, вот последовательность, которая должна быть сгенерирована в диапазоне 0..29: 0 1 4 5 6 9 10 11 24 25 26 29/конец первого прохода /2 3 7 8 14 15 16 19 20 21 12 13 17 18 22 23 27 28

Ответ 2

В приведенном ниже алгоритме делается попытка подготовить порядок ключей, чтобы вам не нужно было иметь силу или даже знать о процедуре вставки. Единственное предположение состоит в том, что переполненные узлы дерева либо расщепляются посередине, либо в позиции последнего вставленного элемента, в противном случае B-дерево можно рассматривать как черный ящик.

Хитрость заключается в том, что триггер node разделяется контролируемым образом. Сначала вы заполняете node точно, левую половину с ключами, которые вместе, и правую половину с другим диапазоном ключей, которые принадлежат друг другу. Наконец, вы вставляете ключ, который находится между этими двумя диапазонами, но не принадлежит ни к одному из них; два поддиапазона разделяются на отдельные узлы, а последний вставленный ключ заканчивается в родительском node. После разделения таким образом вы можете заполнить оставшуюся часть обоих дочерних узлов, чтобы сделать дерево максимально компактным. Это также работает для родительских узлов с более чем двумя дочерними узлами, просто повторите трюк с одним из детей до тех пор, пока не будет создано требуемое количество дочерних узлов. Ниже я использую концептуально самый правый дочерний узел как "разделительную землю" (шаги 5 и 6.1).

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

Подразумеваемое дерево T с максимальным коэффициентом ветвления M.

Верхняя процедура с ключами длины N:

• Сортировка клавиш.
• Установить минимальное дерево-высоту для ceil (log (N + 1)/log (M)).
• Вызвать вставку-кусок с помощью кнопок chunk = и H = минимальная высота дерева.

Процедура insert-chunk с куском длины L, высота поддерева H:

• Если H равно 1:
  • Вставьте все ключи из куска в T
  • Немедленно вернуться.
• Установите идеальный размер подъязыка S в pow (M, H - 1).
• Задайте количество поддеревьев T to ceil ((L + 1)/S).
• Установите фактический размер подъязыка S 'для ограничения ((L + 1)/T).
• Рекурсивно вызовите вставку с куском '= последний этаж ((S - 1)/2) ключей блока и H' = H - 1.
• Для каждого из подъязыков Ceil (L/S ') (размера S'), за исключением последнего с индексом I:
  • Рекурсивно вызывать вставку-кусок с куском '= первые клавиши ceil ((S-1)/2) подчинки я и H' = H-1.
  • Вставьте последний ключ subchunk я в T (эта вставка целенаправленно запускает раскол).
  • Рекурсивно вызовите вставку с куском '= оставшиеся ключи подклучки я (если есть) и H' = H - 1.
• Рекурсивно вызовите вставку с куском '= оставшиеся ключи последней подточки и H' = H - 1.

Обратите внимание, что рекурсивная процедура вызывается дважды для каждого поддерева; это нормально, потому что первый вызов всегда создает идеально заполненную половину поддерева.

Ответ 3

Вот путь, который приведет к минимальной высоте в любом BST (включая дерево b): -

• сортировать массив
• Скажем, у вас есть ключ m в дереве b
• Разделить массив рекурсивно в m + 1 равных частях, используя m ключей в родительском.
• построить дочернее дерево из n/(m + 1) отсортированных ключей с помощью рекурсии.

пример: -

m = 2 array = [1 2 3 4 5 6 7 8 9 10]

divide array into three parts :-

root = [4,8]

recursively solve :-

child1 = [1 2 3]

root1 = [2]

left1 = [1]

right1 = [3]

similarly for all childs solve recursively.

Ответ 4

Так это об оптимизации процедуры создания или оптимизации дерева?

Вы можете четко создать максимально эффективное B-Tree, сначала создав полное сбалансированное двоичное дерево, а затем сжимающие узлы.

На любом уровне в двоичном дереве пробел в числах между двумя узлами содержит все числа между этими двумя значениями по определению двоичного дерева, и это более или менее определение B-Tree. Вы просто начинаете сжимать двоичные деления дерева на узлы B-Tree. Поскольку бинарное дерево сбалансировано по построению, промежутки между узлами на одном уровне всегда содержат одинаковое количество узлов (при условии, что дерево заполнено). Таким образом, построенная таким образом БТР гарантируется сбалансированным.

На практике это, вероятно, довольно медленный способ создания BTree, но он, безусловно, соответствует вашим критериям построения оптимального B-Tree, и литература по созданию сбалансированных двоичных деревьев является всеобъемлющей.

=====================================

В вашем случае, где вы могли бы снять "лучше" над построенной оптимальной версией, рассмотрели ли вы просто изменение количества дочерних узлов? Ваша диаграмма выглядит как классическое 2-3 дерева, но вполне возможно иметь 3-4 дерева или 3-5 деревьев, что означает, что каждый node будет иметь как минимум трех детей.

Ответ 5

Ваш вопрос о оптимизации btree. Маловероятно, что вы делаете это просто для удовольствия. Поэтому я могу только предположить, что вы хотели бы оптимизировать доступ к данным - возможно, как часть программирования базы данных или что-то вроде этого. Вы написали: "При поиске в BTree он вызывается по требованию с диска в память", а это значит, что у вас либо недостаточно памяти для кэширования, либо у вас есть политика для использования как можно меньше памяти. В любом случае это может быть основной причиной того, почему любой ответ на ваш вопрос не будет удовлетворять. Позвольте мне объяснить, почему.

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

Как только вы захотите принять хотя бы некоторое использование памяти, вы можете переосмыслить свое утверждение "При поиске в BTree оно вызывается по требованию с диска в память", что создает пространство для балансировки между оптимизацией чтения и записи. Максимальное оптимизированное BTREE - максимальная оптимизация записи. В большинстве сценариев доступа к данным я знаю, что вы получаете запись при любых 10-100 чтениях. Это означает, что оптимизация максимальной записи может привести к низкой производительности с точки зрения оптимизации доступа к данным. Вот почему базы данных принимают циклы реструктуризации, ключевые космические отходы, неуравновешенные btrees и тому подобное...