# B-Trees

The B-tree is a generalization of a** binary search tree ** in which a node can have more than two children .The B-tree is optimized for systems that read and write large blocks of data.It has following properties

- The
**data items**are stored at**leaves**. - Every
**node**has between**M/2**and**M**children where**M**is a positive integer greater than**1**. **M**is the**order**as well as**height**of tree.- The non leaf nodes store up to
**M-1**keys. - The root is either a leaf or has between two and M children.
- All leaves are at the
**same depth**and have between**[L/2]**and**L**children.

## Insertion in B-Tree

The insertion in b-tree is done such that they satisfy all the properties listed above.

**Example**

Consider a B-Tree of** order 4** and we need to insert **5,3,21,9,1,13,2,7,10,12,4,8**.Each node can have **at most 4 pointers** and **3 keys (M-1) **or ** at least 2 pointers** and **1 key**.Since it is a binary search tree the keys of left subtree will be less than the root value and keys of right subtree will be greater than root value.

- Create a node
**a**and insert**5**.(Fig 1) - Insert
**3**to the left of**5 (3<5)**. - Insert
**21**to the right of**5(21 >5).** - In order to insert 9 split node
**a**into**b and c**as 9 cannot be accommodated in node a(**Max keys =3**).The**left pointer**of**9**points to**3**and**5****((3 ,5) <9)**and the**right pointer points**to**21(21 >9**),

- Insert
**1**in node**b (1<3)**(Fig 2). - Insert
**13**in node**c(13>9 and 13 <21).** **2**cannot be directly inserted in node**b**- In order to insert 2 split
**b**into**b and d**. **3**gets**stored**in node**a**.- Store
**1 and 2**in node**b**. - Store
**5**in node**d**.

- In order to insert 2 split

- Insert
**7**in node**d**Â .**(7 >5 and 7<9)**(Fig 3) - Insert
**10**in node**c**(**10 >9 and 10 <13**). - Now
**12**cannot be directly inserted in node**c**.- Split
**c**into**c and e**. **12**is then inserted in node Â**c**.**21**is stored in**e**.

- Split

- Insert
**4**in node**d**(**4 >3 and 4 <5**).(Fig 4) **8**cannot be inserted in**d**directly.- Split
**d**into**f and g** - Split
**f**into**f and h**. **8**is inserted in**h**.

- Split

Appreciate your efforts in explaining difficult concepts in an easy way