Re: B+ tree - help

Alt 2 is pretty is easy. it is basically when there is <k*, rid> such that k* is the data entry and the rid is the record ID pointing to the data from the index.

Data pointer are the pointers in the case of Alt 2 is the rid. subtree pointers are the pointers that are being pointed from a parent to its child/leaf.

I am not sure what you mean by "how many 'kinds' of block will you have in your ...".

Since the block size is 512, according to the specs of b+ tree, at least 256 byte must be filled since d < m < 2d where d is the order.

Bob Badour wrote:
> 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.
> > 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.
> >
> > I have been looking at wikipedia,
> > http://www.semaphorecorp.com/btp/algo.html and various other sites but
> > none of them really explain how this thing is done. Can someone please
> > help me with this.
>
> What does your textbook say about Alternative 2?
>
> What is the difference between a data pointer and a sub-tree pointer?
>
> How many kinds of blocks will you have in your B+-tree index?
>
> For each kind of block, assume you have N keys:
> How many pointers will you have in the block?
> What is the largest N you can fit in the block?
Received on Wed Sep 27 2006 - 07:03:51 CEST