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*)字节。

另一方面，我突然想到，由于我执行的所有插入和页面拆分都是预先完成的，也许执行它们时效率的提高是不必要的，而且在搜索中* 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++更多)。