Das Valkey-Team ersetzt in Version 9.2 die Skiplist hinter großen Sorted Sets durch einen B+-Baum. Der Speicheraufwand für die Sortierung sinkt je Eintrag um 36 bis 43 %, gemessen mit 5 Millionen Einträgen. Das Aktualisieren von Punktwerten mit ZADD läuft in den Tests mehr als doppelt so schnell.
Ein Klick · kostenlosDr. Web bei Google bevorzugenMarkieren Sie drweb.de als bevorzugte Quelle. Dann sehen Sie unsere Artikel öfter unter den Top-Meldungen.Jetzt hinzufügenInhalt 4 Abschnitte
Das Team hinter der Open-Source-Datenbank Valkey hat am 16. November in seinem Blog beschrieben, wie die Version 9.2 große Sorted Sets verwaltet.[1] Statt der Skiplist ordnet ein B+-Baum namens fbtree die Einträge. Die Version 9.2 steht als Testversion bereit, die Befehle bleiben unverändert.[1]
Das Wichtigste in Kürze
- Der Speicheraufwand für die Ordnung sinkt von 50,3 Byte je Eintrag auf 28,5 Byte beim fortlaufenden und 32,0 Byte beim zufälligen Einfügen.[1]
- Das Team misst bis zu 105 % mehr Durchsatz bei ZADD und 76 % mehr bei ZREM. ZSCORE und ZPOPMIN ändern sich kaum.[1]
- Nur der Befehl OBJECT ENCODING meldet für große Sorted Sets jetzt btree statt skiplist.[1]
Warum kostet die Skiplist so viel Speicher?

Ein Sorted Set hält Einträge nach Punktwert geordnet, etwa für Ranglisten oder Warteschlangen mit Priorität. Große Sets bestehen in Valkey aus einer Hashtabelle für den Zugriff per Name und einer Skiplist für die Reihenfolge.[1] Jeder Eintrag sitzt dort in einem eigenen Knoten, der rund 37 Byte für Zeiger, Spannweiten und Punktwert braucht, noch ohne den Namen des Eintrags.[1]
Die Knoten liegen verstreut im Speicher, deshalb wartet der Prozessor bei jedem Suchschritt auf den Arbeitsspeicher. Ein solcher Zugriff dauert nach Angaben des Teams rund 100 Nanosekunden, ein Treffer im Cache etwa eine.[1] Eine Studie von 2025, auf die das Team verweist, zählte bei Skiplists das 2,4- bis 4,8-Fache an Cache-Fehlzugriffen gegenüber einem vergleichbaren B-Baum, an anderen Implementierungen als Valkey.[1]
Was macht der B+-Baum anders?
Der fbtree packt bis zu 61 Einträge in einen Knoten und speichert Punktwert und Name zusammen.[1] Die Skiplist verzweigt im Schnitt etwa vierfach, der Baum 61-fach. Das sind weniger Ebenen und weniger Zugriffe auf den Arbeitsspeicher.[1]
Dank vier Byte langer Merkmale findet der Baum den richtigen Zweig oft, ohne den Knoten zu laden.[1] Die Blätter sind verkettet, deshalb laufen Bereichsabfragen wie ZRANGE von Blatt zu Blatt.[1]
Valkey spart Speicher, ohne dass Anwender einen Befehl ändern müssen. Genau das macht den Test mit eigenen Daten so billig.
Markus Seyfferth, Chefredakteur Dr. Web
Was sollten Betreiber vor dem Umstieg prüfen?
Valkey entstand am 28. März 2024 unter dem Dach der Linux Foundation als Fork von Redis 7.2.4, nachdem Redis die Lizenz geändert hatte. Das Projekt steht unter der BSD-Lizenz, Amazon Web Services, Google Cloud, Oracle, Ericsson und Snap unterstützen es.[2] Der Beitrag stammt von Rain Valentine von AWS und Dragos Andriciuc von Percona. Valentine hat nach eigener Angabe auch die Hashtabelle des Kerns und die Speicherung von Strings überarbeitet.[1]
Die Durchsatzwerte hat das Team auf einem Graviton3-Server mit 64 Kernen an einem Vorläuferstand gemessen und nicht erneut an der veröffentlichten Fassung.[1] Auch der Speichergewinn betrifft nur den Index: Er schrumpft im Verhältnis zum Gesamtspeicher, je länger die Namen der Einträge sind.[1]
Betreiber eigener Valkey-Server testen die Vorabversion mit einer Kopie ihrer Last, vor allem mit ZADD, ZREM, ZRANK und ZCOUNT.[1] Monitoring und Tests, die nach dem Text skiplist suchen, müssen btree erkennen.[1]
Der WordPress-Hoster Rackspeed nutzt Valkey als Object- und Session-Store. Bei solchen Tarifen bestimmt der Hoster, wann 9.2 kommt, und ein reiner Schlüssel-Wert-Cache braucht keine Sorted Sets. Wie sich Hoster unterscheiden, zeigt der WordPress-Hosting-Vergleich. Einen tiefen Eingriff bringt auch PostgreSQL 19, am 19. November erschienen: Der neue Befehl REPACK verkleinert aufgeblähte Tabellen, ohne dass Lese- und Schreibzugriffe warten müssen.
