B+ Trees

B+ Trees are very efficient search tree data structures that are related to binary search trees.  They are particularly useful in indexing situations where the entire data set cannot fit into main memory at one time.  Each node in a B+ Tree contains multiple keys and pointers (as compared to 1 key and two pointers in a binary search tree).  

There are two types of node structures used in B+ trees: Internal (or indexing) nodes, and leaf nodes (or data nodes).  Only leaf nodes contain data/objects that are being indexed; the internal nodes effectively provide a road map to which leaf node contains the data being search for.

Initially, a B+ Tree contains only one node, the root node, that is also a leaf. It is only when the root node must be split during an insertion that the tree gets one level deeper.  B+ Trees are much shallower for a data set when compared to a binary search tree holding the same number of values.  However, it has higher fanout.

Here are some additional resources on B+ trees that you might want to peruse:

You can also find some great video tutorials on Youtube.

Speak Your Mind



This site uses Akismet to reduce spam. Learn how your comment data is processed.