B Tree

0

B-Tree

B-tree is a special type of self-balancing search tree in which each node can contain more than one key and can have more than two children. It is a generalized form of the binary search tree (BST)

Properties of B-Tree

  1. Every node in a B-Tree contains at most m children.
  2. Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
  3. The root nodes must have at least 2 nodes.
  4. All leaf nodes must be at the same level.

Operations

Searching:

Searching in B Trees is similar to that in Binary search tree. For example, if we search for an item 49 in the following B Tree. The process will something like following :

  1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.
  2. Since, 40<49<56, traverse right sub-tree of 40.
  3. 49>45, move to right. Compare 49.
  4. match found, return.


Post a Comment

0Comments
Post a Comment (0)