Why is a B-tree index most commonly used and what is its algorithmic complexity?

B-tree index is widely used in databases due to its balanced structure, which provides efficient search, insertion, and deletion of data. The main reason for the popularity of B-trees is their ability to maintain sorted data and perform range queries quickly.

Algorithmic complexity of basic operations in a B-tree:

• Search: O(log n)
• Insertion: O(log n)
• Deletion: O(log n)

Where n is the number of elements in the index. This logarithmic complexity is achieved because the tree is balanced, and the height of the tree grows slowly as data increases.