Nested Set Model

Nested Set Model (or Modified Preorder Tree) represents nested sets (trees or hierarchies) in relational databases. See wikipedia.

Model in short

The nested model:

1. assigns two numbers for each node as left and right, that
2. left of each node is less than all its children's left, and
3. right of each node is greater than all its children's right.

Numbers could be assigned according to a preorder tree traversal, which visits each node twice, and assigns numbers at both visits.

• Then querying all descendants of a node could be efficiency as:

SELECT child.id, child.node, child.lft, child.rgt
    FROM `nested` parent, `nested` child
    WHERE child.lft BETWEEN parent.lft AND parent.rgt
    AND parent.id=@node_id

• And querying the path from root to any node could be:

SELECT parent.id, parent.node, parent.lft, parent.rgt
    FROM `nested` parent, `nested` child
    WHERE child.lft BETWEEN parent.lft AND parent.rgt
    AND child.id=@node_id
    ORDER BY parent.lft

• Another column depth is used to record depth of the node, to query immediate children of a node efficiently, and the querying could be:

SELECT child.id, child.node, child.lft, child.rgt
    FROM `nested` parent, `nested` child
    WHERE child.lft BETWEEN parent.lft AND parent.rgt
    AND child.depth=parent.depth+1
    AND parent.id=@node_id

The nested model is also suitable for trees with more than one root, forests.

Test clothing categories

Test data used in nested_test.go are collected from previous wikipedia article.

- Clothing
    - Men's
        - Suits
            - Slacks
            - Jackets
    - Women's
        - Dresses
            - Evening Gowns
            - Sun Dresses
        - Skirts
        - Blouses

Traversal and number nodes as:

Demo

Chinese division data

Store Chinese division data with nested sets:

1. build a division tree from raw data,
2. assign left and right number for divisions by preorder tree traversal,
3. generate sql inserting queries

Data collected from 中国行政区划数据. Initial inserting SQL in division.sql are generated with build.go:

$ cd division && go run build.go   # generates data inserting sql 

T** product categories data

Store product category info and structure with nested sets:

1. run spider/spider.py to query data from t**,
2. build sql inserting data data/categoryInfo.sql and data/categoryTree.sql as in build_test.go

Use as dependency

1. create new table as in createtable.sql with your table name;
2. initialize table as in division/build.go, or
3. call Add...() continually as in TestInserting();
4. call SetTableName() in your init();