B-Tree

Let's learn about the B-Tree data structure.

First, a B-Tree is one of the Balanced Trees that automatically balances itself so that all leaf nodes are at the same level.

In actual databases, B+Trees are used, which are an evolution of B-Trees.

To increase the maximum number of child nodes, a parent node stores one or more keys.
The keys in the parent node are sorted in ascending order.
The range of key values for child nodes is determined by the sorted order.

The maximum number of child nodes a B-Tree can have is an important parameter when using it.

Let's say M is the maximum number of child nodes for each node.

A B-Tree that can have a maximum of M children is called an M-ary B-Tree.

Here, the maximum number of keys in each node is M - 1.

The minimum number of child nodes in each node is ⌈ M / 2 ⌉. (Always round up the value divided by 2, e.g., 1.5 -> 2)

The minimum number of keys in each node is ⌈ M / 2 ⌉ - 1. This condition excludes leaf nodes and the root node.

To summarize:

Additionally, if an internal node has x keys, the number of child nodes must always be x + 1.

B-Tree Basic Structure

Since each node has at least one key, an internal node always has at least two children, regardless of the B-Tree's order.

B-Tree Key Search Process #

Starting from the root node, a top-down search is performed.

Here's the search process when the key to be searched is k.

Start from the root node and iterate through the keys.
1. If a key equal to k is found, terminate the search.
2. Compare the search value with the key. If k falls between keys, descend to the child node between those keys.
Repeat the above process until a leaf node is reached. If k is not found even in the leaf node, the search fails.

B-Tree Search 1

Data is always added to a leaf node.

If a node overflows, the keys are split left and right based on the median key, and the median key is promoted.