B + дерево реализации, * * против *

Question

Я пишу дерево B + по разным причинам и пришел сюда, чтобы задать вопрос о реализации его узлов. Мои узлы в настоящее время выглядят так:

struct BPlusNode
{
public:
    //holds the list of keys
    keyType **keys;
    //stores the number of slots used
    size_t size;
    //holds the array of pointers to lower nodes NULL if this is a leaf node
    BPlusNode **children;
    //holds the pointer to the next load to the 'left'
    BPlusNode *next;
    //Data page pointers NULL if this is a branch node
    Bucket **pages;
};

Как видите, моя текущая реализация использует * * в том месте, где мне интересно, стоит ли мне использовать * * или *.

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

С **

someFunction(BPlusNode* currNode)
{
    ......
    someFunction(currNode->children[ChildIndex]);
}

с *

someFunction(BPlusNode* currNode)
{
    ......
    someFunction((currNode->children) + ChildIndex);
}

Я вижу, что есть дополнительное считывание памяти для получения нужного указателя в версии * *, но версия * * также проще для меня (она более близко соответствует тому, как я вижу нарисованные диаграммы). в «Искусстве компьютерного программирования» и в википедии).

У кого-нибудь есть мысли так или иначе? Предложения по третьему варианту? Доказательство того, почему одно превосходит другое? и т.д.

Edit:
Я мог бы опубликовать это как ответ ниже, но я только что понял, что со схемой * * мне не нужно копировать все содержимое каждого подузла или сегмента, если я хочу вставить один в середину массива (т.е. изменить размер массива) , Если при перераспределении массива имеется 20 подузлов для схемы *, мне потребуется скопировать 20 * байтов sizeof (BPlusNode), в отличие от 20 * байтов sizeof (BPlusNode *) для схемы * *.

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

Answer 1

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

Ваша структура BPlusNode становится классом-дескриптором, который указывает на эти сопоставленные узлы данных и синтезирует такие вещи, как prev и next-указатели, читая братьев и сестер по мере спуска по дереву.

Это может выглядеть примерно так:

enum BPlusNodeType {
    LEAF, BRANCH
};

struct BPlusNodeData {
    static const size_t max_size = 511; // Try to fit into 4K? 8K?
    uint16_t size;
    uint16_t type;
    keyType key[max_size];
    union {
        Bucket* data[max_size];
        BPlusNodeData* children[max_size];
    };
};

Answer 2

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

someFunction((currNode->children) + ChildIndex);

больно, вы можете переписать его как

someFunction(&currNode->children[ChildIndex]);

, который я считаю более понятным.

Answer 3

Вам лучше использовать STL 'vector<keyType *> keys' и 'vector<BPlusNode *> children' и т. Д.?

Это может быть слишком упрощенно, но у меня сложилось впечатление, что двойное косвенное обращение не часто требуется в C ++ (и не так часто в C, хотя чаще, чем в C ++).