Какова структура узла для этой спецификации B-Tree?

Question

Я пытаюсь создать B-дерево со следующими свойствами:

Каждый узел х содержит следующие атрибуты:

1. хп количество ключей, присутствующих в узле х
2. x.key1, x.key2, ..... x.keyx.n - это ключи, присутствующие в узле
3. x.c1, x.c2, ......... x.cx.n, x.cx .n + 1 являются указателями на дочерние узлы
4. x.leaf - это логическая переменная, которая показывает, является ли узел листовым узлом или нет.

На основе этой спецификации, как бы я реализовать структуру узла:

struct Node{ 
    ...? 
}   

Answer 1

Смысловая структура при рисовании это что-то вроде этого.

 a  b  c  d 
    / |  |  |  \ 
    la  bab bbc bcd gd 

    la = less than a 
    bab = between a and b 
    bbc = between b and c 
    bcd = between c and d 
    gd = greater than d 

Если есть больше указателей, чем элементов.

Таким образом, b-дерево порядка N имеет не более N детей. Таким образом, используя BTREE_ORDER в качестве этого значения, а также обеспечение BTREE_ORDER больше 1.

Структура наиболее эффективно осуществляется в

struct Node{ 
    size_t numNodes; 
    KEY_TYPE Key[BTREE_ORDER -1]; 
    struct Node * Children[BTREE_ORDER]; 
} 

Так что имеет место для BTREE_ORDER-1 ключей и BTREE_ORDER дочерних узлов. Агрегат соответствует коду и составляет

Children[0] Key[0] Children[1] Key[1] .... Key[numNodes - 2] Children[ numNodes - 1]