B+ trees

Posted: December 23, 2010 in Databases

A B+ tree or else or B plus tree are multi-way trees, meaning that each node contains a set of keys and pointers.  The true value of B+ trees is obvious during data storing for efficient retrieval in a block-oriented storage context, such as filesystems, because of their very high fanout, which reduces the number of I/O operations required to find an element in the tree.

The B+ trees represent sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. They are dynamic and their hight grows and contracts as records are added or deleted. The contents and the number of index pages reflects this growth and shrinkage.

Simply put a B+ tree of order n (n>3) is a n-ary tree with the following properties:

  • All records are stored at the leaves of the tree
  • The root is either a leaf or has between two and n children
  • An internal node (non-leaf) stores up to n-1 keys to guide the searching; key i represents the smallest key in subtree i+ 1
  • Leaves are always on the same level

Adding Records to a B+ Tree

To insert records in a B+ tree one may follow the steps given in this site.

  • do a search to determine what bucket the new record should go in
  • if the bucket is not full, add the record.
  • otherwise, split the bucket.
  • allocate new leaf and move half the bucket’s elements to the new bucket
  • insert the new leaf’s smallest key and address into the parent.
  • if the parent is full, split it also
  • now add the middle key to the parent node
  • repeat until a parent is found that need not split
  • if the root splits, create a new root which has one key and two pointers.

It also provides with a java online tool to build a b+ tree. For example, one may have the following records in the corresponding order:

18, 96, 41, 54, 112, 28, 50, 90, 23, 43, 14, 36, 131

This would generate the following results

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s