Como o tempo de consulta do banco de dados é dimensionado de acordo com o tamanho do banco de dados?

Question

Estive recentemente na OEIS (Enciclopédia Online de Sequências Inteiras), tentando procurar uma sequência específica que eu tinha.

Agora, esse banco de dados é bastante grande.O site afirma que se 2006 (!5 anos) fosse impressa, ocuparia 750 volumes de texto.

Tenho certeza de que esse é o mesmo tipo de problema que o Google também precisa resolver.Mas eles também possuem um sistema distribuído onde aproveitam o balanceamento de carga.

No entanto, negligenciando o balanceamento de carga, quanto tempo leva para fazer uma consulta em comparação com o tamanho do banco de dados?

Ou, em outras palavras, qual é a complexidade temporal de uma consulta em relação ao tamanho do banco de dados?

Editar:Para tornar as coisas mais específicas, suponha que a consulta de entrada esteja simplesmente procurando uma sequência de números como:

1, 4, 9, 16, 25, 36, 49

Answer 1

Depende fortemente da consulta, estrutura do banco de dados, contenção e assim por diante.Mas, em geral, a maioria dos bancos de dados encontrará uma maneira de usar um índice, e esse índice será algum tipo de estrutura em árvore (veja http://en.wikipedia.org/wiki/B-tree para uma opção), nesse caso o tempo de acesso é proporcional a log(n), ou então um hash, nesse caso o tempo de acesso é proporcional a O(1) em média (veja http://en.wikipedia.org/wiki/Hash_function#Hash_tables para obter uma explicação de como eles funcionam).

Portanto, a resposta normalmente é O(1) ou O(log(n)) dependendo do tipo de estrutura de dados usada.

Isso pode fazer você se perguntar por que nem sempre usamos funções hash.Existem vários motivos.As funções hash dificultam a recuperação de intervalos de valores.Se a função hash não distribuir bem os dados, é possível que o tempo de acesso se torne O(n).Hashes precisam ser redimensionados ocasionalmente, o que é potencialmente muito caro.E log(n) cresce lentamente o suficiente para que você possa tratá-lo como razoavelmente próximo da constante em todos os conjuntos de dados práticos.(De 1.000 a 1 petabyte, varia por um fator de 5.) E frequentemente os dados solicitados ativamente mostram algum tipo de localidade, cujas árvores fazem um trabalho melhor em manter na RAM.Como resultado, as árvores são vistas com mais frequência na prática.(Embora hashes não sejam raros.)

Answer 2

Isso depende de vários fatores, incluindo a implementação do mecanismo de banco de dados, estratégia de indexação, especificações da consulta, hardware disponível, configuração do banco de dados, etc.

Não há como responder a uma pergunta tão geral.

Answer 3

Um banco de dados adequadamente projetado e implementado com terabytes de dados pode, na verdade, superar um pequeno banco de dados mal projetado (especialmente um sem indexação e que usa consultas não sargáveis ​​com mau desempenho e coisas como subconsultas correlacionadas).É por isso que qualquer pessoa que espera ter grandes quantidades de dados precisa contratar um especialista em design de bancos de dados grandes para fazer o design inicial, o mais tardar, quando o banco de dados for grande.Você também pode precisar investir no tipo de equipamento necessário para lidar com o tamanho.