Datenstrukturdienstag:
Der Splay-Tree. Ist von den Zugriffszeiten im Prinzip wie viele andere selbst-balancierte Bäume, aber mit einem Unterschied:
Er schreibt auch bei Lesezugriff. So sortiert er häufig zugegriffene Nodes so um, dass sie schneller gefunden werden.

Bei zufälligem Zugriff performt er wie andere Bäume. Aber wenn im Zugriff ein Muster ist, kann seine Optimierung richtig zutrage kommen und wird ggf. schneller als O(log(n)).

Ich wollte diesen Baum mal in Rust implementieren, als Übungsaufgabe. Dann ist mir aufgefallen, dass der echt nicht so geil für alles ist, was mehr als einen Thread hat, da auch Leseoperationen schreibend zugreifen (naja, das war ja auch sein Vorteil). Vielleicht gibt’s da eine bessere Variante von, die dieses Problem nicht hat? Vielleicht eine, bei der jeder Thread seine Thread-Local-Kopie hat und nur die “richtigen” schreibenden Operationen synchronisiert werden? Wenn jemand eine Idee hat, her damit!

Wie viele Datenstrukturen ist er schon etwas älter und kommt aus 1985.