ChaosTree Architecture Decision Records

This document tracks the core architectural choices, trade-offs, and design constraints that define the ChaosTree engine. Any addition info like future cases is not guaranteed it's assumed.

ADR 1: Why JDK 21+ ?

1. Sequenced Collections (JEP 431)

The most absolute and non-negotiable reason for requiring JDK 21 is JEP 431: Sequenced Collections. Before JDK 21, Java's collection framework had a fragmented and inconsistent approach to collections with a defined encounter order.

In JDK 21, the standard library introduced the SequencedCollection, SequencedSet, and SequencedMap interfaces. The NavigableSet and NavigableMap interfaces were retrofitted to natively extend these new sequenced interfaces.

Because ChaosTree is a strict, mathematically compliant implementation of NavigableSet and NavigableMap, it must honor the modern JDK contract. By targeting JDK 21, ChaosTree natively supports:

• addFirst() / addLast() (Throws UnsupportedOperationException as dictated by the SortedSet contract)
• getFirst() / getLast()
• removeFirst() / removeLast()
• reversed() (A unified, predictable alternative to descendingMap() and descendingSet())

2. Pattern Matching and Sealed Classes

The ChaosTree engine relies on highly restrictive type hierarchies to ensure that the JIT compiler can aggressively inline operations. Using Sealed Classes (introduced in JDK 17) like abstract sealed class AbstractNaryMapNode allows the engine to strictly limit implementors to BTreeMapNode and BPlusTreeMapNode.

When combined with Pattern Matching, this guarantees at compile-time that the compiler has exhaustive knowledge of the node hierarchy, allowing the JVM to eliminate bimorphic/megamorphic dispatch overhead on the hot-path and optimize the exact layout of the arrays in memory.

3. Future-Proofing for Project Valhalla

Setting the baseline to JDK 21 positions the codebase perfectly for the upcoming Project Valhalla (Value Types). ChaosTree's Structure of Arrays (SoA) design, which separates keys[] and values[], is conceptually aligned with how value types work. By operating on a modern LTS (Long-Term Support) JVM, the library is ready to seamlessly adopt primitive array packing once Valhalla lands, without dragging along a decade of legacy JDK 8 baggage.

Decision: ChaosTree will explicitly target JDK 21+. Backporting to JDK 8 or 11 is explicitly rejected, as it would require ripping out the SequencedCollection contracts and destroying the strict compliance guarantees the project was built to deliver.

ADR 2: What happened to version 1.2.0?

1. The Custom API Trap

Version 1.2.0 of ChaosTree was incredibly fast, but it fell into a common trap for custom data structures: it relied on a massive, proprietary API surface. It had its own custom insertion, retrieval, and iteration methods. While this made internal development easy, it made adoption extremely difficult. Java developers expect to be able to seamlessly drop a high-performance map into existing codebases that depend on java.util.Map or java.util.NavigableMap. A custom API breaks polymorphic substitution and violates the Principle of Least Astonishment.

2. The Refactoring to Standard Interfaces

The decision was made to tear out the old custom API entirely for v2.0.0. The mandate for v2.0.0 was strict and absolute: ChaosTree must stand on equal footing with the JDK.

To achieve this, the entire architecture was rewritten to perfectly implement NavigableSet, NavigableMap, SequencedSet, and SequencedMap. Every single boundary condition, edge case, and exception contract was rewritten to match the behavior of java.util.TreeMap and java.util.TreeSet.

3. Mathematical Verification via Guava Testlib

To mathematically prove that v2.0.0 was a flawless drop-in replacement, I subjected the engine to Google Guava's NavigableSetTestBuilder and NavigableMapTestSuiteBuilder. What started as a custom tree implementation became a rigorously verified engine passing over 214,680 strict test permutations. This level of correctness verification was fundamentally impossible with the proprietary v1.2.0 API.

Decision: Version 1.2.0 is permanently deprecated and its custom API is destroyed. ChaosTree v2.0.0 replaces it with a strictly minimal custom API surface limited to only 4 specialized N-ary operations: display(), importFlatMatrix(), exportFlatMatrix(), and buildFromSorted(). Everything else relies purely on the standard JDK contract.

ADR 3: Why 4x Code Duplication over OOP Abstraction?

1. The JVM Virtual Dispatch Penalty

In classical Object-Oriented Design (OOD), the instinct is to write a single generic putInternal or splitNode algorithm in an abstract base class, and use template methods (like isLeaf() or createNode()) to handle differences.

However, placing the hottest loops of a data structure inside an abstract base class forces the JVM to use virtual method dispatch (invokevirtual). Because the base class would handle both BTreeMap and BPlusTreeMap, the dispatch becomes bimorphic. Bimorphic and megamorphic call sites cripple the JVM JIT compiler's ability to aggressively inline the code. By manually duplicating the loops into the final concrete classes, I guarantee strictly monomorphic dispatch, allowing the JIT to compile the tree traversal into raw, uninterrupted machine code.

2. Eliminating Hot-Path Branching (Instance Checks)

The mathematical layouts of a B-Tree and a B+-Tree are fundamentally different. A B+-Tree internal node has values == null, whereas a B-Tree internal node actively manages values. If these trees shared a unified abstraction, the core loop would be forced to constantly evaluate if (this instanceof BPlusTreeMap) or if (values != null) on every single node split, merge, and borrow operation.

Injecting conditional type-checks into the absolute hottest CPU path destroys branch prediction and flushes the CPU pipeline. Hand-writing the 4 distinct variations eliminates these conditional checks entirely. The algorithm knows exactly what data it has.

3. Mechanical Sympathy over "Clean Code"

ChaosTree prioritizes L2 cache locality and array arithmetic above traditional "Clean Code" heuristics (like DRY - Don't Repeat Yourself). A generic OOD abstraction requires abstracting away the memory layout so that algorithms can operate generically. ChaosTree does the exact opposite: the algorithms are explicitly hardcoded to exploit their specific Structure-of-Arrays (SoA) layout.

Decision: I explicitly accept 4x code duplication across BTree, BPlusTree, AvlTree, and RedBlackTree. Code deduplication via hyper-abstraction is rejected because it introduces virtual dispatch overhead and CPU branch mispredictions. The algorithms are the architecture, and they will remain tightly coupled to their concrete implementations to preserve maximum speed.

ADR 4: The 12-Element Linear Search Threshold

1. Algorithmic Complexity vs. Hardware Reality

In textbook computer science, searching a sorted array should always use Binary Search because its time complexity is O(log N), which is mathematically vastly superior to Linear Search's O(N).

However, CPUs do not run Big-O notation—they run machine code. Modern CPU architectures rely heavily on pipelining and branch prediction. Binary search is inherently branch-heavy (constantly asking "is the target greater than or less than the midpoint?"). For very small arrays, the CPU frequently mispredicts these branches, forcing a pipeline flush that wastes dozens of clock cycles.

2. The Power of CPU Cache Prefetching

A linear search simply executes a tight for loop, walking sequentially through the keys[] array. Because ChaosTree uses a Structure-of-Arrays (SoA) layout, the CPU memory controller recognizes this sequential access pattern and pre-fetches the entire array chunk directly into the ultra-fast L1 cache.

The sequential loop unrolls beautifully in the JVM JIT compiler. The hardware executes the linear scan so quickly that it beats the mathematical efficiency of binary search.

3. Finding the Crossover Point

There is a physical crossover point where the mathematical advantage of O(log N) finally overcomes the hardware overhead of branch mispredictions and method calls. Through rigorous JMH profiling on the JVM, that exact crossover point was discovered to be 12 elements.

Decision: ChaosTree implements a hybrid search algorithm for internal node traversal. If a node contains fewer than 12 keys (current.keyCount < 12), the engine executes a raw linear for loop. If it contains 12 or more keys, it delegates to Arrays.binarySearch(). This guarantees that the engine always operates at the absolute physical speed limit of the hardware, regardless of the B-Tree's degree configuration.

ADR 5: Rejection of Degree 2 (Enforcing t ≥ 3)

1. The Object Header Memory Bloat

In textbook definitions, a B-Tree is valid at degree t = 2 (known as a 2-3-4 tree). At this degree, a node holds a minimum of 1 key and a maximum of 3 keys.

In C or C++, this might be an acceptable structure. However, in the Java Virtual Machine, every Object array carries a 16-byte header. Allocating a keys[] array and a child[] array just to hold 1 to 3 elements means the JVM memory overhead drastically outweighs the actual data payload. The tree degenerates into an incredibly bloated, slow Binary Search Tree rather than a cache-friendly N-ary data structure.

2. Crashing the Top-Down Bulk Loader Math

ChaosTree's single-pass, top-down bulk loader relies on "capacity windows" to eliminate the standard Phase 2 repair traversal. It distributes remainder elements by smearing them across the children.

At t = 2, the capacity window is restricted to [1, 3] keys. This incredibly tight mathematical margin destroys the bulk loader's ability to smoothly absorb remainders. Distributing extra keys frequently causes the target nodes to overflow, breaking the invariants of the top-down partitioner and forcing impossible edge cases.

Decision: ChaosTree strictly enforces degree ≥ 3 for all N-ary structures. By enforcing a minimum degree of 3 (where nodes hold 2 to 5 keys), the library guarantees that the top-down bulk loader has the mathematical "breathing room" required to safely partition elements without Phase 2 repairs. It also ensures that the CPU cache actually has a meaningful chunk of contiguous array data to pre-fetch, validating the core architectural premise of the engine.

ADR 6: Structure of Arrays (SoA) over Objects

1. The JVM Cache Line Pollution Problem

Standard Java collections like java.util.TreeMap use a Structure of Objects (SoO). Every element is wrapped in an Entry<K,V> object that contains the key, the value, pointers to left/right/parent nodes, and a color boolean.

Modern CPUs pull memory into the L1/L2 cache in 64-byte chunks called cache lines. When the CPU binary-searches a standard Java TreeMap, it drags all of those useless value pointers, child pointers, and colors into the cache line just to read the one key reference it needs for the comparison. This severely pollutes the cache and causes constant L1 cache misses.

2. Maximum Mechanical Sympathy

ChaosTree abandons the Entry wrapper completely and uses Structure of Arrays (SoA). Inside an N-ary node, data is decoupled into raw, independent physical arrays:

protected final Object[] keys;
protected final Object[] values;
protected final N[] child;

When the engine searches a node, it only touches the keys[] array. Because Java references (with Compressed Oops) are 4 bytes, a single 64-byte CPU cache line can hold exactly 16 contiguous keys. The CPU's memory controller effortlessly pre-fetches these keys, resulting in lightning-fast, zero-miss array scans.

3. Exploitability and Garbage Collection

Beyond pure speed, the SoA layout drastically reduces Garbage Collection pressure by eliminating the 16-byte object header penalty that comes with creating millions of Entry wrappers.

Furthermore, decoupling the arrays allows for mathematical asymmetry. Because keys[] and values[] are physically separate, the BPlusTreeMap engine can conditionally set this.values = null for its internal routing nodes, instantly erasing hundreds of kilobytes of memory allocation that would be impossible to avoid if keys and values were permanently bound together inside an Entry wrapper.

Decision: ChaosTree strictly uses Structure of Arrays (SoA) for all N-ary node memory layouts. I explicitly reject the standard Java paradigm of wrapping elements in Entry or Node objects to maximize L1/L2 CPU cache utilization and minimize Garbage Collection overhead.

ADR 7: Overriding forEach for Iterator-less Traversal

1. The Iterator State Machine Penalty

Standard Java iteration uses the Iterator interface, which requires maintaining external state. On every single element, an iterator must:

• Check hasNext() to ensure it hasn't fallen off the edge.
• Check expectedModCount == modCount to defensively prevent ConcurrentModificationException.
• For standard B-Trees, maintain a complex traversal stack to remember how to climb back up the tree.

2. Direct Internal Traversal via forEach

Instead of forcing all bulk operations through the Iterator interface, ChaosTree explicitly overrides the forEach() method natively on the concrete tree classes (e.g., BPlusTreeMap.forEach(BiConsumer)).

For BPlusTreeMap, because all data lives in a linked-list of leaf nodes, the forEach override ignores the tree completely. It simply grabs the first leaf node and executes a raw, hardware-level linked-list walk (currentLeaf = currentLeaf.next), consuming the arrays directly without allocating an Iterator object or executing constant bounds-checking overhead.

3. Benchmark Results: Beating a Raw ArrayList

By stripping away the Iterator state machine, ChaosTree achieves iteration speeds that defy standard expectations. In JMH benchmarks traversing 1,000,000 elements, ChaosTree is nearly 10x faster than the standard JDK TreeMap.

More remarkably, because it processes elements in contiguous chunks without the per-index bounds checking of a standard array for loop, it actually clocks in faster than a raw ArrayList:

Benchmark                                          Score (ms/op)   Allocated (B/op)
-----------------------------------------------------------------------------------
ChaosTreeMapIterateBenchmark.iterateChaosTree        2.540 ± 0.132      8.7
ChaosTreeMapIterateBenchmark.iterateRawArrayList     3.090 ± 0.213     10.6
ChaosTreeMapIterateBenchmark.iterateJavaTreeMap     20.650 ± 3.691     70.6

Decision: ChaosTree implements native, direct-access forEach overrides on all concrete engines. I accept the duplication of iteration logic in exchange for bypassing the heavy Java Iterator interfaces, successfully edging out even flat array iteration speeds.

ADR 8: Overriding Map Default Methods (The Double-Traversal Penalty)

1. The Benchmark Reality Check

During rigorous JMH benchmarking, an anomaly appeared: putIfAbsent and compute operations on SubMap and DescendingMap views were suddenly twice as slow as the root map. The benchmark was effectively attempting to beat ChaosTree using Java's own default interface methods.

The culprit was the java.util.Map interface itself. If you do not explicitly override modern Map methods like putIfAbsent(), Java provides a default implementation that executes a get(), checks for null, and then executes a put(). For a Tree data structure, this is devastating: it forces the CPU to traverse the entire height of the tree from root to leaf twice.

2. The Single-Traversal Mandate

To maintain equal footing (and eventual dominance) over the JDK, ChaosTree cannot rely on generic interface fallbacks.

I explicitly overrode putIfAbsent, compute, computeIfAbsent, computeIfPresent, and merge inside SubNaryMap and DescendingMapFacade. Instead of relying on the JDK's two-pass default, these methods now translate their bounds directly and delegate straight to the core AbstractNaryTreeMap engine, ensuring the operation is resolved in a single, highly optimized root-to-leaf traversal.

Decision: ChaosTree explicitly overrides all default Map mutation methods across all view classes (SubMaps, DescendingMaps) to brutally enforce single-traversal paths. I will never accept a 2x performance penalty introduced by a default JDK interface.

ADR 9: The Four Engines (Rejecting Theoretical Dogma)

1. The Textbook Answers

Computer Science textbooks provide standard answers for which data structures to use. They tell you that AVL Trees are more strictly balanced, making them better for read-heavy workloads, while Red-Black Trees (RBT) are looser, making them better for write-heavy workloads. They tell you that B-Trees are good for random access, while B+Trees dominate sequential range queries.

Standard libraries usually pick a winner on your behalf. The JDK designers blindly picked Red-Black Tree for java.util.TreeMap, forcing every Java developer to use it regardless of their actual workload.

2. Empirical Benchmarking Over Blind Trust

ChaosTree started as a journey into data structures. When the textbooks gave answers, I refused to blindly accept them. I implemented all of them and subjected them to the exact same grueling JMH benchmarking environments on modern JVMs.

The benchmarks revealed that theoretical Big-O notation often falls apart when confronted with modern CPU cache lines, Garbage Collection pauses, and branch prediction. Sometimes AVL beats RBT on inserts simply because of better memory alignment in a specific JVM version. Sometimes a B-Tree outperforms a B+Tree because the L1 cache happens to perfectly fit the working set.

Decision: ChaosTree implements all four clashing competitors: AvlTreeMap, RedBlackTreeMap, BTreeMap, and BPlusTreeMap. I do not make the decision for you. You have the exact same highly-optimized, mathematically verified API for all four engines. You are encouraged to benchmark your exact payload, on your exact hardware, against all four trees, and let the data decide which one to use.

ADR 10: The Raw Mind Behind the Bulk Loader

1. Attempt 1: The Wavy Form

Writing a B-Tree bulk loader from scratch is notoriously unforgiving. My first attempt was naive: just fill the leaf nodes left-to-right and try to move upwards in a "wavy form" to link the internal routing nodes on the fly. Result: The first test failed miserably. The edge cases for tree height and internal separator keys completely broke the logic.

2. Attempt 2: The Cleanup Fix

I realized that naive left-to-right packing leaves starving (underfull) internal nodes dangling at the right edge of the tree. I tried to patch the algorithm by adding a post-process cleanup step specifically designed to eliminate these dangling nodes. Result: The second test failed. Patching a structurally flawed tree with localized fixes just creates cascading edge cases.

3. Attempt 3: The Phase 1 & Phase 2 Sweep

I finally accepted the textbook database approach. I wrote a classic two-phase bulk loader:

• Phase 1: A greedy sweep to pack all the leaves left-to-right up to a target fill factor.
• Phase 2: Walk back up the tree and run an exhaustive repair sweep to fix underflows and rebalance the dangling right edge.

4. The Final Form: Top-Down Math

That painful 22-attempt journey was exactly what was required to truly understand the physics of B-Tree boundaries. Once I understood exactly why the two-phase approach was so brittle, I threw it out and derived the final implementation that exists in ChaosTree today.

By pre-computing exact mathematical capacity windows (Math.pow bounds) before descending, and smearing the remainder uniformly, the engine perfectly calculates a tree where underflow is mathematically impossible. The 22nd attempt taught me how to repair a tree. The final iteration taught me how to build a tree that never needs repairing.

5. Beyond Guava: Testing the Dragon Feed

Must read the test suite in detail! While Google Guava's testlib was phenomenal for verifying the standard NavigableMap contracts, it obviously does not cover custom extensions like the buildFromSorted Dragon Feed.

Because Guava couldn't test it, I had to write my own aggressively rigorous, randomized test suite to bombard the bulk loader. The test suite throws completely randomized datasets, wildly varying degree sizes, and random fill factors at the engine to prove that the mathematical capacity windows hold true under absolute chaos. The fact that the 22nd attempt finally passed was proven against this custom suite, not Guava.

ADR 11: Why ChaosTree when I already have JDK TreeMap?

1. 50% Less Memory Overhead

The standard JDK java.util.TreeMap relies on a classical Red-Black Tree implementation. Every single key-value pair inserted into the map requires the allocation of a Map.Entry wrapper object. For millions of elements, the JVM's 16-byte object header penalty causes the heap footprint to explode.

By utilizing N-ary architectures (B-Tree and B+-Tree) and a Structure-of-Arrays (SoA) layout, ChaosTree completely eliminates this wrapper object. It groups elements into contiguous, cache-friendly array blocks. In head-to-head benchmarks, ChaosTree consistently consumes over 50% less memory than the equivalent JDK TreeMap for identical datasets.

2. The "Dragon Feed" Factor (1.0f) for Absolute Read Speed

ChaosTree exposes a highly specialized bulk-loading mechanism (nicknamed the "Dragon Feed" via buildFromSorted). When initialized with a fill factor of 1.0f, the engine packs every single node's array to 100% capacity mathematically.

The result of a 1.0f factor Dragon Feed is a perfectly dense, perfectly balanced data structure. Because the keys[] arrays are completely saturated, binary searching down the tree executes with zero L1/L2 CPU cache misses. This provides the absolute fastest possible read speeds achievable on the JVM, completely dominating the scattered memory access patterns of the JDK's pointer-chasing Red-Black tree.

3. Equal Footing, Zero Compromise

If ChaosTree used a proprietary API, migrating away from the JDK would be a risky investment. But because ChaosTree flawlessly implements every contract, edge-case, and view (subMap, descendingMap) of the modern java.util.SequencedMap and NavigableMap interfaces, it serves as a zero-friction, drop-in replacement.

Decision: Use the JDK TreeMap if you are storing a few hundred elements where performance is irrelevant. Use ChaosTree if you are operating at scale, if you care about JVM heap pressure, and if you want to unleash the sheer CPU-level speed of the 1.0f Dragon Feed.

← Back to ChaosTree Home