Qual é o valor médio da velocidade de busca de dados num índice do tipo B-Tree em sistemas de gestão de bases de dados?

A velocidade média de pesquisa de dados em um índice do tipo B-Tree em um SGBD geralmente é estimada como O(log n), onde n é o número de elementos no índice. Isso ocorre porque um B-Tree é uma árvore balanceada, onde a altura da árvore cresce logaritmicamente em relação ao número de registros.

Por exemplo, se uma tabela tiver um milhão de registros, a pesquisa em um B-Tree levará aproximadamente o logaritmo na base do grau da árvore (normalmente cerca de 100 ou mais) do milhão, o que proporciona um acesso muito rápido em comparação com uma busca linear.

# Pseudocódigo para estimar o número de operações de busca em um B-Tree
import math

n = 1_000_000  # número de elementos
order = 100    # grau do B-Tree (número máximo de filhos por nó)
height = math.ceil(math.log(n, order))
print(f"Número médio de níveis para a busca: {height}")