{wiki}

= Nested set index
{synonym}
{title2}

How to implement <Nested set model> in <SQL>:
* https://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/42781302#42781302 contains the correct left/size representation and update queries, which makes it much easier to maintain the tree without having to worry about the sizes of siblings which are constant
* https://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/194031#194031 amazing ASCII art representations of the structure. Unfortunately uses a wonky left/right representation, rather than the much more natural left/size representation from the other post


Nested set model in SQL

{wiki}

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 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)
``


Ciro Santilli @cirosantilli 37

 Incoming links: Nested set model