Nested set model
New to topics? Read the documentation here!
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
- Child 1.1
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, physicsWhen we want to insert one element, e.g. so we have a method:
limit, normally under calculus, we have to specify:- parent
- index within parent
insert(parent, previousSibling)