C++ B-tree is a template library that implements ordered in-memory containers based on a B-tree data structure. Based on https://code.google.com/archive/p/cpp-btree/, but forked from https://github.com/algorithm-ninja/cpp-btree.
A B-tree based implementation can have advantages over the RB-tree based implementations of std::map. It has fewer pointers leading to significant memory savings and less memory fragmentation. Due to better usage of cache lines, large containers can also see a significant performance increase. See btree_bench.cc for details.
The disadvantage is that all modifications invalidate all pointers and iterators due to possible merge/split operations.
The dmeister repo adds C++11 integration, e.g. rvalue constructor and assignment,
emplace() and at().
This library is a C++ template library and, as such, there is no library to build and install. Copy the .h files and use them!
See UsageInstructions for details.
To build and run the provided tests, however, you will need to install CMake, the Google C++ Test framework, and the Google flags package.
-
Download and install CMake from http://www.cmake.org
-
Download and build the GoogleTest framework from https://github.com/google/googletest
-
Download and install gflags from https://github.com/gflags/gflags
-
Set GTEST_ROOT to the directory where GTEST was built.
-
Set GFLAGS_ROOT to the directory prefix where GFLAGS is installed.
export GTEST_ROOT=/path/for/gtest-x.y
export GFLAGS_ROOT=/opt
cmake . -Dbuild_tests=ON
For example, to build on a Unix system with the clang++ compiler,
export GTEST_ROOT=$(HOME)/src/googletest
export GFLAGS_ROOT=/opt
cmake . -G "Unix Makefiles" -Dbuild_tests=ON -DCMAKE_CXX_COMPILER=clang++
For example to build with ninja and clang++:
mkdir build
pushd build
cmake .. -GNinja -Dbuild_tests=ON
popd build
ninja -C build
ninja install