Questão Por que o Google é muito mais rápido que uma pesquisa de disco rígido?


Quando pesquiso um arquivo no meu HD no Windows 7 ou no Windows XP, leva alguns minutos para concluir o processo. Se eu preencher um termo de pesquisa no Google, a resposta estará na minha tela em milissegundos

Como é possível que o Google pesquise na Internet, que é muitas vezes maior que meu disco rígido, mais rápido do que o meu sistema operacional pode pesquisar no meu computador? É apenas uma questão de poder de computação e o algoritmo certo?


247


origem


Você já tentou indexar todos os arquivos em sua unidade e pesquisar apenas o índice? Experimentar Tudo e veja. - Karan
Google desktop "usado" para fazer isso para o windows também ... - rogerdpack
O Google pesquisa por índices armazenados na RAM, não por arquivos em um disco rígido. - Ari
O índice é importante, mas o Google também usa um algoritmo de redução de mapa para conduzir um conjunto massivamente paralelo de operações. Não importa quantos núcleos você tenha em seu computador, garanto que o Google tem mais. - Adam Wuerl
Não há nada que impeça uma implementação de pesquisa na área de trabalho de usar a indexação. Contudolembre-se de que o Google tem dinheiro suficiente para a) muitas CPUs / servidores muito rápidos para paralelizar uma consulta; b) muita RAM muito rápida para evitar ter que acessar um disco nunca; c) muitos discos rígidos muito mais rápidos do que o que você usa; d) muitos engenheiros muito inteligentes para otimizar os algoritmos envolvidos. (Por exemplo, armazenar em cache os resultados de (muitas) consultas usadas com frequência e muito mais.) Não é "apenas" uma questão de qualquer uma delas, todas elas atuando em conjunto. - millimoose


Respostas:


O Google não está pesquisando na internet: está pesquisando um índice. O Google tem enormes fazendas de servidores que estão constantemente digitalizando e indexando a internet. Este processo leva muito tempo, assim como a busca de seu disco rígido não indexado. No Windows 7, há uma opção para indexar seus discos rígidos. Esse processo leva algum tempo no início, mas uma vez em funcionamento, os resultados de uma pesquisa serão instantâneos.

Se você quiser saber mais sobre como funciona a pesquisa do Google, leia o artigo do Google "Como funciona a pesquisa"ou leia o artigo"Como funciona o material: como o Google funciona".


210



Último parágrafo: esse link é muito mais autoritário e, em geral, melhor. - ulidtko
Perdoe minha curiosidade, mas não sistemas de arquivos já indexar os arquivos no disco? O que você vê em seu explorador de arquivos não é um mero índice de links para os setores físicos reais no disco? Por que, então, precisamos fazer ainda mais indexação? - Adi
@Adnan o índice de sistemas de arquivos é projetado para encontrar a posição em que um arquivo é armazenado em uma mídia física. É como o índice de um livro que informa em qual página um capítulo começa. Um índice de pesquisa é projetado para encontrar conteúdo. Um bom índice de pesquisa indexa não apenas o nome de um arquivo, mas também o conteúdo de tipos de arquivo conhecidos como pdf, doc, html, ... Índices avançados também usam sinônimos, por isso, se você pesquisar por "carro", ele também poderá encontrar resultados com a palavra "automóvel". - Simon
@Adnan, sistema de arquivos não é realmente um "índice", apenas uma árvore de nomes de arquivos. A pesquisa dessa árvore não é rápida, porque a estrutura não está otimizada para pesquisa. OTOH google (e bancos de dados) usa estruturas específicas de índices ordenados, o que torna a busca por uma entrada particular muito rápida. Mesmo assim, nem todas as pesquisas podem se beneficiar de tal índice e serão lentas (er). - PiRX
@Adnan Em certo sentido, a árvore FS é otimizada contra procurando. Ele foi projetado para permitir o endereçamento de locais conhecidos. A partir do seu nó raiz, tudo que você obtém é uma lista de diretórios e arquivos sob a raiz. Todo diretório só conhece os arquivos e os diretórios abaixo dele. Acessar um caminho de arquivo conhecido é muito rápido e oferece muita flexibilidade, mas não existe uma lista global de arquivos para pesquisar. Você sempre deve descer pela árvore de diretórios e isso faz com que você faça várias pesquisas distintas. - Phoshi


O Google é como procurar nas páginas amarelas por um endereço (indexado). A pesquisa do Windows é semelhante a verificar números em edifícios (não indexados).

Outra analogia seria examinar uma biblioteca bem organizada e um catálogo de cartões, ou simplesmente vasculhar uma pilha desorganizada de livros toda vez.

Fundamentalmente, é todo o trabalho organizacional feito antes da busca que o torna rápido.

FYI: Ao pesquisar locais indexados, a pesquisa do Windows pode ser tão responsiva quanto.


71



Ou: Digitalizar um livro didático vs consultar um (detalhado) índice - bobobobo


O negócio do Google é pesquisar (e veicular anúncios) e é muito focado nisso. Há diversas ações que o Google faz para garantir que os dados sejam devolvidos a você com muita rapidez:

  • Primeiro usa MapReduce e Ranking da página para gerar um índice abrangente da World Wide Web. Ele atualiza isso regularmente para que os resultados sejam novos.
  • Esse índice é distribuído e replicado nos vários servidores do Google
  • Sua consulta é dividida em vários servidores para criar os resultados retornados. Isso permite que o processo seja altamente paralelizado.
  • Consultas e resultados comuns são armazenados em cache, reduzindo a necessidade de realizar a pesquisa.

Veja este link para mais informações sobre Como funciona a pesquisa

Comparativamente, uma pesquisa no disco rígido sem um índice precisa ler todos os arquivos da unidade e isso pode levar muito tempo.

Além disso, você pode pensar em um sistema de arquivos e um índice como uma árvore. No sistema de arquivos, a raiz da árvore é a pasta de nível superior e pode ter ramificações (pastas) ou folhas (arquivos) nessa pasta. Cada filial pode ter sub-filiais para mais pastas e deixa para mais arquivos. Para pesquisar essa estrutura, você precisa percorrer todos os ramos (e sub-ramos) para encontrar a folha que está procurando. Um índice inverte essa hierarquia. A base se torna o alfabeto e todos os sub-ramos refinam ainda mais isso. As folhas são a localização do item que você está procurando. A pesquisa nessa estrutura permite remover (excluir) grandes seções da árvore (por exemplo, a primeira letra do seu termo de pesquisa permite que você apare 25 outras ramificações imediatamente).


36





Há cerca de 4 anos também me fiz a mesma pergunta. Mas, enquanto eu pesquisava minhas pesquisas, acabei lendo que além do fato de que eles contratam os melhores dos melhores para criar alguns dos algoritmos de busca mais sofisticados e tudo isso.

Um dos principais projetos que eles usaram é semelhante à ideia de reduzir mapa, eu acho. Você tem muitos computadores baratos em fazendas. Deixe esses computadores terem apenas cerca de 80 gigabytes de espaço em disco rígido e esforçar-se para ter cerca de 16 gigabytes de RAM ou até mesmo 32 gig de RAM nesses computadores (tanto quanto possível). Lembre-se de que eles estão conectados por meio de um sistema sofisticado que eles projetaram. Mas a idéia chave aqui é que, quando uma consulta é enviada, ela é passada para o sistema, onde tentará pesquisar os dados novos na RAM. Tenha em mente que eles têm muitos desses computadores baratos. E como os dados estão na RAM, eles são encontrados muito mais rapidamente do que seriam em um disco rígido. Mas não se esqueça que eles também têm um sistema sofisticado (indexação e todos esses algoritmos) que ajuda muito.

E esses dados não precisam ser novos, porque todos sabemos que o Google armazena tudo. Então, quanto ao que deveria estar na RAM, o mesmo princípio com árvores splay pode ser usado, manter o que sempre as pessoas estão pesquisando mais em RAM e liberar o material menos pesquisado no disco rígido.

Essa pequena ideia juntamente com sua indexação e todas as outras coisas que os outros mencionaram em suas respostas, pode ser uma das razões pelas quais é mais rápida do que uma pesquisa no disco rígido.

  • O poder de prever com base em outras pesquisas.
  • Os dados são mais prováveis ​​na RAM, e todos nós sabemos que é mais rápido.
  • Use vários sistemas para dividir e conquistar
  • A pesquisa é sua principal prioridade.

Claro que eu poderia estar errado, mas isso fazia sentido para mim. E eu fiquei feliz com o que aprendi.


30



Você pregou em algumas das coisas que os outros cartazes mais populares perderam. O Google não pesquisa tudo com tanta frequência. Definitivamente não em toda a internet, e nem mesmo tudo em seus próprios caches. Além disso, quando você pesquisa no Google.com, a pesquisa real não está acontecendo em tempo real, apenas uma cópia e exibição rápida dos resultados da pesquisa que já foram produzidos e organizados nos últimos meses pelo Google. É extremamente complicado descrever o processo de produção / organização, mas pode ser vagamente chamado de "indexação" como alguém disse. - Joseph Myers
É extremamente complicado descrever o processo de produção / organização .... Sim, isso é o que eu chamo de parte sofisticada disso. Polegares para cima, você resumiu bem. - Touch
@JosephMyers indexa constantemente o Google. Faça uma pesquisa em uma pergunta feita no SuperUser no início do dia (por exemplo, google.com/search?q=google+faster+than+a+hard+drive) e aparece nos resultados. - Brad Patton
@Touch Eu concordo com pesquisas na RAM. Este foi o quarto ponto no meu post sobre cache - Brad Patton
@Brad Patton True. Eu tive que mencionar isso porque era a base do que eu aprendi. E a parte sobre indexar constantemente, bem, a parte de indexação é o tipo de parte organizadora. Portanto, a afirmação diz que você procura o que foi organizado e não o que está sendo indexado no momento. Quanto ao motivo pelo qual o resultado está aparecendo, o stackoverflow tem mais credibilidade do que muitos websites, portanto, é bom indexá-lo com mais frequência. É por isso que aparece. Se não fosse por isso, você teria que esperar um ou dois dias antes do que você procura. Eu acho que é isso que o Sr. JosephMyers está dizendo. - Touch


O Google usa um sistema de indexação extremamente sofisticado, operações paralelas e várias técnicas de balanceamento de carga não disponíveis para um computador autônomo padrão. há muito pouca semelhança entre uma pesquisa na Web e uma pesquisa de arquivos no disco rígido, e o Google otimiza bastante para os casos de uso específicos.


20





Em 2004, alguns funcionários do Google publicaram um artigo: MapReduce e a partir desse momento melhoraram centenas de vezes.

Além disso, eles usam Sistema de arquivos do Google (GFS) que é um sistema de arquivos distribuídos como Sistema de arquivos do Hadoop Distribud (HDFS) e extremamente otimizado para seus propósitos. Também, tanto quanto eu sei, GFS funciona talvez milhares de vezes mais rápido do que HDFS.


4





Pensei em acrescentar isso, pois também tive essa pergunta há algum tempo e encontrei esses ótimos vídeos que descrevem o que o Google faz na superfície. Interessante de assistir.

Google no Youtube 1
Google no Youtube 2

Ele vai um pouco mais fundo, mas não profundo o suficiente para que você se perca em detalhes técnicos.

Felicidades.


2





Apenas adicionando algo às maravilhosas respostas aqui. O Google usa o cache de frases de pesquisa populares. Os resultados dessas pesquisas residem em uma memória. Então, se você procurar algo muito pesquisado, os resultados aparecerão quase imediatamente.


1





Para responder à pergunta em um nível simplista: imagine que você tenha um livro com um índice de palavras-chave na parte de trás.

Pesquisando um disco rígido (ingenuamente, pelo menos) é como percorrer o livro, página por página, digitalizando cada linha para uma ocorrência de sua palavra-chave.

Usar um mecanismo de pesquisa da Internet é como procurar a palavra-chave no índice e, em seguida, virar diretamente para o número da página que ela fornece.

Na realidade, é claro, é muito mais complexo do que isso. Por exemplo, você normalmente procuraria em seu disco rígido por diferentes tipos de informações além da Internet. Mas a coisa básica a ser retirada é que o mecanismo de pesquisa está usando um índice. Ele já passou pelo "livro", palavra por palavra, e compilou uma lista dessas palavras junto com onde encontrá-las, e organizou a lista de tal forma que ela pode procurar coisas muito rapidamente. .

Por exemplo, pense na organização de um índice em um livro. Em primeiro lugar, geralmente é classificado em ordem alfabética e, em segundo lugar, pode ter títulos de letras. Quando você procura uma palavra no índice, pode ver imediatamente a lista de palavras que começam com a letra que você deseja. E como a lista está classificada, é fácil encontrar a palavra desejada na lista ou informar rapidamente se está faltando.

Então, para resumir, é como se o seu disco rígido tivesse um livro, enquanto o mecanismo de busca tivesse o índice. Embora, como outros apontaram, é possível usar o software para indexar seu disco rígido e, em seguida, você pode usar o índice em vez da coisa toda.


0





Eu acho que uma das razões pelas quais o Google surgiu Auto Complete e usado AJAX foi problema de velocidade. Agora, quando você está digitando, as palavras são enviadas em segundo plano para que o Google possa fazer parte do trabalho enquanto você ainda não terminou. Também os índices são baseados em múltiplas combinações de palavras (que você pode encontrar como sugestões na parte inferior da página). Atualmente, a velocidade da rede é maior do que a dos discos rígidos e, provavelmente, muitos desses índices residem na RAM dos servidores em seu farm.


-1