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:
- B+ Trees: Some interesting, practical trees… – In particular, pay attention to slide 12 for inserting. Don’t worry about deleting.
- B+ Trees Notes from Univ of Dublin Trinity College
You can also find some great video tutorials on Youtube.
Speak Your Mind