Qual é a complexidade temporal de procurar um registro pelo seu índice na base de dados?

A complexidade temporal de procurar um registo pelo seu índice numa base de dados é geralmente O(log n), se uma árvore de índice equilibrada, como uma árvore B, for utilizada, o que é comum em sistemas de gestão de bases de dados relacionais.

Os índices permitem encontrar registos rapidamente sem percorrer toda a tabela (o que seria O(n)). Com um índice, a procura reduz-se a percorrer a árvore, o que dá uma complexidade logarítmica.

Em alguns casos, por exemplo, ao usar índices de hash, a procura pode estar próxima de O(1), mas isso depende da implementação e do tipo de índice.

Assim, graças aos índices, a procura por chave numa base de dados é geralmente eficiente e escala bem.