This repository contains open source implementations of B⁺-trees for research use. The purpose of this implementation is to reproduce B⁺-trees and measure its performance.

• Build
  • Prerequisites
  • Build Options
  • Build and Run Unit Tests
• Usage
  • Linking by CMake
  • Implemented B+-Tree Variants
  • Read/Write APIs
• Acknowledgments

Note: this is a header only library. You can use this without pre-build.

sudo apt update && sudo apt install -y build-essential cmake

• B_TREE_PAGE_SIZE: Page size in bytes (default 1024).
• B_TREE_MAX_DELETED_SPACE_SIZE: Invoking a clean-up-operation if the deleted space size of a node exceeds this threshold (default ${B_TREE_PAGE_SIZE} / 4).
• B_TREE_MIN_FREE_SPACE_SIZE: Invoking a split operation if the free space size of a node after cleaning up becomes lower than this threshold (default ${B_TREE_PAGE_SIZE} / 8).
• B_TREE_MIN_USED_SPACE_SIZE: Invoking a merge operation if the used space size of a node becomes lower than this threshold (default ${B_TREE_PAGE_SIZE} / 16).
• B_TREE_MAX_VARLEN_DATA_SIZE: The expected maximum size of a variable-length data (default 128).

• B_TREE_BUILD_TESTS: Build unit tests for this library if ON (default OFF).
• B_TREE_TEST_BUILD_PML: Build tests for PML-based B+trees if ON (default OFF).
• B_TREE_TEST_BUILD_PSL: Build tests for PSL-based B+trees if ON (default OFF).
• B_TREE_TEST_BUILD_OML: Build tests for OML-based B+trees if ON (default OFF).
• B_TREE_TEST_BUILD_OSL: Build tests for OSL-based B+trees if ON (default OFF).
• DBGROUP_TEST_THREAD_NUM: The maximum number of threads to perform unit tests (default 8).
• DBGROUP_TEST_RANDOM_SEED: A fixed seed value to reproduce unit tests (default 0).
• DBGROUP_TEST_EXEC_NUM: The number of executions per a thread (default 1E5).
• DBGROUP_TEST_OVERRIDE_MIMALLOC: Override entire memory allocation with mimalloc (default OFF).
  • NOTE: we use find_package(mimalloc 1.7 REQUIRED) to link mimalloc.

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release -DB_TREE_BUILD_TESTS=ON \
  -DB_TREE_TEST_BUILD_PML=ON -DB_TREE_TEST_BUILD_PSL=ON \
  -DB_TREE_TEST_BUILD_OML=ON -DB_TREE_TEST_BUILD_OSL=ON ..
make -j
ctest -C Release

1. Download the files in any way you prefer (e.g., git submodule).

   cd <your_project_workspace>
   mkdir external
   git submodule add https://github.com/dbgroup-nagoya-u/b-tree.git external/b-tree

2. Add this library to your build in CMakeLists.txt.

   add_subdirectory("${CMAKE_CURRENT_SOURCE_DIR}/external/b-tree")
   
   add_executable(
     <target_bin_name>
     [<source> ...]
   )
   target_link_libraries(
     <target_bin_name> PRIVATE
     dbgroup::b_tree
   )

We implement four variants of B⁺-trees.

1. Pessimistic Multi-level Locking (PML): using pessimistic locking with multi-level SMOs (i.e., lock coupling¹).
2. Pessimistic Single-level Locking (PSL): using pessimistic locking with single-level SMOs (i.e., B^link-tree²).
3. Optimistic Multi-level Locking (OML): using optimistic locking with multi-level SMOs (i.e., optimistic lock coupling³).
4. Optimistic Single-level Locking (OSL): using optimistic locking with single-level SMOs (i.e., OLFIT⁴).

Our ::dbgroup::index::b_tree::BTree uses OSL by default, but you can select a preferred one as follows:

1. ::dbgroup::index::b_tree::BTreePML
2. ::dbgroup::index::b_tree::BTreePSL
3. ::dbgroup::index::b_tree::BTreeOML
4. ::dbgroup::index::b_tree::BTreeOSL

Note that our B⁺-trees optimize their node layout with fixed-length data (i.e., non-string keys). If you want to control the node layout, please use the following aliases:

• ::dbgroup::index::b_tree::BTreePMLVarLen
• ::dbgroup::index::b_tree::BTreePMLFixLen
• ::dbgroup::index::b_tree::BTreePSLVarLen
• ::dbgroup::index::b_tree::BTreePSLFixLen
• ::dbgroup::index::b_tree::BTreeOMLVarLen
• ::dbgroup::index::b_tree::BTreeOMLFixLen
• ::dbgroup::index::b_tree::BTreeOSLVarLen
• ::dbgroup::index::b_tree::BTreeOSLFixLen

We provide the same read/write APIs for the implemented indexes. See here for common APIs and usage examples.

This work is based on results from project JPNP16007 commissioned by the New Energy and Industrial Technology Development Organization (NEDO), and it was supported partially by KAKENHI (JP20K19804, JP21H03555, and JP22H03594).