JetBrains YouTrackDB — In-Memory Thread-Safe Sorted Tree

Overview

This project implements a custom, in-memory, sorted key–value store based on a B-tree–like data structure, written entirely from scratch in C++17.
It was designed to support sorted key ordering, multiple values per key, and safe concurrent access.

The tree is fully in-memory and uses manual memory management for all internal structures, including arrays of keys, values, and child nodes.

---

Core Design

Chosen Data Structure

The implementation is based on a B-tree variant, chosen for its:

• Self-balancing behavior, maintaining logarithmic O(log n) complexity for insertions and lookups even under high load.
• Support for multiple values per key, implemented via dynamically growing arrays inside each KVPair object.
• Stable performance across large datasets — avoiding the degenerate cases possible in binary search trees.

The B-tree design makes it more scalable and realistic for systems resembling YouTrack’s internal data models, where multiple entities may share the same key.

---

Concurrency Model

Thread safety is achieved through a hybrid locking model:

• Each Node has its own std::shared_mutex, allowing:
  • Concurrent reads (shared_lock)
  • Exclusive writes (unique_lock)
• A global treeMutex protects structural modifications at the root level (e.g., when a node split promotes a key upward).

This approach ensures safe concurrent access without global serialization, minimizing contention for read-heavy workloads.

---

Implementation Details

Components

Component	Description
ByteArray	Manages raw binary data (uint8_t*) with deep-copy semantics. Used for both keys and values.
KVPair	Represents a single key and a dynamically sized array of associated values. Implements exponential resizing for efficient growth.
Node	Stores an array of KVPair entries and pointers to child nodes. Handles entry splitting when capacity limits are reached.
ThreadSafeBTree	Manages root operations, recursive insertion, node splits, and lookup. Provides thread-safe put and get APIs.

Memory Model

• All arrays (entries, children, values) are dynamically allocated using new[] and freed using delete[].
• Each ByteArray performs deep copies of its data buffer to avoid dangling references.

Building

_

Requirements

• g++ (C++17 or newer)
• POSIX threads (-pthread)