fractional-nested-sets

A tree data structure library that uses IEEE 754 floating-point lft/rgt values instead of integers. This eliminates the O(n) node-shifting penalty of traditional MPTT (Modified Preorder Tree Traversal) when inserting or moving nodes, while preserving O(1) subtree and ancestor queries.

Zero dependencies. Works in-memory or with any database via a pluggable storage adapter.

The Problem

Traditional nested sets (MPTT) store integer lft/rgt boundaries. Every time you insert or move a node, every node to the right of the insertion point must be renumbered:

Insert "Tablets" under "Electronics" (1000-node tree)
→ MPTT: UPDATE 500+ rows to shift lft/rgt values
→ FNS:  INSERT 1 row with a fractional lft/rgt

For read-heavy trees (menus, categories, org charts) that occasionally change, this write amplification is the bottleneck.

The Solution

Fractional Nested Sets place new lft/rgt values at the midpoint of adjacent boundaries using IEEE 754 floating-point arithmetic. No other nodes need to change.

When gaps eventually shrink below a precision threshold (~1e-7), a one-time rebalance reassigns clean integer values. In practice this happens rarely — roughly every few hundred mutations — and the amortized cost remains far below MPTT's per-operation penalty.

Install

npm install @abeedoo/fractional-nested-sets

Quick Start

import { FractionalNestedSet } from '@abeedoo/fractional-nested-sets';

const tree = new FractionalNestedSet();

tree.addRoot('electronics');
tree.addChild('electronics', 'phones');
tree.addChild('electronics', 'laptops');
tree.addChild('phones', 'iphones');
tree.addChild('phones', 'android');
tree.addChild('laptops', 'macbooks');

// Subtree query — all descendants
tree.getSubtree('phones');
// → [phones, iphones, android]

// Ancestor query — breadcrumb path from root
tree.getAncestors('macbooks');
// → [electronics, laptops, macbooks]

// Move a node — only the moved subtree is modified
tree.moveNode('macbooks', 'phones');

// Remove a subtree — no renumbering
tree.removeNode('android');

API

TreeOperations Interface

All three included implementations share this interface:

| Method | Description | |--------|-------------| | addRoot(id) | Insert a new root node | | addChild(parentId, childId) | Insert a child as the last child of a parent | | moveNode(nodeId, newParentId) | Move a subtree to a new parent | | removeNode(nodeId) | Remove a node and all its descendants | | getSubtree(nodeId) | All descendants (inclusive), O(1) filter on lft/rgt | | getAncestors(nodeId) | Path from root to node (inclusive) | | getChildren(parentId) | Direct children only | | getAllNodes() | Every node, sorted by lft | | getNode(id) | Single node lookup |

Every mutating method returns { nodesModified: number } — the count of nodes whose lft/rgt values actually changed. This is the key metric that demonstrates FNS's advantage.

Implementations

import { FractionalNestedSet } from '@abeedoo/fractional-nested-sets';
import { TraditionalMPTT } from '@abeedoo/fractional-nested-sets';
import { AdjacencyList } from '@abeedoo/fractional-nested-sets';

| Implementation | Writes | Reads | Use Case | |----------------|--------|-------|----------| | FractionalNestedSet | O(1) amortized | O(1) subtree/ancestor | Production use — best of both worlds | | TraditionalMPTT | O(n) per mutation | O(1) subtree/ancestor | Comparison baseline | | AdjacencyList | O(1) per mutation | O(n) subtree/ancestor | Comparison baseline |

Utility Functions

import { buildNested, printTree, validate } from '@abeedoo/fractional-nested-sets';

// Build a nested JSON structure (great for API responses)
const nested = buildNested(tree.getAllNodes());
// → [{ id: 'electronics', children: [{ id: 'phones', children: [...] }] }]

// Pretty-print for debugging
console.log(printTree(tree.getAllNodes()));
// electronics [1, 12]
//   phones [2, 9]
//     iphones [3, 4]
//     android [5, 6]
//   laptops [10, 11]

// Validate nested-set invariants
const errors = validate(store);
// → [] (empty array = valid tree)

Precision Utilities

import { bisect, hasAdequateGap, needsRebalance, PRECISION_THRESHOLD } from '@abeedoo/fractional-nested-sets';

bisect(1, 2);           // → 1.5
hasAdequateGap(1, 2);   // → true
hasAdequateGap(1, 1 + 1e-8); // → false (below threshold)

Custom Storage Adapter

By default, everything runs in-memory. To persist to a database, implement the StorageAdapter interface:

import { FractionalNestedSet, type StorageAdapter, type TreeNode } from '@abeedoo/fractional-nested-sets';

const adapter: StorageAdapter = {
  get(id: string): TreeNode | undefined { /* SELECT by id */ },
  getAll(): TreeNode[] { /* SELECT * */ },
  set(node: TreeNode): void { /* UPSERT */ },
  delete(id: string): void { /* DELETE by id */ },
  clear(): void { /* TRUNCATE */ },
};

const tree = new FractionalNestedSet(adapter);

The TreeNode shape your table needs:

| Column | Type | Notes | |--------|------|-------| | id | string | Primary key | | parentId | string \| null | Foreign key to self | | lft | float8 / double | Left boundary — use a float type, not integer | | rgt | float8 / double | Right boundary | | depth | integer | Nesting level (0 = root) |

Index lft and rgt for fast range queries:

CREATE INDEX idx_tree_lft ON categories (lft);
CREATE INDEX idx_tree_rgt ON categories (rgt);

How It Works

Traditional MPTT assigns contiguous integers:

Electronics [1, 12]
  Phones [2, 7]
    iPhone [3, 4]
    Android [5, 6]
  Laptops [8, 11]
    MacBook [9, 10]

Inserting "Tablets" after "Laptops" requires shifting lft/rgt for every node with values >= 12 to make room for [12, 13]. In a 10,000-node tree, that's thousands of updates.

Fractional Nested Sets instead bisect the available gap:

Electronics [1, 12]
  Phones [2, 7]
    iPhone [3, 4]
    Android [5, 6]
  Laptops [8, 11]
    MacBook [9, 10]
  Tablets [11.5, 11.75]    ← placed in the gap, nothing else moves

The nested-set query semantics are identical — WHERE lft >= 11.5 AND rgt <= 11.75 still returns the correct subtree. But zero other rows were touched.

Auto-Rebalance

After many bisections in the same region, gaps shrink toward zero. When any gap falls below 1e-7 (configurable), the library triggers a full rebalance that reassigns clean integer values in a single DFS pass. This is O(n) but happens rarely — the amortized cost per operation remains O(1).

// Custom threshold (default is 1e-7)
const tree = new FractionalNestedSet(undefined, 1e-5);

Benchmarks

Run locally:

npm run bench

Results from a 200-node tree with 50 moves:

| Operation | FNS nodesModified | MPTT nodesModified | Reduction | |-----------|--------------------:|---------------------:|----------:| | 200 inserts | 285 | 8,799 | 97% | | 50 moves | 50 | 8,052 | 99% |

The nodesModified count represents how many nodes had their lft/rgt values rewritten. This directly translates to database UPDATE statements in a real application.

Development

npm test              # Run all tests
npm run test:watch    # Watch mode
npm run bench         # Run benchmarks
npm run build         # Compile TypeScript
npm run check         # Type-check without emitting

License

MIT