B + tree implementation, * * vs *

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 становится классом дескриптора, который указывает на эти отображаемые узлы данных и синтезирует такие вещи, как предыдущие и следующие указатели, путем чтения братьев и сестер, когда он спускается по дереву.

Это может выглядеть примерно следующее:

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++).