binary-tree - B堆中的模式是什么？

Question

请帮助识别此 B 堆中的模式:

在正常的二叉堆中，我们总是使用以下条件:
left_child = 2*i,
right_child = 2*i+1
parent = i/2

但是这些条件只适用于前 2 个级别，我无法识别剩余的模式。请帮我。

Answer 1

您可以在 b-heap 中理解寻址作为经典的组合binary-tree寻址和 m-ary树寻址。
b 堆的基本思想是通过在使用另一个页面之前首先完全填充页面来减少访问(内存)页面的数量(参见图像中的蓝色框)。
因此，在计算元素的子/父索引时，可以先使用经典的二叉树寻址(索引相对于页面开始)，但必须检查结果索引在当前元素的页面中是否有效.如果是，那么你就完成了。如果不是，则必须查找当前元素的子页面或父页面，然后计算该页面中的偏移量。
对于页面寻址，您必须使用 m-ary树寻址，其中 m = page_size/2 - 因为每个页面都有 m 个子页面。
当然，b 堆布局细节可能会有变化。一个相对简单的方案是保留每个页面中的最后一个元素——以及所有页面中的第一个元素，但第一个元素——未使用。这基本上每页浪费 2 个元素槽，但简化了寻址。
示例寻址代码(所有索引均从零开始，页面大小以适合其中的元素数量指定，假设元素和页面大小是 2 的幂):

static inline size_t bheap_child(size_t iP, size_t page_size)
{
    size_t page = iP / page_size;
    size_t page_start = page * page_size;
    size_t next_page_start = (page + 1) * page_size;

    size_t i = iP - page_start;

    size_t c = heap_child(i);
    if (c  + 1 < next_page_start)
        return page_start + c;

    // /2 -> we put both siblings into one page
    size_t next_level_off = (c - (page_size - 1)) / 2;

    // #elements in the last level of the page
    size_t page_ways = page_size / 2;

    size_t k = heap_child_k(page, page_ways);

    // skip root node element in that page
    size_t x = (k + next_level_off) * page_size + 1;

    return x;
}

访问父级:

static inline size_t bheap_parent(size_t iP, size_t page_size)
{
    size_t page = iP / page_size;
    size_t page_start = page * page_size;

    size_t i = iP - page_start;

    size_t p = heap_parent(i);
    if (p || !page)
        return page_start + p;

    size_t page_ways = page_size / 2;

    size_t q = heap_parent_k(page, page_ways);

    size_t off = (page - 1) % page_ways;

    size_t x = q * page_size + page_size - 1 - page_ways + off;

    return x;
}

另请参阅我的 git repo definitions of the helper functions .

1 这会有所不同，因为使用经典的二叉树寻址，每个级别都会使元素数量加倍，因此每个新级别很快就会跨越新页面。因此，当在这样的树中向下时，基本上每个级别的访问都会转换为页面错误或 TLB 访问。