How to construct B+ Tree?

Printable View

Sep 18th, 2002, 10:26 AM
sbasak

How to construct B+ Tree?

Given some numbers, how do you construct a B+ Tree?

For example, construct a 6 pointers/node B+tree with following numbers.

2,3,5,7,11,17,19,23,29,31

Any help highly appreciated.

Thanks a lot :)
Sep 24th, 2002, 05:57 AM
sql_lall

What is it

For those of us here not on your wavelength, or the inexperienced (like me :D) What is a B+ tree?? And how does a 6 pointers/node one differ from a 5 pointers/node one???
Sep 25th, 2002, 03:11 AM
sbasak

All major databases (like Oracle, SQL Server etc.) internally use B+ Tree datastructure to organize data physically in the disk. B+ Tree is similar to Binary Tree, but in B+ tree, each leaf node is actually equivalent of physical hard disk block. Unlike Binary tree, B+tree is short and fat ie. number of levels in B+tree is quite low compared to binary tree. As a consequence, search in B+ tree is extremely fast. B tree is similar to B+ tree but in B tree, data index entries are not repeated.

For more information on B/B+ Tree, please see any standard data structure or database techonology book.

My question was how to construct a B+ tree programatically. It is often possible to construct such tree from intuition, but I'm not aware of the formal algorithm.
Oct 2nd, 2002, 07:44 AM
kedaman

I know a little about B trees, I know how they work basically so I could construct one, but B+ trees could be trickier. I was going to have a look into this as well as i need to map files onto physical addresses but frequent hdd access trough a binary tree would slow down indeed..
Oct 4th, 2002, 07:58 AM
Evil_Giraffe

Now bear with me here - I've had a hard summer's drinking since I had to answer an exam question on this. (Or at least, what I think you're referring to :) Never heard 'em called B+ trees tho)
Right, start with one block. This is your root node. The root node is the only node that can ever be less than half full.
[OffPoint]This should be about the size of a disk sector, or whatever size is fetched from the had disk, since it was designed to work from hard disks with very few disk accesses)[/OffPoint]
Each node/block is made up of pointers and (ordered) keys, in the form:
p1| k1 |p2| k2 | ... |p(n-1)| k(n-1) |p(n)
where p1 points to where you can find all key/value pairs with a key less than k1, p2 points to where you can find all key/value pairs with a key greater than or equal to k1 and less than k2, etc...

Except leaf nodes which also contain values but not pointers. I forget the exact structure of those, but it's not too complex - I'm sure you could figure it out. I think it's just ordered keys with values:
k1,v1 | k2,v2 | ... | kn,vn

We have to define 3 operations for a basic data structure: Add, Delete, Lookup

Since lookup is the easiest, I'll start there:
Start at the root node. Using your key, find the keys in the block that are above and below your key, and follow the pointer between them.
Do the same for each intermediate node you come to, until you get to a leaf node, where you can lookup your value.

Add:
Using the key, follow the same procedure as lookup until you find the leaf node that the value belongs in, and insert in the correct place the key/value pair.

BUT WAIT! What if there is no room in the block for this pair? (Remember these are fixed size blocks - did I mention that?)
If this is the case, you need to split the leaf node. Take the upper half of the node and place into a new block. Now take a pointer to that block and insert in the correct place in the parent block.
BUT WAIT! What if the parent node has no room for the new pointer?
Simple - recurse upwards until you reach a node that has room for the new pointer.
BUT WAIT! What if we reach the root node and it has no room? It has no parent and you can't create a second root node!
Simply create a parent for the root node. This becomes the new root node, and there are two pointers to the two blocks in the second layer. This is the only way you get a block less than half full, as you can probably see all other created blocks create two half full blocks.

Delete is similar, but you have to watch out for getting blocks less than half full. I forget exactly how this goes, but I'm sure you can figure out the details.

Hope this is of some help. I suggest you find a book on algorithms for a slightly less hazy description of the algorithm.
Oct 4th, 2002, 08:11 AM
Evil_Giraffe

Re: How to construct B+ Tree?

Quote:

Originally posted by sbasak
Given some numbers, how do you construct a B+ Tree?

For example, construct a 6 pointers/node B+tree with following numbers.

2,3,5,7,11,17,19,23,29,31

Any help highly appreciated.

Thanks a lot :)

Hey! I'll try an example! Right, here the values are in fact the keys, so forget the rubbish about key/value pairs.
In fact, we can probably forget the rubbish about leaf nodes being different to other nodes.
inserting 2,3,5,7,11 gives us:

Code:

P | K | P | K | P | K | P | K | P | K | P X 2 X 3 X 5 X 7 X 11 X

but inserting 17 gives us the first split:

Code:

P | K | P | K | P | K | P | K | P | K | P | 7 | X X X X X X X X ----------------------- ---------------- | | P | K | P | K | P | K | P | K | P | K | P P | K | P | K | P | K | P | K | P | K | P X 2 X 3 X 5 X X X X X X 7 X 11 X 17 X X X X X

does this help? It would look better if they were added in a random order, but it doesn't really matter that much. Since it takes so long constructing the disgrams, I'll leave the rest as an exercise for the reader :)