Traces are trees — each span can have child spans. Nested set encoding converts
this tree into flat integer pairs (left, right) assigned during a depth-first traversal.
Once encoded, checking "Is A an ancestor of B?" becomes a simple integer comparison:
A.left < B.left AND A.right > B.right.
No tree traversal needed.
① Trace Tree
A sample 8-span trace. Click "Run DFS" to see the depth-first traversal assign left/right numbers.
② Nested Set Table
Every span now has a left/right pair. These integers live in a typed array — compact and fast.
Span
Service
Left
Right
Depth
③ Is Ancestor?
Click any two spans in the tree above to test ancestry. First click = potential ancestor, second click = potential descendant.
Click a span in the tree above to select the ancestor candidate.
Key insight: Parent-child stored as integer indices in typed arrays makes
structural queries SIMD-friendly array scans. Instead of walking a tree, you compare two
numbers — and that works for "find all descendants" too:
parent.left < child.left AND parent.right > child.right.
o11ykit