C++ Btree - Template Library B-tree data structure

  •        0

C++ B-tree is a template library that implements ordered in-memory containers based on a B-tree data structure. Similar to the STL map, set, multimap, and multiset templates, this library provides btree_map, btree_set, btree_multimap, and btree_multiset.

C++ B-tree containers have a few advantages compared with the standard containers, which are typically implemented using Red-Black trees. Nodes in a Red-Black tree require three pointers per entry (plus 1 bit), whereas B-trees on average make use of fewer than one pointer per entry, leading to significant memory savings. For example, a set<int32_t> has an overhead of 16 bytes for every 4 byte set element (on a 32-bit operating system); the corresponding btree_set<int32_t> has an overhead of around 1 byte per set element.




comments powered by Disqus

Related Projects

Boost - CPP Library

Boost provides free peer-reviewed portable C++ source libraries. Boost libraries are intended to be widely useful, and usable across a broad spectrum of applications. It supports String, Containers, Streams, Generic programming, Concurrent programming, Math, Memory and lot more.

Infinispan - Key value NOSQL data store and data grid

Infinispan is an extremely scalable, highly available key/value NoSQL datastore and distributed data grid platform. The purpose of Infinispan is to expose a data structure that is highly concurrent, designed ground-up to make the most of modern multi-processor/multi-core architectures while at the same time providing distributed cache capabilities. Infinispan offers enterprise features such as efficient eviction algorithms to control memory usage as well as JTA compatibility.


Stxxl is an implementation of the C++ standard template library STL for external memory (out-of-core) computations, containers, and algorithms that can process huge volumes of data that only fit on disks.

HyperGraphDB - Database for Storing Strongly-Typed Hypergraphs

HyperGraphDB is a general purpose, open-source data storage mechanism based on a powerful knowledge management formalism known as directed hypergraphs. While a persistent memory model designed mostly for Knowledge management, Artificial Intelligence and Semantic web projects, it can also be used as an embedded object-oriented database for Java projects of all sizes. It could also be used as graph database or as (non-SQL) relational database.


B-tree with a twist pointer set. The ordered set approaches the speed of the fastest unordered, hash table based sets, while using several times less memory.

Koloboke - Java Collections till the last breadcrumb of memory and performance

Koloboke aims to replace the standard Java collections and streams with more efficient implementations. The current version of Koloboke focuses on replacing java.util.HashSet and java.util.HashMap. It provides a complete set of primitive type implementations for each collection. Its able to avoid the expensive boxing/unboxing of primitives and saves memory for boxed primitive objects. It is the fastest and the most memory efficient library implementing hash maps and sets.

S-Space - A scalable software library for semantic spaces

The S-Space Package is a collection of algorithms for building Semantic Spaces as well as a highly-scalable library for designing new distributional semantics algorithms. Distributional algorithms process text corpora and represent the semantic for words as high dimensional feature vectors.

Memcached - distributed object caching system

Memcached is high-performance, distributed memory object caching system, generic in nature, but intended for use in speeding up dynamic web applications by alleviating database load. Memcached is an in-memory key-value store for small chunks of arbitrary data (strings, objects) from results of database calls, API calls, or page rendering.

Memprof - A Ruby gem for memory profiling

Memprof is a Ruby level memory profiler that can help you find reference leaks in your application. Memprof can also do very lightweight function call tracing to help you figure out which system calls, and library calls your code causes. Ruby memory profiler similar to bleak_house, but without patches to the Ruby VM.


pack:tag is a JSP-Taglib that minifies, compresses and combines resources (like JavaScript and CSS) and caches them in memory or in a generated file. It works transparent to the user/developer and the compressing-algorithms are pluggable.