c++ - B+树实现，* * 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);
}

我可以看到在**版本中有一个额外的内存读取来产生所需的指针，但是**版本对我来说也更容易考虑(它更符合我看到的图表的方式在“计算机编程艺术”和维基百科上)。

有没有人有这样或那样的想法？对第三种选择的建议？证明为什么一个优于另一个？等等？

编辑:
我可能会在下面将其作为答案发布，但我刚刚意识到，使用 * * 方案我不需要复制每个子节点或存储桶的全部内容，如果我想将一个子节点或存储桶插入到数组的中间(即调整数组的大小) .如果在我重新分配数组时 * 方案有 20 个子节点，我将需要复制 20*sizeof(BPlusNode) 字节，而不是 * * 方案的 20*sizeof(BPlusNode*) 字节。

另一方面，我突然想到，由于我执行所有插入和页面拆分都是预先完成的，所以执行它们时提高效率可能是不必要的，而且 * 优于 * * 在搜索中的好处超过了它。

Answer 1

我会为键和指针数据定义另一个结构。我会 promise 使用固定大小的节点，这些节点应该与您的磁盘结构相匹配。这使得内存映射树变得容易得多。

您的 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];
    };
};