Profi-Wissen

Indizes — schneller suchen und finden

von - 30.04.2013
Profi-Wissen: Indizes — schneller suchen und finden
Indizes helfen beim Suchen. Sie ordnen den Datenbestand und beschleunigen die Suche ungemein. Es gibt sie als Liste, Baum oder Tabelle. Wie funktionieren sie?
Thunderbird braucht gerade mal ein paar Sekunden, um aus 3000 E-Mails genau die herauszufinden, in denen beispielsweise „Shakespeare“ vorkommt. Diese Geschwindigkeit ist unglaublich – was steckt dahinter?
Thunderbird arbeitet natürlich mit einem Index. Der wird im Hintergrund mit jeder neuen Mail fortlaufend aktualisiert. Die eigentliche Suche später findet nicht in den 3000 E-Mails statt, sondern in diesem raffiniert aufgebauten Index. Der Unterschied: Der originale Datenbestand ist chaotisch, ein Index ist immer streng geordnet.
Es gibt hauptsächlich drei Ordnungsprinzipien: die sortierte Liste, den binären Suchbaum und die Hash-Tabelle. Die folgende Bilderstrecke erläutert die Unterschiede dieser drei Ordnungsprinzipien.
Bilderstrecke
5 Bilder
Sequenzielle Suche: Die sequenzielle Suche ist die einfachste Suchform. Sie benutzt keinen Index. Sie durchforscht den kompletten Datenbestand von vorn bis – im schlimmsten Fall – ganz hinten. Hier wird der Suchbegriff „Shakespeare“ erst auf Seite 117 gef
Index: Ein Index ist eine sortierte Liste von Begriffen, die alle in dem Datenbestand vorkommen. Hier etwa führt der Eintrag „Shakespeare“ direkt auf Seite 117. Im Index selbst wird aber weiterhin sequenziell gesucht: von vorn nach hinten.
Binäre Suche: Wenn schon der Index eines Datenbestands riesengroß ist, dann durchsucht die binäre Suche den Index nicht mehr sequenziell, sondern binär: Sie teilt den Datenbestand in der Mitte und prüft, ob der Suchbegriff größer oder kleiner als die Mitt
Binärer Suchbaum: Ein Index muss keine Liste sein. Er lässt sich auch als binärer Baum aufbauen: Jeder Knoten verzweigt in zwei Richtungen. Links werden ausschließlich kleinere Werte eingereiht, rechts größere.Wer das „S“ sucht, der muss zuerst nach recht

Profi-Wissen :

Indizes — schneller suchen und finden

>>
Verwandte Themen