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
- Each node has at most m children
- Each internal node has atmost
- Root has at least 2 children , if it is not leaf.
- A non-leaf node with k children has
- 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 .
- Use Search procedure like m-array tree, to find leave node where x should be placed.
- Add x to appropriate place in leave in ascending order.
- if there are
m-1or fewer key then done.
- if more than
m-1key i.e. overflow, then split the node into 2 equal parts and one middle element.
- Add mid to parent and make these two new nodes as its child.
- if there is a overflow in parent split it , we continue till o overflow occurs or root it self splits.