B Tree-Introduction,
Insertion
V. Sudha
Department of Computer Science and
Engineering
Overview of this
Lecture
• Definition
• Insertion operation
• Example
• Complexity
B-Tree definition
A B-Tree of order m is a tree with the following
structural properties:
1. The root is either a leaf or has between 2 and
m children.
2. All nonleaf nodes (except the root) have
between ceil(m/2) and m children
3. All leaves are at the same depth
Insertion operation
Step 1 - Check whether tree is Empty. If tree is Empty, then
create a new node with new key value and insert it into the tree
as a root node.
Step 2 - If tree is Not Empty, then find the suitable leaf node
to which the new key value is added using Binary Search Tree
logic.
Step 3 - If that leaf node has empty position, add the new key
value to that leaf node in ascending order of key value within
the node.
Step 4 - If that leaf node is already full, split that leaf node by
sending middle value to its parent node. Repeat the same until
the sending value is fixed into a node.
Step 5 - If the spliting is performed at root node then the
middle value becomes new root node for the tree and the
height of the tree is increased by one.
Example
6, 2, 8, 1, 4, 5
6
Example
6, 2, 8, 1, 4, 5
2 6
Example
6, 2, 8, 1, 4, 5
2 6 8
Example
6, 2, 8, 1, 4, 5
6
After splitting
2 8
Example
6, 2, 8, 1, 4, 5
1 2 8
Example
6, 2, 8, 1, 4, 5
1 2 4 8
Splitting this node
Example
6, 2, 8, 1, 4, 5
2 6
1 4 8
Example
6, 2, 8, 1, 4, 5
2 6
1 4 5 8
Complexity
O(logmn)
