B-Tree

B-Tree in Data Structure.

Every node in a binary search tree, such as an AVL Tree or a Red-Black Tree, can only have one value (key) and a maximum of two children, but there is another type of search tree known as a B-Tree that allows a node to store more than one value (key) and have more than two children.

• The Height Balanced m-way Search Tree, also known as B-Tree, was created by Bayer and McCreight in 1972. It was then given the name B-Tree.
• B-Tree can be defined as follows...

"B-Tree is a self-balanced search tree with multiple keys in every node and more than two children for every node."

• A B-tree is a method of placing and locating files (called records or keys) in a database. (The meaning of the letter B has not been explicitly defined.) The B-tree algorithm minimizes the number of times a medium must be accessed to locate a desired record, thereby speeding up the process.
• Here, number of keys in a node and number of children for a node is depend on the order of the B-Tree. 
• Every B-Tree has order.

B-Tree of Order m has the following properties...

1. All the leaf nodes must be at same level.
2. All nodes except root must have at least [m/2]-1 keys and maximum of m-1 keys.
3. All non leaf nodes except root (i.e. all internal nodes) must have at least m/2 children.
4. If the root node is a non leaf node, then it must have at least 2 children.
5. A non leaf node with n-1 keys must have n number of children.
6. All the key values within a node must be in Ascending Order.

For example, B-Tree of Order 4 contains maximum 3 key values in a node and maximum 4 children for a node.

Example..

The following operations are performed on a B-Tree...

1. Search
2. Insertion
3. Deletion

Search Operation in B-Tree

B-Tree

• The search operation in a B-Tree is similar to that of a Binary Search Tree.
• The search procedure in a Binary search tree begins at the root node, and we make a 2-way decision every time we make a decision (we go to either left subtree or right sub-tree).
• In a B-Tree, the search process also begins at the root node, but we make an n-way decision each time, where n is the total number of children a node has.
• The search operation in a B-Tree has a temporal complexity of O(log n). The following is how the search is carried out...

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.

• Searching in a B tree depends upon the height of the tree. The search algorithm takes O(log n) time to search any element in a B tree.

The insertion operation is performed as follows...

Step 1: 

• Check whether tree is Empty.

Step 2: 

• If tree is Empty, then create a new node with new key value and insert into the tree as a root node.

Step 3: 

• If tree is Not Empty, then find a leaf node to which the new key value cab be added using Binary Search Tree logic.

Step 4: 

• If that leaf node has an empty position, then add the new key value to that leaf node by maintaining ascending order of key value within the node.

Step 5: 

• If that leaf node is already full, then split that leaf node by sending middle value to its parent node. Repeat tha same until sending value is fixed into a node.

Step 6: 

• If the splitting is occurring to the root node, then the middle value becomes new root node for the tree and the height of the tree is increased by one.

Example..

Construct a B-Tree of Order 3 by inserting numbers from 1 to 10.

Deletion in B-Tree

At the leaf nodes, deletion is also conducted. It can be a leaf node or an inside node that needs to be deleted. In order to delete a node from a B tree, use the following algorithm.

• Determine the location of the leaf node.
• If the leaf node has more than m/2 keys, delete the required key from the node.
• If the leaf node lacks m/2 keys, fill in the gaps with the element from the eighth or left sibling.

1. If the left sibling has more than m/2 elements, shift the intervening element down to the node where the key is deleted and push the largest element up to its parent.
2. If the right sibling has more than m/2 items, shift the intermediate element down to the node where the key is deleted and push the smallest element up to the parent.

• Create a new leaf node by merging two leaf nodes and the parent node's intervening element if neither sibling has more than m/2 elements.
• If the parent has less than m/2 nodes, repeat the operation on the parent as well.

If the node to be removed is an internal node, its in-order successor or predecessor should be used instead. The process will be same as the node is deleted from the leaf node because the successor or predecessor will always be on the leaf node.

Let us see the Example:

• Remove node 53 from the B Tree of order 5, as indicated in the diagram.

• 53 is present in the right child of element 49. Delete it.

• Now there is only 57 items remaining in the node, and the minimal number of elements required in a B tree of order 5 is 2. 
• It's less than that, and the elements in its left and right subtrees aren't enough, so combine it with the left sibling and parent's intervening element, i.e. 49.

The B tree is used in following manners.

• Because accessing values held in a huge database that is saved on a disc is a very time consuming activity, B tree is used to index the data and enable fast access to the actual data stored on the discs.
• In the worst situation, searching an un-indexed and unsorted database with n key values takes O(n) time. In the worst-case scenario, if we use B Tree to index this database, it will be searched in O(log n) time.