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

Leave a Reply

Your email address will not be published. Required fields are marked *