← Back to ChaosTree

The Dragon Feed

"Every rev (factor) of the dragon is a warning. Every gearshift bears the load (memory). The dragon unleashes its might at 1.0f, packing your data into the map like it never even felt it."

The Dragon Feed is the internal bulk-loading engine of ChaosTree's B-Tree and B+Tree architectures. Instead of utilizing standard iterative insertions—which suffer from pointer chasing, tree rebalancing, and heavy GC allocation rates—the Dragon Feed directly ingests raw sorted matrices and compiles them into contiguous memory pages.

The Gears (Packing Factor)

The Dragon Feed exposes a factor parameter, acting as the transmission for the engine. It dictates exactly how tightly the internal arrays should be packed during bulk ingestion.

- 0.5f (First Gear): 50% capacity. Leaves room for future random insertions without triggering node splits. Highest initial memory footprint.
- 1.0f (Top Gear): 100% capacity. Zero wasted bytes. Maximum CPU cache line saturation. Pure throughput.

JMH Benchmarks (degree = 64)

Benchmark performed on: Intel Core i5-13450HX (16 cores), G1GC, default heap (5803 MB).

Two ingestion paths were measured. importFlatMatrix bulk-copies a pre-built sorted matrix directly into node arrays via System.arraycopy; buildFromSorted walks a sorted iterator (the same style of construction TreeMap uses) and builds nodes incrementally. All 30-fork averages, times in microseconds per operation.

Reproduce with:

java -jar ct-benchmark/target/benchmarks.jar WriteHeavyMap.bulkLoadBPlusTree \
    -p size=10000,100000,1000000,10000000 \
    -p factor=0.5f,0.75f,1.0f \
    -f 3 -wi 10 -w 1 -r 1 -i 10 -tu us -rf text -rff bulkLoad.txt

java -jar ct-benchmark/target/benchmarks.jar WriteHeavyMap.importFlatMatrixBPlusTree \
    -p size=10000,100000,1000000,10000000 \
    -p factor=0.5f,0.75f,1.0f \
    -f 3 -wi 10 -w 1 -r 1 -i 10 -tu us -rf text -rff dragonFeed.txt

importFlatMatrix — arraycopy-based bulk import

All values in microseconds per operation, rows are factor, columns are size — read down a column to compare factors at fixed size, or across a row to see how a single factor scales with size.

Packing factor directly sizes the underlying flat array and resize threshold here, so it's a first-order effect: 1.0f beats 0.5f by roughly 35–42% across every size.

Factor vs. Memory — importFlatMatrix, size = 1,000,000

Same path, finer-grained factor sweep, with JMH's gc.alloc.rate.norm profiler enabled to see bytes allocated per op directly. Allocation drops almost linearly as factor rises — less slack per node means fewer nodes, which means less array overhead per element — and time tracks it closely.

java -jar ct-benchmark/target/benchmarks.jar WriteHeavyMap.importFlatMatrixBPlusTree \
    -p size=1000000 \
    -p factor=0.5f,0.6f,0.7f,0.8f,0.9f,1.0f \
    -f 3 -wi 10 -w 1 -r 1 -i 10 -tu ms -prof gc -rf text -rff dragonFeedMemory.txt

Tree Size (MB) is Alloc/op converted to MB — for a bulk import benchmark this is effectively the resident size of the built tree, since each op constructs one fresh tree from scratch. 0.5f → 1.0f shrinks it from 16.73 MB to 8.30 MB, roughly halving memory footprint for 1,000,000 entries, while time drops ~48% in step.

buildFromSorted — iterator-driven build

All values in microseconds per operation, same layout as above — down a column compares factors at fixed size, across a row shows one factor's scaling.

Here the three factors sit within each other's error bars at every size — packing density only controls node occupancy, and it's a second-order effect compared to the per-entry comparator/iterator/split cost that dominates this path.

Usage

1. By Constructor

// Use the Dragon at top gear (1.0f)
// It is advised to leave a space for future operation.
// 1. Prepare your sorted data matrix
Integer[] sortedKeys = {1, 2, 3, 4, 5};
String[] values = {"A", "B", "C", "D", "E"};
Object[][] matrix = new Object[][]{sortedKeys, values};

// 2. Feed the Dragon
BPlusTreeMap fastMap = new BPlusTreeMap<>(
    BPlusTreeMap.Builder.degree(64)
        .factor(0.8f) // 80% packing density, leaves room for runtime inserts
        .importFlatMatrix(matrix)
        .build()
);
    

2. By Public API through array

• Matrix Layout: The blast parameter must be exactly 2D: blast[0] contains the keys, and blast[1] contains the values.
• Array Integrity: Neither array can be null, and both must be of exactly equal length.
• No Null Keys: A key must never be null. If a value is empty/missing, you must explicitly place null in the value array at that index.
• Strictly Sorted: The keys array MUST be strictly sorted according to the tree's comparator. Feeding unsorted data will instantly and silently corrupt the entire tree structure.
• Minimum Degree: This API relies on chunked array-copying and only services trees with a degree >= 32.
• FILL FACTOR: The factor determines node occupancy and has strict limits between 0.5f and 1.0f. A factor of 0.75f is highly recommended for bulk loading. This packs the nodes densely while leaving exactly enough buffer room to prevent future insertions from triggering massive, cascading split operations. Hold the Chaos!

    // Awaken the Dragon at top gear (1.0f)
    Object[][] blast = new Object[][]{sortedKeys, values};
    float factor = 1.0f;

    BPlusTreeMap<Integer, String> map = new BPlusTreeMap<>();
    //this creates a default degree of 64 and comparator null!
    map.importFlatMatrix(blast, factor);
    

3. By Public API through Sorted Map.Entry

WARNING: The provided iterator MUST yield elements in strict ascending order according to this tree's comparator. If the data is unsorted, the tree structure will be corrupted.

FILL FACTOR:

• A value between 0.5 and 1.0 representing how full to pack each node.
• Use 1.0f for read-only data.
• Use a lower value to leave room for future insertions.
• A value of 0.9f is used for bulk loading in my tree.
• For read purposes, you can use 1.0f, but after that, any insert or remove operation will trigger massive split, merge, borrow, and array-shifting operations.

Parameters:

• sortedData: An iterator providing strictly sorted elements.
• fillFactor: A value between 0.5 and 1.0 representing how full to pack each node.

    // Use the Dragon at top gear (1.0f)
    BPlusTreeMap<Integer, String> map = new BPlusTreeMap<>();
    //this creates a default degree of 64 and comparator null!
    map.buildFromSorted(iterator, factor);