ChaosTree: Node Architecture & Mathematics

ChaosTree diverges from textbook CLRS (Cormen, Leiserson, Rivest, and Stein) implementations to extract maximum mechanical sympathy from the Java Virtual Machine (JVM). This document details the array capacity mathematics, the Structure-of-Arrays (SoA) layout, and the crucial differences between the BTreeMap and BPlusTreeMap engines.

1. The 2t Capacity Math & The Overflow Slot

Standard B-Tree and B+-Tree literature defines a node capacity based on a degree parameter t (where t ≥ 3). Textbook CLRS defines the maximum number of keys in a node as maxKeys = 2t - 1.

In ChaosTree, maxKeys is indeed 2t - 1, but the physical arrays are allocated to size 2t.

int maxKeys = degree << 1; // 2t physical slots allocated
this.keys = new Object[maxKeys];

This creates a dummy slot (or overflow slot) as illustrated in the SVG diagram above. By allocating one extra slot beyond the legal mathematical maximum, ChaosTree can use an insert-then-split architecture instead of the traditional split-then-insert.

Traditional (Preemptive): If node is full (2t-1), split it. Then figure out which half the new key belongs to, and insert it.

ChaosTree (Overflow): Unconditionally insert the key. The node temporarily holds 2t keys. Then, while (current.keyCount > maxKeys), split the node and push the separator up.

This completely eliminates the need to branch or reason about pending keys during a split, removing complex control flow from the JIT hot-path.

2. Structure of Arrays (SoA) for L2 Cache Locality

Standard Java implementations like java.util.TreeMap use a Structure-of-Objects layout. Every node is an Entry<K,V> that holds pointers to left, right, parent, color, key, and value. Binary searching forces the CPU to drag values and node pointers through the CPU cache line.

ChaosTree uses Structure of Arrays (SoA):

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

When ChaosTree searches a node, it runs a binary search exclusively over the keys[] array. The CPU can fetch consecutive keys in a single L2 cache line without touching a single value or child pointer.

3. BTreeMap vs BPlusTreeMap: The GC Null Discriminator

A classical B-Tree stores values in both internal routing nodes and leaf nodes. A B+-Tree pushes all values down to the leaf nodes, leaving internal nodes strictly as a routing index.

ChaosTree leverages this mathematical distinction to ruthlessly optimize Garbage Collection retention:

Array allocations by node type
Tree Type	Leaf Node Arrays	Internal Node Arrays
BTreeMap	`keys[]`, `values[]`	`keys[]`, `values[]`, `child[]`
BPlusTreeMap	`keys[]`, `values[]`	`keys[]`, null, `child[]`

boolean needsValues = isLeaf || (this instanceof BTreeMapNode);
this.values = needsValues ? new Object[maxKeys] : null;

Because internal nodes account for roughly 1/t of the total tree volume, dropping the values[] array entirely in BPlusTreeMap.

4. Analysation of JOL at 1M

Build paths: put = sequential put(i, i) for 0..999,999 (leaves settle at t = 64 keys); import = importFlatMatrix(exportFlatMatrix(), 1.0f) (leaves at 127 keys).

Constants (JOL, compressed oops): Integer = 16 B, TreeMap$Entry = 40 B, TreeMap = 48 B, BTreeMapNode = 32 B, BPlusTreeMapNode = 40 B, BTreeMap/BPlusTreeMap = 72 B.

t = 64
physical slots    = 2t     = 128
keys[] / values[] = 16 + 128*4       = 528 B
child[]           = 16 + (2t+1)*4    = 532 -> 536 B (8 B aligned)
Integer objects   = 2*1,000,000 - 128 (cache -128..127) = 1,999,872
Integer bytes     = 1,999,872 * 16   = 31,997,952 B

Node census (from JOL counts)

internal = count(Node[])
leaves   = count(Node) - internal

put()       : 15,873 - 248 = 15,625 leaves, 248 internal
import 1.0f:  7,939 -  63 =  7,876 leaves,  63 internal

keys per leaf: 1,000,000 / 15,625 = 64.00
               1,000,000 /  7,876 = 126.97

Object[] check
  BTree  : 2 * 15,873          = 31,746
  B+Tree : 2 * 15,625 + 248    = 31,498
  B+ import: 2 *  7,876 +  63    = 15,815

Totals

Structure	Node[]	Object[]	Nodes	Map	Structure	+ Integers
TreeMap	-	-	1,000,000 * 40 = 40,000,000	48	40,000,048	71,998,000
BTree (put)	248 * 536 = 132,928	31,746 * 528 = 16,761,888	15,873 * 32 = 507,936	72	17,402,824	49,400,776
B+Tree (put)	248 * 536 = 132,928	31,498 * 528 = 16,630,944	15,873 * 40 = 634,920	72	17,398,864	49,396,816
B+Tree (import 1.0f)	63 * 536 = 33,768	15,815 * 528 = 8,350,320	7,939 * 40 = 317,560	72	8,701,720	40,699,672

BTree vs B+Tree delta (same shape)

B+ saves  : 248 values[] * 528 = 130,944 B
B+ pays   : 15,873 nodes * 8 B = 126,984 B   (next, prev)
net       : 130,944 - 126,984  =   3,960 B   = 49,400,776 - 49,396,816

Ratios

per entry, structure : TreeMap 40.00 | B+ put 17.40 | B+ import 8.70 B
per entry, total     : TreeMap 72.00 | B+ put 49.40 | B+ import 40.70 B

vs TreeMap total     : 49,396,816 / 71,998,000 = 0.6861  (-31.4%)
                       40,699,672 / 71,998,000 = 0.5653  (-43.5%)
vs TreeMap structure : 40,000,048 / 17,398,864 = 2.30x
                       40,000,048 /  8,701,720 = 4.60x

Integer share of B+ import total : 31,997,952 / 40,699,672 = 78.6%

Slot waste and floor

dead leaf slots put    : 15,625 * 2 * (128 - 64) * 4 = 8,000,000 B
dead leaf slots import :  7,876 * 2 * (128 - 127) * 4 =    63,008 B   (127 keys/leaf)
ref floor (2 refs/entry) : 2 * 1,000,000 * 4 = 8,000,000 B
B+ import structure / floor : 8,701,720 / 8,000,000 = 1.088

Raw JOL output (1M)

java.util.TreeMap@4edde6e5d footprint:
     COUNT       AVG       SUM   DESCRIPTION
   1999872        16  31997952   java.lang.Integer
         1        48        48   java.util.TreeMap
   1000000        40  40000000   java.util.TreeMap$Entry
   2999873            71998000   (total)

chaos.tree.naryMap.BTreeMap@5ef0e311d footprint:
     COUNT       AVG       SUM   DESCRIPTION
       248       536    132928   [Lchaos.tree.naryMap.BTreeMapNode;
     31746       528  16761888   [Ljava.lang.Object;
         1        72        72   chaos.tree.naryMap.BTreeMap
     15873        32    507936   chaos.tree.naryMap.BTreeMapNode
   1999872        16  31997952   java.lang.Integer
   2047740            49400776   (total)

chaos.tree.naryMap.BPlusTreeMap@40b02d47d footprint:
     COUNT       AVG       SUM   DESCRIPTION
       248       536    132928   [Lchaos.tree.naryMap.BPlusTreeMapNode;
     31498       528  16630944   [Ljava.lang.Object;
         1        72        72   chaos.tree.naryMap.BPlusTreeMap
     15873        40    634920   chaos.tree.naryMap.BPlusTreeMapNode
   1999872        16  31997952   java.lang.Integer
   2047492            49396816   (total)

chaos.tree.naryMap.BPlusTreeMap@64ec7f47d footprint: (importFlatMatrix, 1.0f)
     COUNT       AVG       SUM   DESCRIPTION
        63       536     33768   [Lchaos.tree.naryMap.BPlusTreeMapNode;
     15815       528   8350320   [Ljava.lang.Object;
         1        72        72   chaos.tree.naryMap.BPlusTreeMap
      7939        40    317560   chaos.tree.naryMap.BPlusTreeMapNode
   1999872        16  31997952   java.lang.Integer
   2023690            40699672   (total)

5. The Top-Down Bulk Loader Arithmetic

ChaosTree's buildFromSorted eliminates the "Phase 2" repair pass found in standard database bulk-loaders by computing exact capacity windows before descending.

B-Tree capacity bound: (numKeys + 1) / maxChild^h ≤ Children ≤ (numKeys + 1) / minChild^h
B+-Tree capacity bound: maxSubtree = maxKeys * maxChild^h-1

By proving that C (the chosen number of children) fits within the clamped window, ChaosTree guarantees every child will land inside its legal [minKeys, maxKeys] boundary before the recursion even reaches it. The remainder is smeared uniformly (1 per child) to bound the worst-case sibling imbalance at exactly 1 key. This makes underflow mathematically impossible and fully eliminates the need for a secondary tree-repair traversal.

← Back to ChaosTree Home