Unit-5 B tree- Data Structures | BCA 3rd sem 2023

Unit-5 B tree- Data Structures | BCA 3rd sem 2023-Hello everyone welcome to the pencilchampions.com website. This website provide Unit-5 B tree  Data Structures BCA 3rd sem for BCA student. Thankyou for visiting.

Unit-5

Introduction of  B TREE

• B tree is a self balance search tree in which each node could have more than two children and hold multiple keys.
• B tree on the other hand , can store multiple keys inside a single node.
• In a B tree, each node has a maximum of a children.
• The level of all the leaf nodes should be the same.
• A B treeis designed to store sorted data and allows search, insertion and deletion operation to be performed in logarithmic time. As In multiway search tree, there are so many nodes which have left subtree but no right subtree. Similarly, they have right subtree but no left subtree. As is known, access time in the tree is totally dependent on the level of the tree. So our aim is to minimize the access time which can be through balance tree only.
• For balancing the tree each node should contain n/2 keys. So the B tree of order n can be defined as:

1. All leaf nodes should be at same level.
2. All leaf nodes can contain maximum n-1 keys.
3. The root has at least two children.
4. The maximum number of children should be n and each node can contain k keys. Where, k<=n-1.
5. Each node has at least n/2 and maximum n nonempty children.
6. Keys in the non-leaf node will divide the left and right sub-tree where the value of left subtree keys will be less and value of right subtree keys will be more than that particular key.

Operations performed on B Tree

1. Insertion in B-Tree
2. Deletion from B-Tree
   

   ---

   Read external link-https://bcastudyguide.com/unit-5-b-tree/

   ---

1) Insertion in B-Tree

The insertion of a key in a B tree requires the first traversal in B-tree. Through the traversal, it is easy to find that key which needs to be inserted is already existed or not. There are basically two cases for inserting the key that are:

1. Node is not full
2. Node is already full
   

   ---

   Read more –https://pencilchampions.com/unit-4-tree-data-structures-bca-3rd-sem/

If the leaf node in which the key is to be inserted is not full, then the insertion is done in the node.

If the node were to be full then insert the key in order into existing set of keys in the node, split the node at its median into two nodes at the same level, pushing the median element up by one level.

Linear Search

It is a very basic and simple search algorithm.

In linear search we search an element in given array by traversing the array fro the starting till the desired element is found