Why Using B-tree Indexing in SQL?

A B-tree index is a type of tree data structure used in databases to improve search efficiency. It is called a B-tree because it is a balanced tree, meaning that all leaf nodes are at the same level, and the branching factor is kept relatively low to ensure fast access to leaf nodes.

The B-tree index stores data in sorted order, which makes it very efficient for range queries and equality checks. In MySQL, the default index type is BTREE.

Here is an example of a simple B-tree index:

       [5,10,20,25,30,40,45,50,60]
           /    |        |      \
        /       |        |        \
    [5,10]  [20,25,30] [40,45]   [50,60]

In this example, we have a sorted list of values [5,10,20,25,30,40,45,50,60] which represents the index. The tree is balanced, and each node has a maximum of four children. Each internal node stores a range of values that correspond to the range of values stored in its children nodes.

For example, the internal node [20,25,30] represents the range of values from 20 to 30, and its children nodes store values in that range. The leaf nodes contain pointers to the actual data in the database, and their values are also sorted.

Here is another example of the inner structure of a B-tree: