Warum ist Google so viel schneller als eine Festplattensuche?

251

Wenn ich in Windows 7 oder Windows XP eine Datei auf meiner Festplatte suche, dauert es einige Minuten, bis der Vorgang abgeschlossen ist. Wenn ich in Google einen Suchbegriff eingebe, wird die Antwort in Millisekunden auf meinem Bildschirm angezeigt

Wie kann Google im Internet suchen, das um ein Vielfaches größer ist als meine Festplatte, und zwar schneller, als mein Betriebssystem meinen Computer durchsuchen kann? Geht es nur um Rechenleistung und den richtigen Algorithmus?

windows hard-drive windows-search google-search Arne
quelle
99
Haben Sie versucht, alle Dateien auf Ihrem Laufwerk zu indizieren und nur den Index zu durchsuchen? Alles ausprobieren und sehen.
Karan
11
Google Desktop "verwendet", um das für Windows auch zu tun ...
Rogerdpack
14
Google durchsucht die im RAM gespeicherten Indizes und nicht die Dateien auf der Festplatte.
Ari
13
Der Index ist wichtig, aber Google verwendet auch einen Kartenreduzierungsalgorithmus, um eine Vielzahl paralleler Operationen durchzuführen. Egal wie viele Kerne Sie in Ihrem Computer haben, ich garantiere, dass Google mehr hat.
Adam Wuerl
41
Es steht einer Implementierung der Desktopsuche nicht entgegen, die Indizierung zu verwenden. Denken Sie jedoch daran, dass Google über genügend Bargeld verfügt, um a) viele sehr schnelle CPUs / Server für die Parallelisierung einer Abfrage bereitzustellen. b) viel sehr schneller RAM, um zu vermeiden, dass jemals auf eine Festplatte zugegriffen werden muss; c) viele Festplatten viel schneller als die, die Sie verwenden; d) viele sehr kluge Ingenieure, um die beteiligten Algorithmen zu optimieren. (ZB das Zwischenspeichern der Ergebnisse für (viele) häufig verwendete Abfragen und vieles mehr.) Es ist nicht "nur" eine Frage von beidem, es ist alles, was zusammenspielt.
Millimoose

Antworten:

211

Google durchsucht nicht das Internet, sondern einen Index. Google hat riesige Serverfarmen, die ständig das Internet durchsuchen und indizieren. Dieser Vorgang nimmt viel Zeit in Anspruch, genau wie das Durchsuchen Ihrer nicht indizierten Festplatte. In Windows 7 gibt es eine Option zum Indizieren Ihrer Festplatten. Dieser Vorgang dauert zunächst einige Zeit, aber sobald er ausgeführt wird, werden die Ergebnisse einer Suche sofort angezeigt.

Wenn Sie mehr darüber wissen , wie die Google - Suche funktioniert , wie Sie Google-Artikel lesen „ So funktioniert die Suche “ oder lesen Sie den Artikel „ How Stuff Works: Google Works “.

Simon
quelle
46
Letzter Absatz: Dieser Link ist viel maßgeblicher und insgesamt besser.
Ulidtko
4
Entschuldigen Sie meine Neugier, aber indizieren Dateisysteme die Dateien auf der Festplatte nicht bereits? Ist das, was Sie in Ihrem Datei-Explorer sehen, nicht nur ein Index von Links zu den tatsächlichen physischen Sektoren auf der Festplatte? Warum müssen wir dann noch mehr indizieren?
Adi
9
@Adnan Der Dateisystemindex soll die Position ermitteln, an der eine Datei auf einem physischen Datenträger gespeichert ist. Es ist wie der Index eines Buches, der Ihnen sagt, auf welcher Seite ein Kapitel beginnt. Ein Suchindex dient zum Auffinden von Inhalten. Ein guter Suchindex indiziert nicht nur einen Dateinamen, sondern auch den Inhalt bekannter Dateitypen wie pdf, doc, html, ... Fortgeschrittene Indizes verwenden auch Synonyme. Wenn Sie also nach "Auto" suchen, finden Sie möglicherweise auch Ergebnisse mit das Wort "Automobil".
Simon
3
@Adnan, das Dateisystem ist eigentlich kein "Index", sondern nur ein Baum von Dateinamen. Das Durchsuchen eines solchen Baums ist nicht schnell, da seine Struktur nicht für das Suchen optimiert ist. OTOH google (und Datenbanken) verwendet spezielle sortierte Indexstrukturen, mit denen blitzschnell nach bestimmten Einträgen gesucht werden kann. Selbst dann können nicht alle Suchvorgänge von einem solchen Index profitieren und sind langsam (er).
PiRX
8
@Adnan In gewissem Sinne ist der FS - Baum optimiert gegen Suche. Es wurde entwickelt, um die Adressierung bekannter Standorte zu ermöglichen. Alles, was Sie von Ihrem Root-Knoten erhalten, ist eine Liste von Verzeichnissen und Dateien unter root. Jedes Verzeichnis kennt nur die darin enthaltenen Dateien und die Verzeichnisse darunter. Der Zugriff auf einen bekannten Dateipfad ist sehr schnell und bietet viel Flexibilität, es gibt jedoch keine globale Auflistung der zu durchsuchenden Dateien. Sie müssen immer durch den Verzeichnisbaum absteigen, und das sorgt für eine Menge eindeutiger Suchvorgänge.
Phoshi
71

Google ist wie das Durchsuchen der gelben Seiten nach einer Adresse (indiziert). Die Windows-Suche ähnelt dem Herumfahren und Überprüfen von Zahlen in Gebäuden (nicht indiziert).

Eine andere Analogie wäre das Durchsuchen einer gut organisierten Bibliothek und eines Kartenkatalogs oder jedes Mal nur das Durchsuchen eines unorganisierten Bücherstapels.

Grundsätzlich ist es die ganze organisatorische Arbeit, die vor der Suche erledigt wurde, die es schnell macht.

Zu Ihrer Information: Beim Durchsuchen indizierter Speicherorte kann die Windows-Suche genauso ansprechend sein.

Ryan
quelle
5
Oder: Scannen eines Lehrbuchs oder
Einsehen
36

Googles Geschäft ist die Suche (und das Schalten von Anzeigen) und es ist sehr darauf ausgerichtet. Google unternimmt eine Reihe von Maßnahmen, um sicherzustellen, dass die Daten sehr schnell an Sie zurückgesandt werden:

  • Zunächst werden MapReduce und PageRank verwendet , um einen umfassenden Index des World Wide Web zu erstellen. Es aktualisiert dies regelmäßig, damit die Ergebnisse frisch sind.
  • Dieser Index wird auf den vielen Servern von Google verteilt und repliziert
  • Ihre Abfrage wird auf mehrere Server aufgeteilt, um die zurückgegebenen Ergebnisse zu erstellen. Dadurch kann der Prozess stark parallelisiert werden.
  • Häufige Abfragen und Ergebnisse werden zwischengespeichert, sodass die Suche überhaupt nicht mehr ausgeführt werden muss.

Weitere Informationen zur Funktionsweise von Search finden Sie unter diesem Link

Vergleichsweise muss bei einer Festplattensuche ohne Index jede Datei auf der Festplatte durchgelesen werden, was viel Zeit in Anspruch nehmen kann.

Außerdem können Sie sich sowohl ein Dateisystem als auch einen Index als Baum vorstellen. Im Dateisystem ist der Stamm des Baums der Ordner der obersten Ebene und er kann Zweige (Ordner) oder Blätter (Dateien) in diesem einen Ordner haben. Jeder Zweig kann Unterzweige für mehr Ordner und Blätter für mehr Dateien haben. Um diese Struktur zu durchsuchen, müssen Sie alle Zweige (und Unterzweige) „durchgehen“, um das Blatt zu finden, nach dem Sie suchen. Ein Index dreht diese Hierarchie um. Die Basis wird zum Alphabet und alle Unterzweige verfeinern dies weiter. Die Blätter sind der Ort des Artikels, den Sie suchen. Durch Durchsuchen dieser Struktur können Sie große Baumabschnitte beschneiden (ausschließen) (z. B. können Sie mit dem ersten Buchstaben Ihres Suchbegriffs 25 andere Zweige sofort abschneiden).

Brad Patton
quelle
30

Vor ungefähr 4 Jahren habe ich mir die gleiche Frage gestellt. Aber als ich meine Nachforschungen anstellte, las ich schließlich, dass sie neben der Tatsache, dass sie die Besten der Besten einstellen, einige der ausgefeiltesten Suchalgorithmen und all das zu entwickeln.

Eines der wichtigsten verwendeten Designs ähnelt meiner Meinung nach der Idee der Kartenreduzierung. Auf Farmen gibt es viele billige Computer. Lassen Sie diese Computer nur ca. 80 GB Festplattenspeicher haben und arbeiten Sie hart, um ca. 16 GB RAM oder noch besser 32 GB RAM auf diesen Computern zu haben (so viel wie möglich). Denken Sie daran, dass sie durch ein ausgeklügeltes System verbunden sind, das sie entworfen haben. Die Schlüsselidee hierbei ist jedoch, dass eine gesendete Abfrage an ihr System übergeben wird, wo sie versucht, die neuen Daten im RAM zu durchsuchen. Denken Sie daran, sie haben viele dieser billigen Computer. Und da sich die Daten im RAM befinden, werden sie viel schneller gefunden als auf einer Festplatte. Aber vergessen Sie nicht, dass sie auch ein ausgeklügeltes System (Indexierung und all diese Algorithmen) haben, das sehr hilfreich ist.

Und diese Daten müssen nicht unbedingt aktuell sein, da wir alle wissen, dass Google alles speichert. Um festzustellen, was sich im RAM befinden soll, kann dasselbe Prinzip wie bei Splay-Bäumen angewendet werden. Stellen Sie sicher, dass die meisten Benutzer im RAM suchen, und speichern Sie die am wenigsten gesuchten Daten auf der Festplatte.

Diese kleine Idee in Verbindung mit ihrer Indizierung und all den anderen Dingen, die andere in ihren Antworten erwähnt haben, könnte einer der Gründe sein, warum sie schneller ist als eine Festplatten-Suche.

  • Die Vorhersagekraft basierend auf anderen Suchanfragen.
  • Die Daten befinden sich höchstwahrscheinlich im RAM, von dem wir alle wissen, dass es schneller ist.
  • Verwenden Sie mehrere Systeme, um zu teilen und zu erobern
  • Das Suchen ist ihre Hauptpriorität.

Natürlich könnte ich mich irren, aber das ergab für mich einen Sinn. Und ich war glücklich mit dem, was ich gelernt habe.

Berühren
quelle
7
Sie haben einige Dinge verinnerlicht, die die anderen, populäreren Plakate übersehen haben. Google durchsucht nicht alles so oft. Auf jeden Fall nicht im ganzen Internet und auch nicht alles in seinen eigenen Caches. Wenn Sie auf Google.com suchen, geschieht die eigentliche Suche nicht in Echtzeit, sondern nur durch schnelles Kopieren und Anzeigen von Suchergebnissen, die bereits in den letzten Monaten von Google erstellt und organisiert wurden. Es ist extrem kompliziert, den Produktions- / Organisationsprozess zu beschreiben, aber man kann es vage als "Indizieren" bezeichnen, wie jemand sagte.
Joseph Myers
Es ist äußerst kompliziert, den Produktions- / Organisationsprozess zu beschreiben . Ja, das nenne ich den raffinierten Teil davon. Daumen hoch, du hast es gut zusammengefasst.
Berühren Sie den
1
@ JosephMyers Google-Indizes ständig. Führen Sie eine Suche nach einer Frage durch, die SuperUser zu einem früheren Zeitpunkt gestellt hat (z. B. google.com/search?q=google+faster+than+a+hard+drive ), und die Frage wird in den Ergebnissen angezeigt .
Brad Patton
@Touch Ich stimme der Suche im RAM zu. Dies war der vierte Punkt in meinem Beitrag über Caching
Brad Patton
@ Brad Patton Wahr. Ich musste es erwähnen, weil es die Grundlage für das war, was ich gelernt habe. Und der Teil über die ständige Indizierung, der Teil über die Indizierung ist eine Art organisierender Teil. Daher gilt die Aussage, dass Sie suchen, was organisiert wurde und nicht, was gerade indiziert wird. Was den Grund für das Ergebnis angeht, so ist Stackoverflow glaubwürdiger als viele andere Websites. Daher ist es sinnvoll, es häufiger zu indizieren. Deshalb taucht es auf. Wäre dies nicht der Fall, müssten Sie ein oder zwei Tage warten, bis Ihre Suche angezeigt wird. Ich denke, das sagt Herr JosephMyers.
Berühren Sie den
20

Google verwendet ein äußerst ausgeklügeltes Indizierungssystem, parallele Vorgänge und eine Reihe von Lastausgleichstechniken, die für einen Standalone-Standardcomputer nicht verfügbar sind. Es gibt wirklich sehr wenig Ähnlichkeit zwischen einer Websuche und einer Suche nach Festplattendateien, und Google optimiert stark für ihre spezifischen Anwendungsfälle.

Frank Thomas
quelle
4

Im Jahr 2004 haben einige Google-Mitarbeiter einen Artikel veröffentlicht: MapReduce. Von da an haben sie diesen Artikel hundertfach verbessert.

Außerdem verwenden sie Google File System (GFS) , ein verteiltes Dateisystem wie das Hadoop Distribud File System (HDFS), das für ihre Zwecke äußerst optimiert ist. Soweit ich weiß, arbeitet GFS vielleicht tausendmal schneller als HDFS .

smttsp
quelle
2

Ich dachte, ich würde noch etwas hinzufügen, da ich auch diese Frage vor einiger Zeit hatte und diese tollen Videos gefunden habe, die beschreiben, was Google an der Oberfläche macht. Interessant zu sehen.

Google auf Youtube 1
Google auf Youtube 2

Er geht ein bisschen tiefer, aber nicht tief genug, dass man sich in technischen Details verliert.

Prost.

Mogget
quelle
1

Fügen Sie hier einfach etwas zu den wunderbaren Antworten hinzu. Google verwendet die Zwischenspeicherung beliebter Suchbegriffe. Die Ergebnisse dieser Suchvorgänge befinden sich in einem Speicher. Wenn Sie also nach etwas suchen, das häufig durchsucht wird, werden die Ergebnisse fast sofort angezeigt.

Mellowcandle
quelle
0

Um die Frage auf einer vereinfachenden Ebene zu beantworten: Stellen Sie sich vor, Sie haben ein Lehrbuch mit einem Stichwortindex auf der Rückseite.

Das Durchsuchen einer Festplatte (zumindest naiv) gleicht einem seitenweisen Durchsuchen des Buchs, bei dem jede Zeile nach einem Vorkommen Ihres Schlüsselworts durchsucht wird.

Das Verwenden einer Internet-Suchmaschine bedeutet, das Schlüsselwort im Index nachzuschlagen und dann direkt zur angegebenen Seitenzahl zu wechseln.

In Wirklichkeit ist es natürlich viel komplexer. Beispielsweise durchsuchen Sie normalerweise Ihre Festplatte nach anderen Arten von Informationen als im Internet. Aber das Grundlegende, was man wegnehmen sollte, ist, dass die Suchmaschine einen Index verwendet. Es hat das "Buch" bereits Wort für Wort durchgesehen, eine Liste dieser Wörter zusammengestellt und die Liste so organisiert, dass es die darin enthaltenen Informationen sehr schnell nachschlagen kann .

Denken Sie beispielsweise an die Organisation eines Index in einem Buch. Erstens ist es normalerweise alphabetisch sortiert, und zweitens kann es Buchstabenüberschriften haben. Wenn Sie ein Wort im Index nachschlagen, sehen Sie sofort die Liste der Wörter, die mit dem gewünschten Buchstaben beginnen. Und da die Liste sortiert ist, ist es einfach, das gewünschte Wort in der Liste zu finden oder schnell zu erkennen, ob es fehlt.

Zusammenfassend ist es so, als hätte Ihre Festplatte nur ein Buch, während die Suchmaschine den Index hat. Obwohl einige andere darauf hingewiesen haben, ist es möglich, Software zum Indizieren Ihrer Festplatte zu verwenden, und dann können Sie den Index anstelle des Ganzen verwenden.

mwfearnley
quelle
-1

Ich denke, einer der Gründe, warum Google aufgetaucht ist Auto Completeund verwendet wurde, AJAXwar ein Geschwindigkeitsproblem. Wenn Sie jetzt tippen, werden Wörter im Hintergrund gesendet, damit Google einen Teil der Arbeit erledigen kann, solange Sie noch nicht fertig sind. Auch Indizes basieren auf mehreren Wortkombinationen (die Sie als Vorschläge am Ende der Seite finden). Derzeit ist die Netzwerkgeschwindigkeit höher als die von Festplatten, und wahrscheinlich befindet sich ein Großteil dieser Indizes im RAM der Server in ihrer Farm.

Xaqron
quelle