What is the pattern in the B-Heap?

Question

Please, help to recognize the pattern in this B-heap:

In normal Binary-heap we always use the following conditions: left_child = 2*i, right_child = 2*i+1 parent = i/2

But these conditions are applicable only for the first 2 levels, and I can't recognize the remaining pattern. Please, help me.

Answer 1

You can understand the addressing in a b-heap as a combination of classic binary-tree addressing and m-ary tree addressing.

The basic idea of a b-heap is to reduce the number of visited (memory) pages (cf. the blue boxes in your image) by first completely filling a page before using another page.¹

So when computing the child/parent index of an element, you can use the classic binary-tree addressing first (with indexes relative to the page begin), but you have to check whether the resulting index is valid in the page of the current element. If it is, then you're done. If it's not you have to lookup the child or parent page of the current element and then compute the offset in that page.

For the page addressing you have to use m-ary tree addressing, where m = page_size/2 - because each page has m child-pages.

Of course there are possible variations in the b-heap layout details. A relatively straight-forward scheme is to keep the last element in each page - and the first element in all pages but the first - unused. This wastes basically 2 element slots per page but simplifies the addressing.

Example addressing code (all indices are zero-based, page size is specified in number of elements that fit into it, assuming that element and page size are a power of two):

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;
}

For accessing the parent:

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;
}

See also my git repo for the definitions of the helper functions.

---

¹ This makes a difference because with classic binary-tree addressing each level doubles the number of elements such that quickly each new level spans new pages. Thus, when going down in such a tree basically each level access translates into a page fault or TLB access.