zurück zum Artikel

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

Eine neue C++-Template-Bibliothek [1] 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 [2] 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 [3] 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 [4]" Varianten der Container angeboten, bei denen Sicherheitskopien angelegt und Iteratoren nach Benutzung neu positioniert werden.

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


URL dieses Artikels:
http://www.heise.de/-1796751

Links in diesem Artikel:
[1] http://google-opensource.blogspot.de/2013/01/c-containers-that-save-memory-and-time.html
[2] http://de.wikipedia.org/wiki/Rot-Schwarz-Baum
[3] http://de.wikipedia.org/wiki/B-Baum
[4] https://code.google.com/p/cpp-btree/wiki/UsageInstructions#Safe_B-Tree_maps_and_sets
[5] https://code.google.com/p/cpp-btree/
[6] https://code.google.com/p/cpp-btree/downloads/list
[7] mailto:jul@heise.de