Daten fürs schnelle Wiederfinden speichern: Red-Black-Trees

Eichhörnchen Sandy ist nicht mehr die Jüngste. Nicht nur die Knochen schmerzen, auch das früher sehr gute Gedächtnis lässt sie immer häufiger im Stich. Als sie letztes Jahr nach ihren Lieblings-Walnüssen vom Vorjahr suchte, musste sie sogar alle ihre Verstecke aufbuddeln. Wie im wirklichen Leben üblich verbargen sich die Leckereien erst unter dem letzten Vorratsstein.

Vielen Programmierern wird Sandys Leid sicherlich irgendwie bekannt vorkommen. Wie das altersschwache Eichhörnchen legen auch sie ihre Daten ungeordnet im Speicher ab. Als Behälter dienen dann ein Array oder eine lange, über Zeiger verkettete Liste, zum Beispiel:

typedef struct _element{
        void *zeigeraufmeinedaten;
        struct _element *naechstes;
} element;

Der Zeiger »naechstes« verweist einfach immer auf das jeweils folgende Element in der Liste. Sucht der Programmierer nun nach einem darin gespeicherten Element, muss er sich mühsam durch die gebildete Kette hangeln. Je mehr Dinge diese Liste speichert, desto länger braucht die Suche - im schlimmsten Fall muss man jedes Element einmal anfassen. Wer diese ineffiziente Suche auch noch in eine hübsche und möglichweise mehrfach verschachtelte Schleife verpackt, lässt die Laufzeit wie eine Rakete in den Himmel schießen.

Kerniges

Auch der Linux-Kernel kämpft häufig mit solchen Problemen. So muss sich das Betriebssystem beispielsweise merken, welche Speicherregionen bereits belegt sind. Diese Informationen könnte es in einer derartigen Liste ablegen. Möchte der Kernel nun feststellen, ob eine Speicherregion noch frei ist, müsste er diese unter Umständen recht lange Kette immer komplett durchlaufen. Ein anderes Beispiel liefert der so genannte I/O-Scheduler: Sobald ein Programm auf die Festplatte zugreifen möchte, sendet es eine entsprechende Anfrage an den Betriebssystemkern.

Dort übernimmt dann der I/O-Scheduler die weitere Regie (siehe [1]). Vereinfacht ausgedrückt merkt er sich alle eingehenden Aufträge zunächst in einer Warteschlange, um sie dann anschließend in eine optimierte Reihenfolge zu bringen. Das soll die Festplattenzugriffe beschleunigen. Je mehr Programme eine Anfrage stellen, mit desto mehr Daten muss der Scheduler jonglieren. Eine einfache Liste würde hier das gesamte System zu stark ausbremsen und den erhofften Geschwindigkeitsvorteil zumindest teilweise wieder auffressen.

Auf die Bäume

Weil Eichhörnchen Sandy zwar schon etwas senil ist, aber doch noch nicht auf den Kopf gefallen, soll in diesem Jahr ein ausgeklügeltes Lagersystem Ordnung in ihre Vorratshaltung bringen. Dazu hat sie sich extra einen schönen alten Baum mit vielen Astlöchern ausgesucht. Bevor sie ihre Nüsse dort verstaut, sortiert sie sie noch nach der Sorte. Die Informatiker hatten diese Idee schon etwas früher. Gegenüber Sandys realem Baum bieten sich jedoch erfreulicherweise ein paar zusätzliche Gestaltungsspielräume und somit einige Vorteile.

Er besteht jetzt aus einer Wurzel und vielen Gabelungen, den so genannten Knoten, die beliebige Daten aufnehmen können. Die Verbindungsäste werden Kanten genannt. Die allerletzten Knoten in der Baumkrone heißen wie ihre realen Pendants Blätter. Im Unterschied zum Eichhörnchen-Leben stehen Bäume in der Informatiker-Welt aber auf dem Kopf, die Wurzel wird also meist oben eingezeichnet, der Weg zu den Blättern verläuft nach unten.