Indizes — schneller suchen und finden

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.