Pourquoi Google est-il tellement plus rapide qu'une recherche sur disque dur?

251

Lorsque je recherche un fichier sur mon disque dur sous Windows 7 ou Windows XP, le processus prend quelques minutes. Si je remplis un terme de recherche dans Google, la réponse est affichée sur mon écran en millisecondes.

Comment est-il possible pour Google d'effectuer des recherches sur Internet, plusieurs fois plus volumineux que mon disque dur, plus rapidement que mon système d'exploitation ne peut effectuer une recherche sur mon ordinateur? Est-ce seulement une question de puissance de calcul et du bon algorithme?

Arne
la source
99
Avez-vous essayé d'indexer tous les fichiers de votre lecteur et de ne rechercher que l'index? Essayez tout et voyez.
Karan
11
Le bureau Google "utilisé" pour faire de même pour Windows ...
rogerdpack
14
Google effectue une recherche dans les index stockés dans la RAM et non dans les fichiers d'un disque dur.
Ari
13
L'index est important, mais Google utilise également un algorithme de réduction de carte pour effectuer un ensemble d'opérations extrêmement parallèles. Quel que soit le nombre de cœurs que vous avez sur votre ordinateur, je garantis que Google en a plus.
Adam Wuerl
41
Rien n'empêche une implémentation de recherche sur le bureau d'utiliser l'indexation. Cependant , rappelez-vous que Google dispose de suffisamment d’argent pour a) beaucoup de processeurs / serveurs très rapides pour mettre en parallèle une requête; b) beaucoup de RAM très rapide pour ne jamais avoir à accéder à un disque; c) beaucoup de disques durs beaucoup plus rapidement que celui que vous utilisez; d) beaucoup d'ingénieurs très intelligents pour optimiser les algorithmes impliqués. (Par exemple, la mise en cache des résultats pour (beaucoup) de requêtes fréquemment utilisées et bien plus encore.) Ce n'est pas "seulement" une question de l'un ou l'autre, mais de tous ces éléments agissant de concert.
Millimoose

Réponses:

211

Google ne cherche pas sur Internet: il cherche un index. Google possède d'énormes batteries de serveurs qui analysent et indexent en permanence Internet. Ce processus prend beaucoup de temps, tout comme la recherche de votre disque dur non indexé. Dans Windows 7, il existe une option pour indexer vos disques durs. Ce processus prend un certain temps au début, mais une fois lancé, les résultats d’une recherche seront instantanés.

Si vous souhaitez en savoir plus sur le fonctionnement de la recherche Google, vous pouvez lire l'article de Google intitulé " How Search Works " ou l'article " Comment ça marche? Comment fonctionne Google ".

Simon
la source
46
Dernier paragraphe: ce lien fait beaucoup plus autorité et est globalement meilleur.
Ulidtko
4
Pardonnez-moi ma curiosité, mais les systèmes de fichiers n’indexent- ils pas déjà les fichiers sur le disque? Ce que vous voyez dans votre explorateur de fichiers n’est-il pas un simple index de liens vers les secteurs physiques réels du disque? Pourquoi avons-nous alors besoin de faire encore plus d' indexation?
Adi
9
@Adnan l'index des systèmes de fichiers est conçu pour rechercher la position dans laquelle un fichier est stocké sur un support physique. C'est comme l'index d'un livre qui vous indique à quelle page commence un chapitre. Un index de recherche est conçu pour rechercher du contenu. Un bon index de recherche indexe non seulement un nom de fichier, mais également le contenu de types de fichiers connus tels que pdf, doc, html, ... Les index avancés utilisent également des synonymes. Par conséquent, si vous recherchez "voiture", vous obtiendrez des résultats avec le mot "automobile".
Simon le
3
@Adnan, le système de fichiers n'est pas vraiment un "index", mais juste une arborescence de noms de fichiers. La recherche dans un tel arbre n'est pas rapide, car sa structure n'est pas optimisée pour la recherche. OTOH google (et les bases de données) utilise des structures d'index triées spécifiques qui permettent de rechercher rapidement des entrées particulières. Même dans ce cas, toutes les recherches ne peuvent pas bénéficier de cet index et seront plus lentes (plus ou moins longues).
PiRX
8
@Adnan En un sens, l'arborescence FS est optimisée pour la recherche. Il est conçu pour permettre l’adressage des lieux connus. À partir de votre nœud racine, vous n’obtenez que la liste des répertoires et des fichiers situés sous la racine. Chaque répertoire ne connaît que les fichiers qu'il contient et les répertoires situés en dessous. L’accès à un chemin de fichiers connu est très rapide et offre beaucoup de souplesse, mais il n’existe pas de liste globale des fichiers dans lesquels effectuer une recherche. Vous devez toujours descendre dans l'arborescence de répertoires, ce qui permet de nombreuses recherches distinctes.
Phoshi
71

Google, c'est comme chercher dans les pages jaunes une adresse (indexée). La recherche Windows s'apparente à vérifier les numéros des bâtiments (non indexés).

Une autre analogie consisterait à parcourir une bibliothèque bien organisée et un catalogue de cartes, ou simplement à trier une pile de livres non organisée à chaque fois.

Fondamentalement, c'est tout le travail organisationnel effectué avant la recherche qui accélère les choses.

FYI: Lorsque vous recherchez des emplacements indexés, la recherche Windows peut être tout aussi réactive.

Ryan
la source
5
Ou: Scanner un manuel ou regarder dans une table des matières (détaillée)
bobobobo
36

L’activité de Google est la recherche (et la diffusion d’annonces) et elle est très axée sur cela. Google veille à ce que vos données vous soient renvoyées très rapidement:

  • Tout d'abord, il utilise MapReduce et PageRank pour générer un index complet du Web. Il le met à jour régulièrement pour que les résultats soient frais.
  • Cet index est distribué et répliqué sur plusieurs serveurs de Google.
  • Votre requête est répartie sur plusieurs serveurs pour générer les résultats renvoyés. Cela permet au processus d'être hautement parallélisé.
  • Les requêtes et les résultats courants sont mis en cache, ce qui réduit le besoin d'effectuer une recherche.

Consultez ce lien pour plus d'informations sur le fonctionnement de Search

Comparativement, une recherche sur un disque dur sans index doit lire tous les fichiers du lecteur, ce qui peut prendre beaucoup de temps.

De plus, vous pouvez considérer un système de fichiers et un index comme une arborescence. Dans le système de fichiers, la racine de l'arborescence est le dossier de niveau supérieur et il peut contenir des branches (dossiers) ou des feuilles (fichiers) dans ce dossier. Chaque branche peut avoir des sous-branches pour plus de dossiers et des feuilles pour plus de fichiers. Pour rechercher cette structure, vous devez «marcher» sur toutes les branches (et sous-branches) pour trouver la feuille que vous recherchez. Un index renverse cette hiérarchie. La base devient l'alphabet et toutes les sous-branches sont affinées. Les feuilles sont l'emplacement de l'article que vous recherchez. La recherche dans cette structure vous permet d’élaguer (exclure) de grandes sections d’arbre (par exemple, la première lettre de votre terme de recherche vous permet de couper immédiatement 25 autres branches).

Brad Patton
la source
30

Il y a environ 4 ans, je me suis également posé la même question. Mais lorsque je cherchais dans mes recherches, je finis par lire que, outre le fait qu’ils embauchent les meilleurs des meilleurs pour proposer des algorithmes de recherche parmi les plus sophistiqués et tout le reste.

L'un des concepts clés qu'ils ont utilisés est similaire à l'idée de carte réduire, je pense. Vous avez beaucoup d'ordinateurs bon marché dans les fermes. Laissez ces ordinateurs ne disposent que d’environ 80 Go d’espace sur le disque dur et appuyez fort pour obtenir environ 16 Go de RAM, voire mieux 32 Go de RAM sur ces ordinateurs (autant que possible). N'oubliez pas qu'ils sont connectés via un système sophistiqué qu'ils ont conçu. Mais l’idée principale ici est que lorsqu’une requête est soumise, elle est transmise à son système où elle essaiera de rechercher les nouvelles données dans la RAM. Gardez à l'esprit qu'ils ont beaucoup de ces ordinateurs bon marché. Et comme les données sont en RAM, elles se retrouvent beaucoup plus rapidement que sur un disque dur. Mais n'oubliez pas qu'ils ont également un système sophistiqué (indexation et tous ces algorithmes) qui l'aide beaucoup.

Et ces données ne doivent pas nécessairement être récentes, car nous savons tous que Google stocke tout. En ce qui concerne ce qui devrait être dans la RAM, le même principe peut être utilisé avec les arbres splay, gardez ce que les gens recherchent le plus dans la RAM et videz les fichiers les moins recherchés sur le disque dur.

Cette petite idée, associée à leur indexation et à toutes les autres choses que d'autres ont mentionnées dans leurs réponses, pourrait être l'une des raisons pour lesquelles elle est plus rapide qu'une recherche sur disque dur.

  • Le pouvoir de prédire basé sur d'autres recherches.
  • Les données sont probablement en RAM, ce qui, nous le savons tous, est plus rapide.
  • Utilisez plusieurs systèmes pour diviser et conquérir
  • La recherche est leur principale priorité.

Bien sûr, je peux me tromper, mais cela me semblait logique. Et j'étais content de ce que j'ai appris.

Toucher
la source
7
Vous avez mis le doigt sur certaines des choses qui ont échappé aux autres affiches, plus populaires. Google ne fait pas toutes les recherches aussi souvent. Pas du tout sur Internet, ni même dans ses propres caches. De plus, lorsque vous effectuez une recherche sur Google.com, la recherche proprement dite ne se fait pas en temps réel, mais simplement une copie et un affichage rapides des résultats de recherche déjà produits et organisés par Google ces derniers mois. Il est extrêmement compliqué de décrire le processus de production / organisation, mais ce processus peut être appelé de manière approximative "indexation", comme quelqu'un l'a dit.
Joseph Myers
Il est extrêmement compliqué de décrire la production / processus d' organisation ... . Oui, c'est ce que j'appelle la partie sophistiquée. Bravo, vous l'avez bien résumé.
Touchez le
1
@JosephMyers Google indexe en permanence. Effectuez une recherche sur une question posée sur SuperUser plus tôt dans la journée (par exemple, google.com/search?q=google+faster+than+a+hard+drive ) et elle apparaît dans les résultats.
Brad Patton
@Touch, je suis d'accord sur les recherches dans la RAM. C’était le quatrième point de mon post sur la mise en cache
Brad Patton le
@ Brad Patton True. Je devais le mentionner parce que c'était la base de ce que j'avais appris. Et la partie sur l’indexation en permanence, eh bien la partie indexation est une sorte de partie organisatrice. Par conséquent, la déclaration indique que vous recherchez ce qui a été organisé et non ce qui est indexé pour le moment. En ce qui concerne la raison pour laquelle le résultat est affiché, stackoverflow a plus de crédibilité que de nombreux sites Web, il est donc judicieux de l'indexer plus fréquemment. C'est pourquoi ça se voit. Si ce n'était pas pour cela, vous devriez attendre un jour ou deux avant que ce que vous recherchez apparaisse. Je pense que c'est ce que dit M. Joseph Myers.
Appuyez sur
20

Google utilise un système d'indexation extrêmement sophistiqué, des opérations en parallèle et un certain nombre de techniques d'équilibrage de charge non disponibles sur un ordinateur autonome standard. il y a vraiment très peu de similitude entre une recherche Web et une recherche de fichier sur disque dur, et Google optimise fortement pour leurs cas d'utilisation spécifiques.

Frank Thomas
la source
4

En 2004, certains employés de Google ont publié un article: MapReduce et l’ont amélioré des centaines de fois plus tard.

En outre, ils utilisent le système de fichiers Google (GFS), qui est un système de fichiers distribué tel que le système de fichiers Hadoop Distribud (HDFS) et extrêmement optimisé pour leurs objectifs. Aussi, autant que je sache, GFS fonctionne peut-être mille fois plus vite que HDFS .

smttsp
la source
2

J'ai pensé ajouter quelque chose à cela puisque j'avais moi aussi cette question il y a un moment et que j'ai trouvé ces superbes vidéos qui décrivent ce que Google fait à la surface. Intéressant à regarder.

Google sur Youtube 1
Google sur Youtube 2

Il va un peu plus en profondeur, mais pas assez pour que vous vous perdiez dans les détails techniques.

À votre santé.

Mogget
la source
1

Il suffit d'ajouter quelque chose aux merveilleuses réponses ici. Google utilise la mise en cache des expressions de recherche populaires. Les résultats de ces recherches résident dans une mémoire. Donc, si vous recherchez quelque chose qui fait l'objet de nombreuses recherches, les résultats apparaîtront presque immédiatement.

Mellowcandle
la source
0

Pour répondre à la question à un niveau simpliste: imaginez que vous ayez un manuel avec un index de mots-clés à la fin.

Rechercher un disque dur (au moins naïvement) revient à parcourir le livre, page par page, en balayant chaque ligne pour rechercher une occurrence de votre mot clé.

Utiliser un moteur de recherche Internet revient à chercher le mot-clé dans l'index, puis à regarder directement le numéro de page indiqué.

En réalité, c'est beaucoup plus complexe que cela. Par exemple, vous rechercherez généralement sur votre disque dur des types d’informations autres que l’Internet. Mais l'essentiel, c'est que le moteur de recherche utilise un index. Il a déjà parcouru le "livre" mot à mot et il a dressé une liste de ces mots et indique où les trouver. Il a organisé la liste de manière à pouvoir y rechercher très rapidement des éléments. .

Par exemple, pensez à l'organisation d'un index dans un livre. Premièrement, il est généralement trié par ordre alphabétique, et deuxièmement, il peut avoir des en-têtes de lettres. Lorsque vous recherchez un mot dans l'index, vous pouvez voir immédiatement la liste des mots commençant par la lettre souhaitée. Et comme la liste est triée, il est facile de trouver le mot que vous voulez dans la liste, ou de dire rapidement s'il manque.

Donc, pour résumer, c'est comme si votre disque dur avait juste un livre, alors que le moteur de recherche avait l'index. Cependant, comme l'ont déjà souligné d'autres personnes, il est possible d'utiliser un logiciel pour indexer votre disque dur. Vous pouvez ensuite utiliser l'index au lieu de l'intégralité.

Mwfearnley
la source
-1

Je suppose que l’une des raisons pour lesquelles Google a émergé Auto Completeet utilisé AJAXest le problème de la vitesse. Désormais, lorsque vous tapez, les mots sont envoyés en arrière-plan afin que Google puisse effectuer une partie du travail pendant que vous n’avez pas encore terminé. Les index sont également basés sur plusieurs combinaisons de mots (que vous pouvez trouver sous forme de suggestions au bas de la page). Actuellement, la vitesse du réseau est supérieure à celle des disques durs et une grande partie de ces index réside probablement dans la RAM des serveurs de leur batterie.

Xaqron
la source