Custom Creation:

This section of the User Guide will take you through the steps of creating/randomly generating your own B-Tree to practising questions on that B-Tree.

• 1.1) Custom B-Tree Creation
• 1.2) Random B-Tree Creation
• 1.3) Save and Load a B-Tree
• 1.4) Questions on Created B-Tree (Random or Custom)

B-Tree Creation

When entering the Custom Tree Creation Menu you will be greeted with the following page. From here you will have all the tools you need to create your custom/randomly generated B-Tree.

To navigate back to the main menu select the Back button located on the top left of the screen. The light bulb on the top left of the screen will switch the application in and out of dark mode.

The arrow and centre(.) buttons will move the B-Tree around within the canvas and the centre button will move it to the centre of the canvas.

To get help with using the software, select the “Need Help” button and the following pop up will appear where you can view a quick guide to the software.

1.1) Custom B-Tree Creation

To create a custom B-Tree you will use the tools in the figure below. In order to create a new B-Tree you will need to select the “Max Degree” input box and insert a numerical value between 2 and 4. Once entering the value, select the “Custom Tree” button.

After selecting the “Custom Tree” button, the canvas should allow you to insert/delete keys as seen in the figure below.

To insert keys, select the “Insert” input box and insert a numerical value and then click the “Insert” button. Once completed, you will see a key pop up in the canvas and this can be seen in the left image. After continually inserting values, you will eventually have a B-Tree that looks as you desire, this B-Tree will be restructured automatically and requires no user input to change it.

If you made a mistake or you would like to remove a key, you can use the delete feature. To delete keys, select the “Delete” input box and insert a numerical value (that already exists within the B-Tree) and then click the “Delete” button. Once completed, you will see the desired key removed from the B-Tree. The deletion from the B-Tree will cause it to be restructured automatically and requires no user input to change it. For example, removing 22 from the B-Tree above:

1.2) Random B-Tree Creation

To create a randomly generated B-Tree you will use the tools in the figure below. In order to create a new randomly generated B-Tree you will need to select the “Max Degree” input box and insert a numerical value between 2 and 4. You will need to select the “Num Keys” input box and insert a numerical value between 1 and 100.

To use a seed to generate your random B-Tree, you will need to select the “Seed” input box and insert a numerical and select the “Use Seed” Checkbox. Essentially all this does is create a B-Tree using a particular seed.

Once entering the values described above, select the “Random Tree'' button. After selecting the “Random Tree” button, the canvas should allow you to insert/delete keys as seen in the figure below and it will create a randomly generated B-Tree on the canvas. After generating the random B-Tree you can use the insert and delete key functionality to further customise your randomly generated B-Tree.

To insert keys, select the “Insert” input box and insert a numerical value and then click the “Insert” button. Once completed, you will see your key inserted into the B-Tree, the B-Tree will be restructured automatically and requires no user input to change it.

To delete keys, select the “Delete” input box and insert a numerical value that already exists in the B-Tree and then click the “Insert” button. Once completed, you will see your key removed from the B-Tree, the B-Tree will be restructured automatically and requires no user input to change it.

1.3) Save and Load a B-Tree

To save and load a B-Tree, you will need to use the buttons displayed below.

To save a B-Tree that you have created, you will need to select the “Save” button. After saving the B-Tree, it will automatically download a text file to your device containing the contents used to create the B-Tree.

To load a B-Tree you will need to select the “Load” button. After selecting the button, a pop up to your field will be displayed. From here, you can select the text file of the B-Tree you would like to load. After selectin the file and opening it, the B-Tree will be created within the canvas area.

1.4) Questions on Created B-Tree

After creating/generating your custom B-Tree, you can then answer questions on it. To do this, select the “Generate Questions on Tree” button.

After selecting this button you will be greeted with the following screen. As soon as the screen loads, you will be prompted with a question to perform on the B-Tree. You can use sections 3 and 4 in the user guide to help you complete these operations.

Once you have completed the operation, select the “Check Answer” button. From here, one of two things may happen.

The first option is that the operation you performed may be incorrect. In this case you will be notified and you will have the chance to see the correct answer by selecting the “Show Correct Answer”.

The second option is that the operation you performed may be correct. In this case you will be notified and then a new question will be generated and the tree will be reset back to the original one created by you.

Note how a new question was created, from here you can perform the new question. If you get stuck during a question and would like to retry it, you can select the retry button situated at the top left of the screen.

You can navigate back the custom tree creation by selecting the back button. You can also access the help menu by selecting the button as seen below.

Custom B-Tree Creation

To create a custom B-Tree you will use the tools in the figure below. In order to create a new B-Tree you will need to select the “Max Degree” input box and insert a numerical value between 2 and 4. Once entering the value, select the “Custom Tree” button.

After selecting the “Custom Tree” button, the canvas should allow you to insert/delete keys as seen in the figure below.

To insert keys, select the “Insert” input box and insert a numerical value and then click the “Insert” button. Once completed, you will see a key pop up in the canvas and this can be seen in the left image. After continually inserting values, you will eventually have a B-Tree that looks as you desire, this B-Tree will be restructured automatically and requires no user input to change it.

If you made a mistake or you would like to remove a key, you can use the delete feature. To delete keys, select the “Delete” input box and insert a numerical value (that already exists within the B-Tree) and then click the “Delete” button. Once completed, you will see the desired key removed from the B-Tree. The deletion from the B-Tree will cause it to be restructured automatically and requires no user input to change it. For example, removing 22 from the B-Tree above:

Random B-Tree Creation

To create a randomly generated B-Tree you will use the tools in the figure below. In order to create a new randomly generated B-Tree you will need to select the “Max Degree” input box and insert a numerical value between 2 and 4. You will need to select the “Num Keys” input box and insert a numerical value between 1 and 100.

To use a seed to generate your random B-Tree, you will need to select the “Seed” input box and insert a numerical and select the “Use Seed” Checkbox. Essentially all this does is create a B-Tree using a particular seed.

Once entering the values described above, select the “Random Tree'' button. After selecting the “Random Tree” button, the canvas should allow you to insert/delete keys as seen in the figure below and it will create a randomly generated B-Tree on the canvas. After generating the random B-Tree you can use the insert and delete key functionality to further customise your randomly generated B-Tree.

To insert keys, select the “Insert” input box and insert a numerical value and then click the “Insert” button. Once completed, you will see your key inserted into the B-Tree, the B-Tree will be restructured automatically and requires no user input to change it.

To delete keys, select the “Delete” input box and insert a numerical value that already exists in the B-Tree and then click the “Delete” button. Once completed, you will see your key removed from the B-Tree, the B-Tree will be restructured automatically and requires no user input to change it.

Save and Load a B-Tree

To save and load a B-Tree, you will need to use the buttons displayed below.

To save a B-Tree that you have created, you will need to select the “Save” button. After saving the B-Tree, it will automatically download a text file to your device containing the contents used to create the B-Tree.

To load a B-Tree you will need to select the “Load” button. After selecting the button, a pop up to your field will be displayed. From here, you can select the text file of the B-Tree you would like to load. After selectin the file and opening it, the B-Tree will be created within the canvas area.

Questions on Created B-Tree

After creating/generating your custom B-Tree, you can then answer questions on it. To do this, select the “Generate Questions on Tree” button.

After selecting this button you will be greeted with the following screen. As soon as the screen loads, you will be prompted with a question to perform on the B-Tree. You can use sections 3 and 4 in the user guide to help you complete these operations.

Once you have completed the operation, select the “Check Answer” button. From here, one of two things may happen.

The first option is that the operation you performed may be incorrect. In this case you will be notified and you will have the chance to see the correct answer by selecting the “Show Correct Answer”.

The second option is that the operation you performed may be correct. In this case you will be notified and then a new question will be generated and the tree will be reset back to the original one created by you.

Note how a new question was created, from here you can perform the new question. If you get stuck during a question and would like to retry it, you can select the retry button situated at the top left of the screen.

You can navigate back the custom tree creation by selecting the back button. You can also access the help menu by selecting the button as seen below.

Answer Random Questions

When entering the Answer Random Questions menu you will be greeted with the following page. As soon as the screen loads, you will be prompted with a question to perform on a random B-Tree. You can use sections 3 and 4 in the user guide to help you complete these operations.

Once you have completed the operation, select the “Check Answer” button. From here, one of two things may happen.

The first option is that the operation you performed may be incorrect. In this case you will be notified and you will have the chance to see the correct answer by selecting the “Show Correct Answer”.

The second option is that the operation you performed is correct. In this case you will be notified and then a new question will be generated with a new random tree.

Note how a new question was created, from here you can perform the new question. If you get stuck during a question and would like to retry it, you can select the retry button situated at the top left of the screen.

You can navigate back the custom tree creation by selecting the back button. You can also access the help menu by selecting the button as seen below.

Manipulations:

The tree manipulation guide is an introduction into how to manipulate the B-tree to achieve the desired answer. Every possible way to manipulate the B-Tree is listed below.

• 1.1) Moving a key
• 1.2) Inserting a Key into a Node
• 1.3) Removing a Key from a Node
• 1.4) Deleting a Key
• 1.5) Moving an Entire Node
• 1.6) Establishing a Child Node Link
• 1.7) Overwriting a Child Node
• 1.8) Splitting the Root node

1.1) Moving a Key:

To move a key, follow these steps:

1. Hover your mouse pointer over the key you want to move.
2. Left-click and hold the mouse button to select the key.
3. The colour of the key will change from light blue to a slightly darker blue to indicate that it has been selected.
4. While keeping the left mouse button pressed, drag your mouse to the desired location on the canvas.
5. Once you've reached the desired position for the key on the canvas, release the left mouse button to place it.

1.2) Inserting a Key into a Node:

To insert a key into a node, follow the instructions in 1.1 for selecting and moving a key. When positioning the key within the node, observe the colour change from light blue to green, signifying the key's correct placement. There are three key attachment positions within a node:

1. 1.2.1. Adding to the Front of the Node:
   • To attach a key to the front of the node, hover the selected key so that the right half of the key overlaps with the left edge of the node.
   • The key will turn green when it's in the correct position for placement within the node.
   • Release the left mouse button to place the key at the front of the node.
   
2. 1.2.2. Adding to the End of the Node:
   • To attach a key to the end of the node, hover the selected key so that the right half of the key overlaps with the left edge of the node.
   • The key will change from light blue to green to indicate it's ready for placement at the end.
   • Release the left mouse button to insert the key at the node's end.
   
3. 1.2.3. Adding Between Other Keys Within the Node:
   • To attach a key between two existing keys within the node, hover your mouse over the desired location between the keys.
   • The selected key that you are dragging should be in between the keys that you want to place the selected key between.
   • As you drag the key to the space between the keys, it will change colour to green, indicating the correct position.
   • Release the left mouse button to insert the key in the desired location between the existing keys within the node.
   

1.3) Removing a Key from a Node:

To remove a key from a node, follow these steps:

1. Locate the node containing the key you want to remove.
2. Left-click on the key you wish to remove and hold down the left mouse button.
3. While holding the left mouse button, drag the key away from the tree or node.
4. Release the left mouse button to detach the key from the node.

1.4) Deleting a Key:

To delete a key from the tree, follow these steps:

1. Locate the key you want to delete within the tree.
2. Left-click on the key you wish to delete and hold down the left mouse button.
3. While holding the left mouse button, drag the key to the bottom right of the canvas.
4. As you move the key to this area, an "X" symbol will appear in the bottom right corner of the canvas.
5. Release the left mouse button while the key is over the "X" symbol, the key will be red if it is in the correct range to delete.
6. The key will be deleted from the tree entirely.

1.5) Moving an Entire Node:

Left-clicking and dragging moves individual keys, however, there may be situations where we would like to move an entire node instead of just moving individual keys.

To move an entire node, follow these steps:

1. Press the spacebar to enter “move entire node” mode.
2. You will be able to determine if you are within this mode if all of the first keys within every node, including free nodes, are colored green.
3. Select the first key within the node that you would like to move, by left-clicking the first key within the node and holding down the left mouse button.
4. Note that the only key that you can select to move an entire node is the first key within the node, and this is indicated by the green color of the first key.
5. While keeping the left mouse button pressed, drag your mouse to the desired location on the canvas.
6. Once you've reached the desired position for the node on the canvas, release the left mouse button to place it.

1.6) Establishing a Child Node Link:

To create a link between a child node and the tree, follow these detailed steps:

1. Identify the node to which you want to attach a child node.
2. Determine the keys between which you intend to establish a connection. The connection's nature is influenced by its placement in relation to these keys.
3. Hover your mouse over the lower right or lower left corner of the key from which you wish to initiate the connection.
4. When positioned correctly, a small red circle will appear, signaling that you can initiate a connection from this point.
5. Left-click and hold down the mouse button to initiate the connection when you see the small red circle.
6. Drag your mouse in the direction of the node you want to connect as a child to the tree.
7. While dragging, you'll notice a yellow arrow extending from the original key location where you clicked; this arrow represents the ongoing connection process, often referred to as "connection mode."
8. Additionally, during connection mode, a small red circle will appear at the middle-top of every node that can potentially serve as a child to the original node where you initiated the connection.
9. To finalize the connection, while in connection mode, drag your mouse to the small red circle positioned at the top of the node you want to connect to.
10. Upon hovering over the small red circle, release your mouse click to establish the connection.
11. If the connection is successful, a yellow arrow will be drawn between the two nodes.

1.7) Overwriting a Child Node:

There may be cases where a connection between a parent node and child node already exists, however, you would like to overwrite this already established connection to make a new connection between the parent node and a new child node.

To overwrite a child node, follow these steps:

1. Identify the parent node with the existing child node connection you want to replace.
2. Determine the keys between which you intend to create the new connection, taking into account the adjusted relationship.
3. Hover your mouse over the bottom right or bottom left corner of the key from which you wish to initiate the new connection.
4. Once correctly positioned, a small red circle will indicate that you can initiate the connection from this location.
5. Left-click and hold down the mouse button when the small red circle is visible to start the new connection.
6. Drag your mouse towards the desired node you wish to connect as the new child node.
7. During this process, you'll observe a yellow arrow extending from the original key location where you initiated the connection, representing the ongoing "connection mode."
8. Additionally, within connection mode, a small red circle will appear at the middle-top of every node that can potentially become the new child node.
9. To complete the process, while in connection mode, guide your mouse to the small red circle positioned at the top of the node you want to connect as the new child node.
10. Upon hovering over the small red circle, release your mouse click to establish the new connection.
11. If successful, a yellow arrow will be drawn between the parent node and the new child node, effectively overwriting the previous connection.

1.8) Splitting the Root Node:

There may be cases where you need to split the root node of the tree so that the median key of the original root becomes the single key of the new root and the keys contained in the left half of the original root become the new roots’ left child and the keys contained in the right half of the original root become the new roots’ right node.

Please note that functionality of splitting the node will only be available to the user if the root node has the maximum amount of keys i.e., (2t-1) keys.

To split the root node, follow these steps:

1. Hover your mouse to the area slightly above the median key of the root node.
2. If the root is available to be split then a split node symbol will appear. The symbol looks like a diverging path of three yellow arrows.
3. Left click the mouse button to perform the split root function.

1.1) Moving a Key:

To move a key, follow these steps:

1. Hover your mouse pointer over the key you want to move.
2. Left-click and hold the mouse button to select the key.
3. The colour of the key will change from light blue to a slightly darker blue to indicate that it has been selected.
4. While keeping the left mouse button pressed, drag your mouse to the desired location on the canvas.
5. Once you've reached the desired position for the key on the canvas, release the left mouse button to place it.

1.2) Inserting a Key into a Node:

To insert a key into a node, follow the instructions in 1.1 for selecting and moving a key. When positioning the key within the node, observe the colour change from light blue to green, signifying the key's correct placement. There are three key attachment positions within a node:

1. 1.2.1. Adding to the Front of the Node:
   • To attach a key to the front of the node, hover the selected key so that the right half of the key overlaps with the left edge of the node.
   • The key will turn green when it's in the correct position for placement within the node.
   • Release the left mouse button to place the key at the front of the node.
2. 1.2.2. Adding to the End of the Node:
   • To attach a key to the end of the node, hover the selected key so that the right half of the key overlaps with the left edge of the node.
   • The key will change from light blue to green to indicate it's ready for placement at the end.
   • Release the left mouse button to insert the key at the node's end.
3. 1.2.3. Adding Between Other Keys Within the Node:
   • To attach a key between two existing keys within the node, hover your mouse over the desired location between the keys.
   • The selected key that you are dragging should be in between the keys that you want to place the selected key between.
   • As you drag the key to the space between the keys, it will change colour to green, indicating the correct position.
   • Release the left mouse button to insert the key in the desired location between the existing keys within the node.

1.3) Removing a Key from a Node:

To remove a key from a node, follow these steps:

1. Locate the node containing the key you want to remove.
2. Left-click on the key you wish to remove and hold down the left mouse button.
3. While holding the left mouse button, drag the key away from the tree or node.
4. Release the left mouse button to detach the key from the node.

1.4) Deleting a Key:

To delete a key from the tree, follow these steps:

1. Locate the key you want to delete within the tree.
2. Left-click on the key you wish to delete and hold down the left mouse button.
3. While holding the left mouse button, drag the key to the bottom right of the canvas.
4. As you move the key to this area, an "X" symbol will appear in the bottom right corner of the canvas.
5. Release the left mouse button while the key is over the "X" symbol, the key will be red if it is in the correct range to delete.
6. The key will be deleted from the tree entirely.

1.5) Moving an Entire Node:

Left-clicking and dragging moves individual keys, however, there may be situations where we would like to move an entire node instead of just moving individual keys.

To move an entire node, follow these steps:

1. Press the spacebar to enter “move entire node” mode.
2. You will be able to determine if you are within this mode if all of the first keys within every node, including free nodes, are colored green.
3. Select the first key within the node that you would like to move, by left-clicking the first key within the node and holding down the left mouse button.
4. Note that the only key that you can select to move an entire node is the first key within the node, and this is indicated by the green color of the first key.
5. While keeping the left mouse button pressed, drag your mouse to the desired location on the canvas.
6. Once you've reached the desired position for the node on the canvas, release the left mouse button to place it.

1.6) Establishing a Child Node Link:

To create a link between a child node and the tree, follow these detailed steps:

1. Identify the node to which you want to attach a child node.
2. Determine the keys between which you intend to establish a connection. The connection's nature is influenced by its placement in relation to these keys.
3. Hover your mouse over the lower right or lower left corner of the key from which you wish to initiate the connection.
4. When positioned correctly, a small red circle will appear, signaling that you can initiate a connection from this point.
5. Left-click and hold down the mouse button to initiate the connection when you see the small red circle.
6. Drag your mouse in the direction of the node you want to connect as a child to the tree.
7. While dragging, you'll notice a yellow arrow extending from the original key location where you clicked; this arrow represents the ongoing connection process, often referred to as "connection mode."
8. Additionally, during connection mode, a small red circle will appear at the middle-top of every node that can potentially serve as a child to the original node where you initiated the connection.
9. To finalize the connection, while in connection mode, drag your mouse to the small red circle positioned at the top of the node you want to connect to.
10. Upon hovering over the small red circle, release your mouse click to establish the connection.
11. If the connection is successful, a yellow arrow will be drawn between the two nodes.

1.7) Overwriting a Child Node:

There may be cases where a connection between a parent node and child node already exists, however, you would like to overwrite this already established connection to make a new connection between the parent node and a new child node.

To overwrite a child node, follow these steps:

1. Identify the parent node with the existing child node connection you want to replace.
2. Determine the keys between which you intend to create the new connection, taking into account the adjusted relationship.
3. Hover your mouse over the bottom right or bottom left corner of the key from which you wish to initiate the new connection.
4. Once correctly positioned, a small red circle will indicate that you can initiate the connection from this location.
5. Left-click and hold down the mouse button when the small red circle is visible to start the new connection.
6. Drag your mouse towards the desired node you wish to connect as the new child node.
7. During this process, you'll observe a yellow arrow extending from the original key location where you initiated the connection, representing the ongoing "connection mode."
8. Additionally, within connection mode, a small red circle will appear at the middle-top of every node that can potentially become the new child node.
9. To complete the process, while in connection mode, guide your mouse to the small red circle positioned at the top of the node you want to connect as the new child node.
10. Upon hovering over the small red circle, release your mouse click to establish the new connection.
11. If successful, a yellow arrow will be drawn between the parent node and the new child node, effectively overwriting the previous connection.

1.8) Splitting the Root Node:

There may be cases where you need to split the root node of the tree so that the median key of the original root becomes the single key of the new root and the keys contained in the left half of the original root become the new roots’ left child and the keys contained in the right half of the original root become the new roots’ right node.

Please note that functionality of splitting the node will only be available to the user if the root node has the maximum amount of keys i.e., (2t-1) keys.

To split the root node, follow these steps:

1. Hover your mouse to the area slightly above the median key of the root node.
2. If the root is available to be split then a split node symbol will appear. The symbol looks like a diverging path of three yellow arrows.
3. Left click the mouse button to perform the split root function.

B-Tree Properties

Before we delve into B-tree insertions with preemptive splitting, let's ensure we have a solid understanding of what a B-tree is. A B-tree is a self-balancing search tree data structure that maintains sorted data and enables efficient insertion, deletion, and search operations. It's widely used in database systems and file systems because of its balanced structure and efficient performance characteristics.

A B-tree of degree t is defined by the following properties:

• Every node has at most 2*t-1 keys. Ex: A tree of degree 2 has a maximum of (2*2)-1 = 3 keys for each node.
• Every node (except the root) has at least t-1 keys. Ex: A tree of degree 2 has a minimum of (2)-1 = 1 key for each node.
• The root has at least 1 key.
• All keys within a node in the tree must be sorted in increasing order.
• If a node has n keys then that node must have n+1 children.
• All leaves have the same depth, ensuring balanced search operations.

Insertion Guide:

Inserting into a B-Tree

Deletion Guide:

B-Tree Properties

Before we delve into B-tree insertions with preemptive splitting, let's ensure we have a solid understanding of what a B-tree is. A B-tree is a self-balancing search tree data structure that maintains sorted data and enables efficient insertion, deletion, and search operations. It's widely used in database systems and file systems because of its balanced structure and efficient performance characteristics.

A B-tree of degree t is defined by the following properties:

• Every node has at most 2*t-1 keys. Ex: A tree of degree 2 has a maximum of (2*2)-1 = 3 keys for each node.
• Every node (except the root) has at least t-1 keys. Ex: A tree of degree 2 has a minimum of (2)-1 = 1 key for each node.
• The root has at least 1 key.
• All keys within a node in the tree must be sorted in increasing order.
• If a node has n keys then that node must have n+1 children.
• All leaves have the same depth, ensuring balanced search operations.

Inserting into a B-Tree

What is Preemptive Splitting?

• Preemptive splitting is a type of insertion method that we use for inserting into B-trees. This method ensures that insertions within a B-Tree can be done within a single traversal to the insertion point.
• To preemptively split a B-Tree, while traversing the tree to the insertion point, we check every single node that we traverse to see if it needs to be preemptively split. This is done regardless of whether or not the insertion occurs at that node.
• To determine if a node needs to be split, we look at the number of keys within that node. If the number of keys within that node is equal to the maximum number of allowable keys then it needs to undergo splitting.
• To perform the split, take the median key of that node and place it into its parent node, then update the parent’s node child pointers to point to the left half of the split node and the right half of the split node in the appropriate locations.

Case 1: Inserting a key into a leaf node where the leaf node has less than the maximum amount of keys ie. (2t-1) keys.

• 1.a) Without preemptive splitting
• Traverse the tree to the correct leaf node.
• Simply insert the key into the correct position within the leaf node.
• Example: Insert 7

Case 1: Inserting a key into a leaf node where the leaf node has less than the maximum amount of keys ie. (2t-1) keys.

• 1.b) With pre-emptive splitting
• Traverse the tree to the correct leaf node.
• If any of the nodes along the traversal that are not the leaf node have the maximum amount of keys, then that specific node needs pre-emptive splitting.
• Split that node by taking the median of that node and inserting it into it's parent node.
• The left half of the split node and the right half of the split node become the new children of the parent node.
• Update the children to correspond to the correct node.
• Example: Insert 49

• Now complete the traversal to the correct leaf node.
• Simply insert the key into the correct position within the leaf node.

Case 2: Inserting a key into a leaf node where the leaf node has the maximum amount of keys ie. (2t-1) keys.

• 2.a) Without preemptive splitting
• Traverse the tree to the correct leaf node.
• Example: Insert 69

• If the leaf node where we want to insert the new key, has the maximum amount of keys, then split that leaf node.

• Split the leaf node by taking the median key of that node and moving it to the correct position in its parent node.
• The left half of the split node and the right half of the split node become the new children of the parent node.
• Update the children to correspond to the correct node.

• Now that the leaf node is appropriately split:
• Insert the key into the leaf node that corresponds to the correct traversal of the tree.

Case 2: Inserting a key into a leaf node where the leaf node has the maximum amount of keys ie. (2t-1) keys.

• 2.b) With preemptive splitting
• Traverse the tree to the correct leaf node.
• If any of the nodes along the traversal that are not the leaf node have the maximum amount of keys, then that specific node needs pre-emptive splitting.
• Example: Insert 18

• Split that node by taking the median of that node and inserting it into it's parent node.
• The left half of the split node and the right half of the split node become the new children of the parent node.
• Update the children to correspond to the correct node.

• Now complete the traversal to the correct leaf node.

• If the leaf node where we want to insert the new key, has the maximum amount of keys, then split that leaf node.

• Split the leaf node by taking the median key of that node and moving it to the correct position in its parent node.
• The left half of the split node and the right half of the split node become the new children of the parent node.
• Update the children to correspond to the correct node.

• Now that the leaf node is appropriately split:
• Insert the key into the leaf node that corresponds to the correct traversal of the tree.

B-Tree Properties

Before we delve into B-tree insertions with preemptive splitting, let's ensure we have a solid understanding of what a B-tree is. A B-tree is a self-balancing search tree data structure that maintains sorted data and enables efficient insertion, deletion, and search operations. It's widely used in database systems and file systems because of its balanced structure and efficient performance characteristics.

A B-tree of degree t is defined by the following properties:

• Every node has at most 2*t-1 keys. Ex: A tree of degree 2 has a maximum of (2*2)-1 = 3 keys for each node.
• Every node (except the root) has at least t-1 keys. Ex: A tree of degree 2 has a minimum of (2)-1 = 1 key for each node.
• The root has at least 1 key.
• All keys within a node in the tree must be sorted in increasing order.
• If a node has n keys then that node must have n+1 children.
• All leaves have the same depth, ensuring balanced search operations.

Introduction to B-Tree Deletion

• B-Tree deletion is more complicated than insertion because operations not only occur at the leaf nodes but we can also delete from the internal nodes.
• As with insertion, we must perform the operation where we do not violate the properties of a B-Tree.
• Just as with insertions we are going to use a method called preemptive merging to ensure that B-Tree deletions can be performed with a single traversal of the tree.

What is Preemptive Merging?

• Preemptive merging, similar to preemptive splitting, is a type of deletion method that we use for deleting from B-trees. This method ensures that deletions from a B-Tree can be done within a single traversal to the deletion point on every occurence of the operation.
• To preemptively merge a B-Tree, while traversing the tree to the deletion point, we check every single node that we traverse, besides the root node, to see if it needs to be preemptively merged. This is done regardless of whether or not the deletion occurs at that node.
• To determine if a node needs to be merged, we look at the number of keys within that node. If the number of keys within that node is equal to the minimum number of allowable keys then it needs to undergo merging.
• Let’s call the node that needs to undergo merging the “merging node”.
• To perform the merge there are two cases that we must account for:

Deleting from a B-Tree

What is Preemptive Merging?

• Preemptive merging, similar to preemptive splitting, is a type of deletion method that we use for deleting from B-trees. This method ensures that deletions from a B-Tree can be done within a single traversal to the deletion point on every occurence of the operation.
• To preemptively merge a B-Tree, while traversing the tree to the deletion point, we check every single node that we traverse, besides the root node, to see if it needs to be preemptively merged. This is done regardless of whether or not the deletion occurs at that node.
• To determine if a node needs to be merged, we look at the number of keys within that node. If the number of keys within that node is equal to the minimum number of allowable keys then it needs to undergo merging.
• Let’s call the node that needs to undergo merging the “merging node”.
• To perform the merge there are two cases that we must account for:

Case 1: Deleting a key at the leaf node where the leaf node has more than the minimum amount of keys in it, ie more than (t-1) keys

2.a) Deleting a key at the leaf node where the leaf node has the minimum amount of keys in it, ie (t-1) keys and The leaf node has a left immediate sibling node with more than the minimum amount of keys ie. more than (t-1) keys

• Example: Delete 86
• Locate the key to delete.
• If the key to delete lies in a leaf node and the leaf node contains the minimum amount of keys, ie. (t-1) keys:

• Look to the immediate left sibling node of the shared parent key

• If the immediate left sibling node of the shared parent key has more than (t-1) keys:
• Borrow the shared parent key's predecessor by moving it into the parent node and moving the shared parent key into the node we want to delete from

• The leaf node now has more than the minimum amount of keys so:
• We simply delete the key from the leaf node.

2.b) Deleting a key at the leaf node where the leaf node has the minimum amount of keys in it, ie (t-1) keys and The leaf node’s left immediate sibling node has the minimum amount of keys ie (t-1) keys, but the leaf node’s right immediate sibling node has more than the minimum amount of keys ie. more than (t-1) keys

• Example: Delete 47
• Locate the key to delete.
• If the key to delete lies in a leaf node and the leaf node contains the minimum amount of keys, ie. (t-1) keys:

• First look to the immediate left sibling node of the shared parent key
• If the immediate left sibling node of the shared parent key also has the minimum amount of keys, ie (t-1) keys:

• Look to the immediate right sibling node of the shared parent key

• If the immediate right sibling node of the shared parent key has more than the minimum amount of keys, ie. (t-1) keys:
• Borrow the shared parent key's successor by moving it into the parent node and moving the shared parent key into the node we want to delete from

• The leaf node now has more than the minimum amount of keys so:
• We simply delete the key from the leaf node.

2.c) Deleting a key at the leaf node where the leaf node has the minimum amount of keys in it, ie (t-1) keys and All immediate siblings have the minimum amount of keys ie. (t-1) keys

• Example: Delete 40
• Locate the key to delete.
• If the key to delete lies in a leaf node and the leaf node contains the minimum amount of keys, ie. (t-1) keys:

• First look to the immediate left sibling node of the shared parent key
• If the immediate left sibling node of the shared parent key also has the minimum amount of keys, ie (t-1) keys:

• Look to the immediate right sibling node of the shared parent key
• If the immediate right sibling node of the shared parent key also has the minimum amount of keys, ie (t-1) keys:

• Merge the key to delete within either the immediate left sibling node or the immediate right sibling node by merging the sibling node and the shared parent key to the node to delete from.
• Please note that you can merge with either sibling node and in this example we are merging with the left sibling node. (Merging with the right will also be fine)

• The leaf node now has more than the minimum amount of keys so:
• We simply delete the key from the leaf node.

3.a) Deleting a key at an internal node where the left child node has the more than the minimum amount of keys ie. more than (t-1) keys

• Example: Delete 49
• Locate the key to delete.
• If the key to delete lies in an internal node:

• Look to the left child node of the key to delete

• If the left child node of the key to delete has more than (t-1) keys:
• Borrow the key-to-delete's predecessor by moving it into the same node as the node where the key-to-delete is

• The internal node now has more than the minimum amount of keys so:
• We simply delete the key from the internal node.

3.b) Deleting a key at an internal node where the left child node has the minimum amount of keys ie. (t-1) keys and the right child node has more than the minimum amount of keys ie. more than (t-1) keys

• Example: Delete 72
• Locate the key to delete.
• If the key to delete lies in an internal node:

• Look to the left child node of the key to delete

• If the left child node of the key-to-delete has the minimum amount of keys, ie (t-1) keys:
• Look to the right child node of the key-to-delete

• If the right child node of the key-to-delete has more than the minimum amount of keys, ie more than (t-1) keys:
• Borrow the key-to-delete's successor by moving it into the same node as the node where the key-to-delete is

• The internal node now has more than the minimum amount of keys so:
• We simply delete the key from the internal node.

3.c) Deleting a key at an internal node where both children have the minimum amount of keys in them, ie (t-1) keys

• Example: Delete 72
• Locate the key to delete.
• If the key to delete lies in an internal node:

• Look to the left child node of the key to delete

• If the left child node of the key-to-delete has the minimum amount of keys, ie (t-1) keys:
• Look to the right child node of the key-to-delete

• If the right child node of the key-to-delete has the minimum amount of keys, ie (t-1) keys:
• Merge the left child node and the right child node together

• The internal node now has the same amount of keys as it has children so:
• We simply delete the key from the internal node.

Glossary

Frequently Asked Questions - FAQ