Re: B+ tree - help

accpactec_at_hotmail.com wrote:
> Ok, I am looking at this question about b+ trees and I just don't get
> it. Here is the question:
>
> A given B+-tree is stored on a disk with blocks containing 512 bytes
> each. The indexed key, data pointer and pointer to a sub-tree occupy 8
> bytes, 6 bytes and 4 bytes, respectively. Assume we use Alternative (2)
> for data entries.
>
> a. Compute the order of the B+-tree.

Internal nodes of the tree consist of an alternation: [stp; ik; stp; ... ; ik; stp] where 'stp' is a subtree pointer and 'ik' the indexed key. Note that it always begins and ends with an 'stp'. The order is how many stp's you can fit in that scenario on a block.

> b. Calculate the minimum number of entries of data records that a
> 2-level B+-tree (not counting the root) with the given parameters can
> index.

Look at the tree. How many outgoing edges does each internal node at least have? So, knowing that the tree is balanced, how many leaf nodes are there at the bottom? And how many ik's must there at least be in each leaf node?

• Jan Hidders