|
 Hanke,
S.: "The Performance of Concurrent Red-Black Tree Algorithms"
Hanke,
S., Ottmann, Th., Soisalon-Soininen, E.: Relaxed Balanced Red-Black
Trees
Hanke,
S., Soisalon-Soininen, E.: Group Updates for Red-Black Trees
K.Larsen,
T.Ottmann, E.Soisalon-Soininen: "Relaxed Balance for Search Trees
with Local Rebalancing."
Die
Relaxed Balance Homepage von Kim Larsen
AOF-Vortrag:
Relaxed Balancing (Th. Ottmann)
Relaxed-Balancing
Animationen
Bericht
Nr.115: S. Hanke, "The Performance of Concurrent Red-Black Tree
Algorithms"
Bericht
Nr.50: Eckerle, Nurmi, "Concurrent Perfect Balancing of Binary Search
Trees"
Bericht
Nr.71: Ottmann, Soisalon-Soininen, "Relaxed Balancing Made Simple"
Bericht
Nr.90: Sabine Hanke, "Chromatic Search Trees Revisited"
|
Relaxed Balancing
Standard Implementationen von Wörterbüchern sind balancierte
Bäume, wie z.B. Rot-Schwarz-Bäume oder AVL-Bäume, die
die Ausführung von Such- und Updateoperationen in O(log n) Zeit
erlauben, falls n die Anzahl der im Baum gespeicherten Schlüssel
ist. Um die logarithmische Laufzeit zu gewährleisten, wird
sofort nach jedem Update eine Folge von
Rebalancierungsschritten ausgeführt, die die entsprechende
Balancebedingung wiederherstellt. Die Rebalancierung ist derjenige
Teil einer Updateoperation, der die meiste Zeit benötigt.
In stark dynamischen Anwendungen kann es nun
passieren, daß Update-Anfragen derart gehäuft auftreten,
daß der Suchbaum möglicherweise nicht in der Lage ist, die
Anfragen so schnell wie benötigt zu bearbeiten.
Falls ein Wörterbuch auf einer Shared-Memory Architektur verwendet
wird, muß man dafür sorgen, daß ein gleichzeitiges Lesen
und Schreiben derselben Teile der Datenstruktur verhindert wird. Eine
gängige Methode für Concurrency-Control ist, die kritischen
Teile durch Locks zu schützen, so daß andere Prozesse
keinen oder nur eingeschränkten Zugriff auf diese Datensätze
haben. Für die Effizienz ist wichtig, daß dabei jeweils nur
kleine Bereiche des Suchbaumes gleichzeitig gesperrt werden.
Implementiert man jedoch die Standardalgorithmen für balancierte
Suchbäume in einer parallelen Umgebung, so wird es notwendig, den
gesamten Suchpfad von der Wurzel bis zu einem Blatt zu sperren, an dem ein
Update durchgeführt werden soll.
Dies führt zu der Idee, die Rebalancierung von der eigentlichen
Updateoperation abzukoppeln. Anstatt zu verlangen, daß die
Balancebedingung sofort nach jeder Updateoperation wiederhergestellt
wird, kann die Rebalancierung beliebig lange hinausgezögert und
von weiteren Such- und Updateoperationen unterbrochen werden. Diese
Art von Rebalancierung nennt man Relaxed Balancing.
|