C++-Bibliothek für B-Tree-Container

Eine neue C++-Template-Bibliothek für verschiedene Container wurde von Googles Open-Source-Abteilung bereit gestellt. Sie soll analog zu den Standardimplementierungen map, set, multimap und multiset arbeiten, allerdings wurden für die Umsetzung B-Trees verwendet.

Typischerweise werden die Container der Standard Template Library in C++ durch sogenannte Rot-Schwarz-Bäume implementiert. Hierbei wird ein Element pro Knoten gespeichert, was drei Zeiger und 1 Bit pro Element nötig macht. Mit der alternativen Methode über B-Trees soll der Speicherbedarf deutlich reduzierbar sein: So wird als Beispiel angeführt, dass ein set<int32_t> auf einem 32-Bit-Betriebssystem einen Overhead von 16 Bytes für alle Set-Elemente von 4 Byte Größe verursacht, während das B-Tree-Äquivalent btree_set<int32_t> 1 Byte pro Element erzeugt. Da auch der Cache anders verwendet wird, sollen sich auch die Zugriffszeiten auf große Container verringern lassen.

Einen Unterschied in puncto Kompatibilität gibt es allerdings: Insertions und Deletions machen noch ausstehende Iteratoren für den Container ungültig. Um hier keine Fehler zu begehen, werden "sichere" Varianten der Container angeboten, bei denen Sicherheitskopien angelegt und Iteratoren nach Benutzung neu positioniert werden.

Die Bibliothek steht unter Apache 2.0 License und lässt sich von der Projektwebsite herunterladen. (jul)