Results 1 to 6 of 6

Thread: How to construct B+ Tree?

  1. #1

    Thread Starter
    Fanatic Member sbasak's Avatar
    Join Date
    Aug 2001
    Location
    Globe Trotter
    Posts
    524

    Question 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
    Life is a one way journey, not a destination. Travel it with a smile and never regret anything.
    Yesterday is history, tomorrow is a mystery, today is gift - that's why we call it present.

  2. #2
    Fanatic Member sql_lall's Avatar
    Join Date
    Jul 2002
    Location
    Up Above (i.e. AUS)
    Posts
    571

    Question What is it

    For those of us here not on your wavelength, or the inexperienced (like me ) What is a B+ tree?? And how does a 6 pointers/node one differ from a 5 pointers/node one???
    sql_lall

  3. #3

    Thread Starter
    Fanatic Member sbasak's Avatar
    Join Date
    Aug 2001
    Location
    Globe Trotter
    Posts
    524
    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.
    Life is a one way journey, not a destination. Travel it with a smile and never regret anything.
    Yesterday is history, tomorrow is a mystery, today is gift - that's why we call it present.

  4. #4
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221
    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..
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  5. #5
    PowerPoster Evil_Giraffe's Avatar
    Join Date
    Aug 2002
    Location
    Suffolk, UK
    Posts
    2,555
    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.

  6. #6
    PowerPoster Evil_Giraffe's Avatar
    Join Date
    Aug 2002
    Location
    Suffolk, UK
    Posts
    2,555

    Re: How to construct B+ Tree?

    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width