 Nested set model

ID: nested-set-model

 Top articles  Latest articles New article in topic

Ciro Santilli 37 Updated 2025-07-16

This is particularly important in SQL: Nested set model in SQL, as it is an efficient way to transverse trees there, since querying parents every time would require multiple disk accesses.

The ASCII art visualizations from stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/194031#194031 are worth reproducing.

As a tree:

Root 1
- Child 1.1
  - Child 1.1.1
  - Child 1.1.2
- Child 1.2
  - Child 1.2.1
  - Child 1.2.2

As the sets:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

Consider the following nested set:

0, 8, root
  1, 7, mathematics
    2, 3, geometry
      3, 6, calculus
        4, 5, derivative
        5, 6, integral
      6, 7, algebra
  7, 8, physics

When we want to insert one element, e.g. limit, normally under calculus, we have to specify:

parent
index within parent

so we have a method:

insert(parent, previousSibling)

 Read the full article

 New to topics? Read the docs here!