# What is B-Tree?

Connect with

Well, you must have so many questions in you mind when you heard about anything which has more impact in the software industry. What is Btre ?
where it can be used? How to use this BTree? B-Tree is an extension of Binray Search Tree (BST). B-Tree of order m satisfy following properties.

BTree is used in almost all the database.

## 1. Properties of Binary Tree

1. Each node has at most m children `ceil(m/2)` i.e. `ceil(5/2)=3`
2. Each internal node has atmost `ceil(m/2)` children.
3. Root has at least 2 children , if it is not leaf.
4. A non-leaf node with k children has `(k-1)` keys.
5. All leaves appear in same level.

## 2. Algorithm to insert B-Tree

let us consider , x be a number of node and m be the number of keys in a node .

1. Use Search procedure like m-array tree, to find leave node where x should be placed.
2. Add x to appropriate place in leave in ascending order.
3. if there are `m-1` or fewer key then done.
4. if more than `m-1` key i.e. overflow, then split the node into 2 equal parts and one middle element.
5. Add mid to parent and make these two new nodes as its child.
6. if there is a overflow in parent split it , we continue till o overflow occurs or root it self splits.

Connect with 