BTreeX

A high-performance B+ Tree implementation in C++17 with rank query support.

Features

• Pure B+ Tree Design: All data stored in leaf nodes for optimal range queries
• Rank Query Support: Get rank by key and get key by rank operations
• High Performance: Optimized for modern CPUs with cache-friendly design
• Custom Allocator: Support for custom memory allocators
• C++17 Standard: Modern C++ implementation with template metaprogramming
• Iterator Support: Bidirectional iterators for STL-compatible iteration
• No External Dependencies: Header-only implementation

Performance

BTreeX is designed for high-performance operations, especially optimized for:

• Sequential and reverse inserts
• Range queries
• Iteration over sorted data
• Rank-based queries

Benchmark Results (10,000 items)

Operation	BTreeX	Absl B-Tree	STX B+ Tree	Std::Map	BTreeX vs Absl	BTreeX vs STX
Insert (Sequential)	76.3M/s	23.5M/s	8.2M/s	10.5M/s	3.2x faster	9.3x faster
Find	29.0M/s	29.6M/s	37.5M/s	24.9M/s	Similar	0.8x
Iterate	490.1M/s	531.0M/s	1.02G/s	227.6M/s	0.9x	0.5x
Range Query	51.3M/s	42.0M/s	500.6M/s	76.7M/s	1.2x faster	0.1x
GetRank	21.0M/s	N/A	N/A	N/A	Unique feature	Unique feature
FromRank	58.5M/s	N/A	N/A	N/A	Unique feature	Unique feature

Key Observations

Strengths:

• ✅ Insert Performance: 3.2x faster than Abseil B-tree, 9.3x faster than STX B+ tree
• ✅ Range Queries: 1.2x faster than Abseil B-tree
• ✅ Rank Queries: Unique feature not available in standard B-tree implementations
• ✅ Memory Efficiency: ~5 bytes per stored item (vs 45 bytes in skip lists)

Trade-offs:

• ⚠️ Iterate Performance: Slower than STX B+ tree (0.5x) due to lack of leaf-node linked list
• ⚠️ Range Query: Much slower than STX B+ tree (0.1x) for the same reason
• Note: STX B+ Tree uses leaf-node double-linked list for O(1) cross-node traversal, BTreeX currently uses path-stack traversal

Design Decisions

Node Size and Layout

• Fixed node size: 256 bytes (cache-line friendly)
• Maximum keys: 62 keys per leaf node (for 8-byte integers)
• Maximum keys: 24 keys per internal node (with child pointers)
• No parent pointers: Reduces memory overhead, uses path tracking instead

B+ Tree vs B-Tree

BTreeX (B+ Tree):

• All data stored in leaf nodes
• Internal nodes store only separators and child pointers
• Optimal for range queries and sequential access
• Predictable iteration performance

Abseil B-Tree:

• Data stored in both internal and leaf nodes
• More compact storage
• Faster iteration (data in internal nodes)
• Not optimal for range queries

Rank Query Implementation

BTreeX maintains subtree counts at each internal node, enabling:

• GetRank(key): Find rank of a key in O(log n)
• FromRank(rank): Find key at a given rank in O(log n)

This comes with a small overhead (subtree count maintenance) but provides powerful query capabilities for ranking systems, leaderboards, and pagination.

Building

Prerequisites

• CMake 3.20+
• C++17 compatible compiler (GCC 7+, Clang 5+, MSVC 2019+)
• Google Benchmark (for benchmarks, optional)
• Google Test (for tests, optional)

Build Presets

# Default: Release build with library only
cmake --preset default
cmake --build --preset default

# Development: Debug build with tests and examples
cmake --preset dev
cmake --build --preset dev

# Benchmark: Release build with benchmarks
cmake --preset release-benchmark
cmake --build --preset release-benchmark

Manual Build

# Release build
cmake -B build -DBUILD_RELEASE_BENCHMARK=ON
cmake --build build

# Debug build
cmake -B build-dev -DBUILD_DEV=ON
cmake --build build-dev

Usage

Basic Example

#include "BTreeX/btree_x.hpp"

using namespace btreex;

int main() {
    BTreeX<int> tree;
    
    // Insert
    tree.Insert(5);
    tree.Insert(10);
    tree.Insert(3);
    
    // Find
    if (tree.Contains(5)) {
        std::cout << "Found 5!" << std::endl;
    }
    
    // Rank query
    auto rank = tree.GetRank(5);  // Rank of 5
    auto value = tree.FromRank(0); // First element
    
    // Using iterators
    for (auto it = tree.begin(); it != tree.end(); ++it) {
        std::cout << *it << " ";
    }
    
    // Range-based for loop
    for (const auto& item : tree) {
        std::cout << item << " ";
    }
    
    return 0;
}

Custom Allocator

#include "BTreeX/btree_x.hpp"
#include <memory_resource>

using namespace btreex;

int main() {
    // Use a memory resource
    std::pmr::monotonic_buffer_resource pool(1024);
    BTreeX<int, BTreeXPolicy<int>> tree(&pool);
    
    // Or use a custom allocator
    struct MyAllocator {
        void* allocate(size_t size) { /* ... */ }
        void deallocate(void* ptr, size_t size) { /* ... */ }
    };
    
    BTreeX<int, BTreeXPolicy<int>> tree2;
}

API Reference

Core Operations

• bool Insert(KeyT item) - Insert a key, returns true if inserted
• bool Contains(KeyT item) - Check if key exists
• bool Delete(KeyT item) - Delete a key, returns true if found
• void Clear() - Remove all items

Rank Queries (Unique Feature)

• std::optional<uint32_t> GetRank(KeyT item, bool reverse = false) - Get rank of key
• BTreeXPath FromRank(uint32_t rank) - Get path to key at rank

Range Queries

• BTreeXPath GEQ(Q&& query) - Find first key >= query
• BTreeXPath LEQ(Q&& query) - Find last key <= query
• bool Iterate(uint32_t rank_start, uint32_t rank_end, Callback&& cb) - Iterate over range

Iterators

• iterator begin() / iterator end() - Forward/bidirectional iteration
• const_iterator begin() const / const_iterator end() const - Const iteration
• const_iterator cbegin() const / const_iterator cend() const - Const iteration

Properties

• size_t Size() - Number of items
• size_t Height() - Tree height
• size_t NodeCount() - Number of nodes
• bool Empty() - Check if empty

Performance Optimization History

Version 1.0 (Current)

• ✅ Template-based callbacks (eliminate std::function overhead)
• ✅ Optimized Contains() (avoid BTreeXPath construction)
• ✅ Reverse insert optimizations (first element check in BSearch)
• ✅ Native iterator support with bidirectional traversal
• ✅ Custom allocator support
• ✅ Rank query support (GetRank, FromRank)

Performance Comparison with STX B+ Tree

After analyzing STX B+ Tree's implementation, we identified key optimizations that could improve BTreeX:

STX B+ Tree's Performance Secrets:

1. Leaf Node Double-Linked List

   • Each leaf node has prevleaf and nextleaf pointers
   • Iterators can jump directly between leaf nodes
   • No path stack traversal needed for cross-node iteration
   • Impact: 10x faster range queries, 2x faster iteration

2. Ultra-Lightweight Iterator

   • Only stores currnode (leaf pointer) and currslot (position)
   • No path maintenance overhead
   • Direct memory access to key/data
   • Impact: Minimal overhead, cache-friendly

3. Dynamic Search Strategy

   • Linear search for nodes < 256 elements (branch prediction friendly)
   • Binary search for larger nodes
   • Impact: Optimized for real-world access patterns

Current Gap:

STX B+ Tree iterator:     [currnode] [currslot] = 16 bytes
BTreeX iterator:          [node*][pos][is_end] + stack = ~128+ bytes

STX range query:          Jump to nextleaf directly (O(1))
BTreeX range query:       Pop up tree, find next, go down (O(log n))

Future Optimizations

• HIGH PRIORITY: Add leaf node double-linked list for O(1) cross-node iteration
• HIGH PRIORITY: Simplify iterator design (remove path stack)
• Cache alignment (64-byte aligned nodes)
• Prefetch optimization (prefetch next nodes)
• SIMD-optimized binary search (for simple types)
• Memory pool integration

Comparison with Other Implementations

B+ Tree vs B-Tree vs STX B+ Tree vs Skip List

Feature	BTreeX (B+)	Absl (B-Tree)	STX B+ Tree	Skip List
Range Query	⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐⭐⭐	⭐⭐
Sequential Scan	⭐⭐⭐⭐	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	⭐⭐
Random Access	⭐⭐⭐⭐	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	⭐⭐⭐
Rank Query	⭐⭐⭐⭐⭐	N/A	N/A	⭐⭐⭐
Memory Efficiency	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐
Insert Performance	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐	⭐⭐⭐
Delete Performance	⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐

Key Differences:

• STX B+ Tree: Uses leaf-node double-linked list for O(1) cross-node iteration, making it superior for range queries and iteration
• BTreeX: Currently uses path-stack traversal for iteration (O(log n)), making it slower for cross-node operations but with better insert performance
• Absl B-Tree: Stores data in internal nodes (B-tree), not a true B+ tree, faster for small trees but suboptimal for range queries
• Skip List: Simpler implementation but higher memory overhead

Testing

Run tests:

cmake --preset dev
cmake --build build-dev
ctest --preset dev

Run benchmarks:

cmake --preset release-benchmark
cmake --build build-release-benchmark
./build-release-benchmark/benchmark/btree_x_benchmark
./build-release-benchmark/benchmark/comparison_benchmark

License

Apache License 2.0

Acknowledgments

• Inspired by Dragonfly's B+ Tree implementation by Roman Gershman
• Design influenced by Abseil's B-tree implementation
• Original motivation: Replace Redis zskiplist for better memory efficiency

Contributing

Contributions are welcome! Please ensure:

• All tests pass
• Benchmarks show no regression
• Code follows the project style guide (.clang-format)