What is the average search speed in a B-Tree index in database management systems?

The average search speed in a B-Tree index in a DBMS is usually estimated as O(log n), where n is the number of elements in the index. This is because a B-Tree is a balanced tree, where the height of the tree grows logarithmically with the number of records.

For example, if a table has a million records, searching with a B-Tree will take approximately the logarithm base the order of the tree (usually 100 or more) of a million, which provides very fast access compared to linear search.

# Pseudocode for estimating the number of search operations in a B-Tree
import math

n = 1_000_000  # number of elements
order = 100    # order of the B-Tree (maximum number of children per node)
height = math.ceil(math.log(n, order))
print(f"Average number of levels for search: {height}")