B+ Trees

A Java applet that animates insertion into B+ trees.

This is a self-directed group project for CISC 235 - Information Structures (Winter 1997) taught by David Alex Lamb at Queen's University.

Informally, a B+ tree is an n-ary tree with n variable but large (often >100).

A B+ tree of order v consists of a root, internal nodes and leaves. The root my be either leaf or node with two or more children. Internal nodes contain between v and 2v keys, and a node with k keys has k + 1 children. Leaves are always on the same level. If a leaf is a primary index, it consists of a bucket of records, sorted by search key. If it is a secondary index, it will have many short records consisting of a key and a pointer to the actual record.

Insertion Into a B+ Tree:


  • 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.
If you were using a Java-enabled Web browser, you would see a nifty cool B+ Tree instead of this lame paragraph.

Build Your Own Tree:

Insert elements as before. Build yourself the tree you've always dreamed of!

If you were using a Java-enabled Web browser, you would see another nifty cool B+ Tree.
B+ Tree Applet by Kristi Thompson and Sean Mclaughlin. Our first Java App! Copyright © 1997. All Rights Reserved
Based in part upon the BST Search Tree Applet by James Stewart.

To use this applet, paste the following into your html document:

The width, height, vspace and hspace may be adjusted to suit your web page. The elements parameter specifies the set of records that the tree will start out with; you may include as many as you want or leave this parameter out entirely. The defaults parameter specifies the values initially appearing in the text entry boxes. It may also be left out.

http://www.Seanster.com/BplusTree
The Java source code is available here.
Our Bookmarks of B+ Tree and Java WWW Resources