Why We Chose MPTT (Modified Preorder Tree Traversal)
There are a few different strategies for tree implementation in a relational database. At the end of the day, we wanted a tree with one parent per node and zero or more children. That rules several im
## The Problem With Standard Tree Implementations
Socra needs to rapidly query all nodes under any given node — a core requirement for how the AI navigates and retrieves knowledge. This rules out the most common approach.
| Implementation | How It Works | Why We Rejected It |
|---|---|---|
| Adjacency List | Each node points to its direct parent | Descendant queries require recursive traversal — computationally brutal at scale |
| Nested Set | Encodes tree position as numeric ranges | Numerous drawbacks; not worth the tradeoffs |
| MPTT | Stores a unique path per node | Fast descendant queries; sortable siblings; our starting point |
Adjacency lists power ~90% of tree structures (Twitter included) and support infinite depth — but querying an entire subtree is prohibitively expensive. Not viable for our use case.
## Why MPTT, and What We Built On Top
MPTT stores each node's position as a path string (e.g., root → `1`, children → `11`, `12`). Finding all descendants of a node is a single prefix query. Sibling order is implicit in the path. Your computer's directory structure works similarly, minus sortability.
MPTT's known drawbacks: moving a node requires updating all descendant paths, there's no explicit parent-child link (risking orphaned nodes), and maximum depth is bounded by path length.
To address these, we layered on:
- **Explicit parent and root attributes** — enables O(1) parent lookups and protects against lost nodes
- **Human-readable path** — mirrors computer directory structure, doubles as clean URL generation
The result is a hybrid model: MPTT's fast subtree queries combined with direct relational pointers for the most common lookups.
## Outcome
After dozens of iterations and failed attempts, the hybrid tree performs efficiently across every query pattern we've needed. O(1) parent lookups, O(log n) insertions, fast descendant retrieval. The architecture is now the neural scaffold underpinning RSII's knowledge structure.
- [x] Implement hybrid tree model
- [x] Enhance querying with explicit parent/root attributes
- [x] Create user-friendly URL pathsBy Mike Morton