B-Tree Insertion in DBMS

A B-tree is a special type of m-way tree, commonly used for disk access. A B-tree of order m can have at most m-1 keys and m descendants. B-trees are advantageous because they allow nodes to hold many keys and key values while keeping the height of the tree relatively small.
All properties of an m-way tree exist in a B-tree of order m. Additionally, it has the following properties:

• No node in the B-tree has more than m children.
• All B-tree nodes, except roots and leaves, have at least m/2 descendants.
• A base node must have at least two elements.
• Each leaf node must be at the same level.
• Not all nodes need to have the same number of children, but each node should have half that number.
• Inserting an element into a B-tree requires two steps:
  Find a suitable node to place the element and split if necessary. This insertion method always follows a bottom-up approach.
  New keys are always placed on the outermost node. Use k as the key to insert. We follow a similar approach to binary search trees, starting at the root node and moving down until we reach a leaf node. When a leaf node is reached, the key is inserted into that leaf node.
• Unlike BST, the number of keys a node can hold is limited and predetermined. Before we put the key inside the node, make sure the node has extra capacity.

Inserting Data into B-Tree

Insertion of a new item into a B-Tree is done with the insertion method. The simplest form of this method is to make a copy of the node that you want to insert into and then insert it into the place where the original node was.

If the tree does not contain any nodes, create a root node and place the key within it. Increase the maximum number of keys that can be stored in the node.
Look for the right node to insert.

Once the node reaches capacity, proceed with the steps below.

• Arrange items from smallest to largest.
• Now there are elements that go beyond that limit. halfway share
  Drag the middle key to the top left so that the two adjacent keys become its child nodes.
  • If the node is not filled, follow the steps below:
    Arrange the nodes in ascending order.

While using a proactive insertion algorithm, when a node is full, it splits it before descending to it. The advantage of pre-split is that you don't have to traverse the same node twice. If we don't split the nodes before accessing them, but only decompose them when new keys are added (proactive approach), we might re-traverse each node from leaf to root. This happens in situations where all nodes on the root are completely filled from root to end. When you reach the end of a branch of the tree, split it and raise the key. When the button moves up, it splits the parent node (because it is already full). This domino effect does not occur with this pre-insertion process. However, this aggressive insertion has its drawbacks. You might end up creating splits that you don't want.

Use of Insertion

An example of insertion is the addition of an element to a B-Tree. A new key is created, and then inserted into the B-Tree. This new key can then be used when searching for data in the tree.

A common use for insertion is when a user wants to add a new column to a table. For example, if there is already a column named "Phone" but users want to add another column called "Mobile". Adding two columns adds more data, which means more space within the table and thus more space required in the database. In this case, new rows are added to the end of each table row. The key value pair is used as the index for both columns when looking up values in either column (just as it would be if both columns were added at once).

It can be done in two ways:

1)  You can use the copy() method on your tree, which will make a copy of the item at the top level (i.e., your root node). Then, you can insert it at any location in your tree by calling insert() on this new copy.

2)  You can create an array with several items and then use push_back() or insert() on each array element to add them as children of their respective parent nodes.

Algorithm

STEP:1- Find the leaf node to which X should be added using the SEARCH method for M-way trees (explained above).

STEP 2- Add X to this node where it belongs among the existing values. Because it is a leaf node, subtrees are not an issue.

STEP 3- After adding X, if the node contains M-1 or less values, we are done.

STEP 4- We refer to a node as having overflowed if there are M nodes after adding X. We divided the node into three sections to fix it as follows:

• Left: the initial values for (M-1)/2
• The middle value is position 1 plus ((M-1)/2)
• the most recent (M-1)/2 values