= Nested set model
{wiki}
This is particularly important in <SQL>: <Nested set model in SQL>, as it is an efficient way to transverse trees there, since querrying parents every time would require multiple disk accesses.
The <ASCII art> visualizations from https://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)
``