Change in B-tree index

[ayshakhatun3113]

In this example, we have an ordered list of numeric values which represent the index. The tree is balanced because all the lower leaves, shown here in green, are at the same level (3). Leaves, also known as leaf nodes, contain the actual data or references to data records in the database table. In the Oracle example, these leaves contain the ROWID, which allows you to quickly identify the desired data record on the hard disk.

Above the leaves are the nodes (branches), shown here in yellow. In this example, each node can only hold three values ​​and therefore only has three child/leaf nodes. Nodes always represent only an area for the nodes or leaves stored in them. The top node is called the root, shown here in blue, and represents the start of the B-tree index.

To illustrate how this works, let's now look at a single block of numbers. For example, the second entry in the root (18-28) refers to all values ​​between the numbers 18 and 28. Since we need to store a bc data total of 6 numbers and the maximum storage capacity has been set to three values ​​per leaf, a new node must be created. This new node again contains two entries (18-23 | 24-28), which in turn refer to a range of numbers. In this example, only two of the three positions are occupied. The individual values ​​are now stored at the lowest level (level 3). The limit of three values ​​per node/leaf defined for the entire tree also applies here.

In the example, there is still one free position at the root (blue) and at the second node (yellow). This means that the maximum number of values ​​to be stored has not yet been reached. If the values ​​32 and 36 are now added, a new leaf is created on the right-hand side. This leaf creates a new entry at the node, which now has three entries. This tree, limited to three entries per node, can store up to 27 entries at the third level (33). If the number of values ​​to be stored exceeds 27, a new level must be created. The tree could now store up to 81 values ​​at level 4 (34).


In an Oracle database, the size of nodes/blocks can be defined when creating the database. Let's take a block size of 8 KB as an example. If data such as strings, timestamps or integers with a size of 8 bytes are stored, a block can store more than 400 entries. As can be seen from the table, this type of tree can already store up to 64 million entries in the third level and up to 25 billion entries in the fourth level. In practice, B-trees usually only have up to 4 levels.

A key aspect of the B-tree index is its ability to self-balance. When the underlying data changes, either by adding new records or deleting existing records, the tree automatically restructures itself to maintain its balance. This means that the leaf nodes of the B-tree always remain at the same level. This automatic balancing ensures that search performance remains at a consistently high level even when data changes dynamically. However, it should be noted that regular index adjustments can slow down the insertion (INSERT), update (UPDATE) and deletion (DELETE) of data compared to tables without an index.

To illustrate this, let's look again at the previously indexed numerical values ​​from 0 to 28 and add the values ​​13, 15, and 17. By inserting these values, the tree must be restructured all the way to the root. This means that the number ranges must be adjusted at each level and a new leaf must be added. The new structure with the changed values ​​in bold is shown in the following illustration.