In this article we will try to understand basics of B tree and B+ tree.
B Tree is a specialized version of m-way tree. OK, so what is m-way tree then? It is pretty simple. M-way tree is a tree that can have m children. Just like binary tree can have 2 children, it is also a m way tree with m = 2. So how is B Tree a specialized version of m-way tree. B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties.
- Every node in a B-Tree contains at most m children.
- Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
- The root nodes must have at least 2 nodes.
- All leaf nodes must be at the same level.
It is not necessary that, all the nodes contain the same number of children but, each node must have m/2 number of nodes.
Now this is important. While performing some operations on B Tree, any property of B Tree may violate such as number of minimum children a node can have. To maintain the properties of B Tree, the tree may split or join.
One of the main reason of using B tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.
B+ Tree
B+ tree is an extension of the B tree. The difference in B+ tree and B tree is that in B tree the keys and records can be stored as internal as well as leaf nodes whereas in B+ trees, the records are stored as leaf nodes and the keys are stored only in internal nodes.
The records are linked to each other in a linked list fashion. This arrangement makes the searches of B+ trees faster and efficient. Internal nodes of the B+ tree are called index nodes.
The B+ trees have two orders i.e. one for internal nodes and other for leaf or external nodes. In the B+ tree, leaf nodes denote actual data pointers. B+ tree ensures that all leaf nodes remain at the same height.
Internal node :
- At most, an internal node of the tree contains n pointers.
- An internal node of the B+ tree can contain at least n/2 record pointers except the root node.
Leaf node:
- The leaf node of the B+ tree can contain at least n/2 record pointers and n/2 key values.
- At most, a leaf node contains n record pointer and n key values.
- Every leaf node of the B+ tree contains one block pointer P to point to next leaf node.
Difference between B Tree and B+ Tree
