nested

README

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();

Documentation

Index

• func AddNodeByParent(db *sql.DB, id int64, name string, parentID int64) error
• func AddNodeBySibling(db *sql.DB, id int64, name string, siblingID int64) error
• func AddRootNode(db *sql.DB, id int64, name string) error
• func RemoveNodeAndDescendants(db *sql.DB, id int64) error
• func RemoveOneNode(db *sql.DB, id int64) error
• func SetTableName(name string)
• type Node
  • func GetChildren(db *sql.DB, id int64) ([]Node, error)
  • func GetDescendants(db *sql.DB, id int64) ([]Node, error)
  • func GetNodeDetail(db *sql.DB, id int64) (*Node, error)
  • func GetNodesByDepth(db *sql.DB, depth int32) ([]Node, error)

Functions

func AddNodeByParent

func AddNodeByParent(db *sql.DB, id int64, name string, parentID int64) error

AddNodeByParent adds a new node with certain parent, new node will be the last child of the parent.

func AddNodeBySibling

func AddNodeBySibling(db *sql.DB, id int64, name string, siblingID int64) error

AddNodeBySibling add a new node right after sibling

func AddRootNode

func AddRootNode(db *sql.DB, id int64, name string) error

AddRootNode adds a new root. There could be more than one root node, and the new root will be the left most one, or AddNodeBySibling should be used to insert a new root after another one.

func RemoveNodeAndDescendants

func RemoveNodeAndDescendants(db *sql.DB, id int64) error

RemoveNodeAndDescendants removes node and all its descendants -- it removes the whole subtree.

func RemoveOneNode

func RemoveOneNode(db *sql.DB, id int64) error

RemoveOneNode removes one node and move all its descentants 1 level up -- it removes the certain node from the tree only.

func SetTableName

func SetTableName(name string)

SetTableName for query strings

Types

type Node

type Node struct {
	ID          int64
	Node        string
	ParentID    int64
	Depth       int32
	Path        []int64
	PathName    []string
	NumChildren int32
}

Node detail with path from root to node

func GetChildren

func GetChildren(db *sql.DB, id int64) ([]Node, error)

GetChildren returns all immediate children of node

func GetDescendants

func GetDescendants(db *sql.DB, id int64) ([]Node, error)

GetDescendants returns sub tree of node

func GetNodeDetail

func GetNodeDetail(db *sql.DB, id int64) (*Node, error)

GetNodeDetail with path from root

func GetNodesByDepth

func GetNodesByDepth(db *sql.DB, depth int32) ([]Node, error)

GetNodesByDepth returns all nodes of certain depth