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