Insert-only core · one epoch · fixed capacity N

Order Maintenance Explorer

Click an element to select it, then insert after it. Every operation does a constant amount of work: one insertion, a few split moves, and a few steps of the top-level job. Watch where that work goes.

Parameters

Apply and replay reruns the same operations under the new parameters. Values below the thresholds of docs/SPEC.md §7.1 (for example KG = 1, s ≤ 4, small β) can make guards fail. The structure then falls back to a synchronous rebuild, and answers stay correct.

quiet fresh sibling, being filled splitting, being drained ghost node (top tree) changed by the last operation tombstone

Top tree

live tree: weights, and where new nodes go stored path through a ghost: still decides the tag where the top-tree job is

Last operation

    Selected element

    Reservation

    Steps per operation

    How to read the picture

    Bottom row: the elements in list order (H is the head sentinel). Above it, the groups, which split once they reach G elements, and the chunks, whose thin bar shows the fill against capacity T, with the red tick at θ = ⌊2T/3⌋. A quiet chunk above θ waits in the priority queue. The reservation process takes the fullest one, places two fresh chunks around it, and starts a top-tree job. The rows above the chunks are the top tree, one row per height. Each bar covers the chunks whose stored path passes through that node, so a ghost (dashed) keeps its bar until the sweep has re-routed all of them. An element's key is (chunk tag, group label, element label), and order(x, y) compares keys. Shift-click a second element to try it.