mptt

README

gorm-mptt

预排序遍历树算法(MPTT)树

预排序遍历树算法全称是：Modified Preorder Tree Traversal 简称 MPTT。主要应用于层级关系的存储和遍历。 MPTT在遍历的时候很快，但是其他的操作就会变得很慢。对于需要频繁查询，但修改不是很频繁的树状数据结构， 使用MPTT树进行存储，可以让数据查询更为高效。

一棵标准的树结构：

使用方法

1. 定义model

   type CustomTree struct {
       mptt.ModelBase
       Name     string        `gorm:"type:varchar(125);index:custom_tree_name" validate:"required"`
       Children []*CustomTree `gorm:"-"`
   }
   

2. 创建树manager。其中gormDb类型为*gorm.DB。

   manager, err := mptt.NewTreeManager(gormDb, new(CustomTree))
   assert.Nil(t, err)
   

节点增加

1. 使用CreateNode方法可以快速创建节点。需要确保node的ParentID信息正确。如ParentID为空，则将插入一棵新的树的根节点。

   err := manager.CreateNode(node)
   

2. 插入subNode，作为parentNode的最后一个孩子节点。

   err := manager.InsertNode(subNode, parentNode, mptt.LastChild)
   

3. 插入subNode，作为parentNode的第一个孩子节点。

   err := manager.InsertNode(subNode, parentNode, mptt.FirstChild)
   

4. 插入newNode，位置为existsNode的左边（前面）

   err := manager.InsertNode(newNode, existsNode, mptt.Left)
   

5. 插入newNode，位置为existsNode的左边（后面）

   err := manager.InsertNode(newNode, existsNode, mptt.Right)
   

节点移动

1. 已知节点主键ID，和目标节点的ID。使用MoveNodeByID方法移动

   ok, err := manager.MoveNodeByID(19, 50, mptt.Left) // 将node(19)移动到node(50)的左边
   ok, err := manager.MoveNodeByID(19, 50, mptt.Right) // 将node(19)移动到node(50)的右边
   ok, err := manager.MoveNodeByID(19, 50, mptt.FirstChild) // 将node(19)移动为node(50)的第一个孩子节点
   ok, err := manager.MoveNodeByID(19, 50, mptt.LastChild) // 将node(19)移动为node(50)的最后一个孩子节点
   

2. 已知节点和目标节点对象。使用MoveNode方法移动。最后一个refreshTarget为true时，会主动修正nodeB对象中的MPTT信息。

   ok, err := manager.MoveNode(nodeA, nodeB, mptt.Left) // 将node(19)移动到node(50)的左边
   ok, err := manager.MoveNode(nodeA, nodeB, mptt.Right, true) // 将node(19)移动到node(50)的右边
   

节点删除

1. 包括按ID删除方法DeleteNodeByID，按对象删除方法DeleteNode。

   err := manager.DeleteNodeByID(19)
   err := manager.DeleteNode(toDeleteNode, true) // 第二个参数代表代表确认node中的MPTT信息准确无误，无需框架主动刷新信息后再执行删除。
   

节点查询

使用manager进行树中信息查询时，需要先使用Node()方法锚定某个已知节点(manager.Node(node).QueryFuncXXX)。如下：

// 从数据库中重新查询node信息，确保MPTT信息准确，有部分方法，如IsRootNode，不会实际查库，
// 主要根据MPTT信息计算的到结果。所以当不确认node信息是否准确时，建议RefreshNode
err := manager.RefreshNode(node)

// 查询node节点是否为根节点
isRoot := manager.Node(node).IsRootNode()

// 查询node节点是否为叶子节点
isLeaf := manager.Node(node).IsLeafNode()

// 查询node节点是否为子节点
isChild := manager.Node(node).IsChildNode()

// 查询node节点的level
level := manager.Node(node).GetLevel()

// 查询node节点所在树的根节点
err = manager.Node(node).GetRoot(&result)

// 查询node节点下级的所有叶子节点
err = manager.Node(node).GetLeafNodes(&results)

// 查询node节点的所有子节点
err = manager.Node(node).GetChildren(&results)

// 查询node节点的所有兄弟节点（parentID相同的节点）
err = manager.Node(node).GetSiblings(&results)

// 查询node节点的所有子孙节点， includeSelf为真时，列表包含当前节点
err = manager.Node(node).GetDescendants(&results)
err = manager.Node(node).GetDescendants(&results, includeSelf)

// 查询node节点的所有祖先节点， includeSelf为真时，列表包含当前节点。该方法返回的数据默认从根节点到当前node排序。
err = manager.Node(node).GetAncestors(&results)
err = manager.Node(node).GetAncestors(&results, includeSelf)

// 查询Family节点列表，包含祖先节点和子孙节点
err = manager.Node(node).GetFamily(&results)

// 查询node的下一个兄弟节点，可以传入conditions(gorm过滤器)，用于过滤符合条件的右侧兄弟
err = manager.Node(node).GetNextSibling(&result, conditions...)

// 查询node的前一个兄弟节点，可以传入conditions(gorm过滤器)，用于过滤符合条件的左侧兄弟
err = manager.Node(node).GetPreviousSibling(&result, conditions...)

// 查询node节点是否为target节点的祖先节点。includeSelf == true时，node == target也为真
isAncestor := manager.Node(node).IsAncestorOf(target, includeSelf)

// 查询node节点是否为target节点的子孙节点。includeSelf == true时，node == target也为真
IsDescendant := manager.Node(node).IsDescendantOf(target, includeSelf)

Rebuild方法

使用场景：

1. 当有节点不是通过TreeManager中的方法创建，需要修正树中节点的MPTT信息；
2. 当并发处理导致树上的MPTT信息错乱时；
3. 其他任何导致树上MPTT信息不准确，需要修正这些数据时

都可以调用Rebuild来修正整个森林，PartialRebuild修正特定的树：

err = manager.Rebuild()
err = manager.PartialRebuild(treeID)

备注

设计上，为了保证已有的树结构，可以使用本库快速迁移到MPTT，ID、ParentID列支持除了数值和string类型，但当前只测试了内嵌mptt.ModelBase的int类型场景。 left、right、level、tree_id等业务无关列强制要求使用int类型。

TODO: 测试string类型主键。

manager, err := mptt.NewTreeManager(gormDb, new(CustomTree), mptt.WithAttrs(colFields))

Documentation

Index

• Constants
• Variables
• func IsNil(object interface{}) bool
• type KeyColumnFields
• type KeyField
• type KeyFields
• type ModelBase
• type Option
  • func WithAttrs(fields KeyColumnFields) Option
  • func WithTableName(name string) Option
• type PositionEnum
• type TreeManager
  • func NewTreeManager(db *gorm.DB, modelPtr interface{}, opts ...Option) (TreeManager, error)
• type TreeNode

Constants

const (
	TableName          = "[table_tree]"
	ColumnIDAttr       = "[id]"
	ColumnParentIDAttr = "[parent_id]"
	ColumnTreeIDAttr   = "[tree_id]"
	ColumnLeftAttr     = "[left]"
	ColumnRightAttr    = "[right]"
	ColumnLevelAttr    = "[level]"

	DefaultIDColumn       = "ID"
	DefaultParentIDColumn = "ParentID"
	DefaultTreeIDColumn   = "TreeID"
	DefaultLeftColumn     = "Lft"
	DefaultRightColumn    = "Rght"
	DefaultLevelColumn    = "Lvl"
)

MPTT Table consts

Variables

var (
	UnsupportedPositionError = errors.New("unsupported position error")
	ModelTypeError           = errors.New("tree node data should be a pointer")
)

Functions

func IsNil

func IsNil(object interface{}) bool

IsNil if the object is nil

Types

type KeyColumnFields

type KeyColumnFields struct {
	IDFieldName     string
	ParentFieldName string
	TreeIDFieldName string
	LeftFieldName   string
	RightFieldName  string
	LevelFieldName  string
}

KeyColumnFields for custom mptt model without embedded struct ModelBase

type KeyField

type KeyField struct {
	*schema.Field
	Attr string
}

KeyField mptt has id parent_id tree_id left right level fields id parent_id tree_id only support positive integer or string left right level only support positive integer

type KeyFields

type KeyFields struct {
	ID     KeyField
	Parent KeyField
	Tree   KeyField
	Left   KeyField
	Right  KeyField
	Level  KeyField
}

type ModelBase

type ModelBase struct {
	ID       int `gorm:"primaryKey" json:"id"`
	ParentID int `gorm:"default:0;index" json:"parent_id"`
	TreeID   int `gorm:"index" json:"tree_id"`
	Lvl      int `gorm:"index" json:"lvl"`
	Lft      int `gorm:"index" json:"lft"`
	Rght     int `gorm:"index" json:"rght"`
}

ModelBase default mptt base model for user to embedded

type Option

type Option func(options *treeOptions)

Option ...

func WithAttrs

func WithAttrs(fields KeyColumnFields) Option

WithAttrs custom model without Embedded Struct ModelBase

func WithTableName

func WithTableName(name string) Option

WithTableName custom table name

type PositionEnum

type PositionEnum string

const (
	LastChild  PositionEnum = "last-child"
	FirstChild PositionEnum = "first-child"
	Left       PositionEnum = "left"
	Right      PositionEnum = "right"
)

type TreeManager

type TreeManager interface {
	GormDB() *gorm.DB
	CreateNode(node interface{}) error
	InsertNode(node, target interface{}, position PositionEnum) error
	MoveNode(node, target interface{}, position PositionEnum, refreshTarget ...bool) (bool, error)
	MoveNodeByID(nodeID, targetID interface{}, position PositionEnum) (bool, error)
	DeleteNode(n interface{}, doNotRefresh ...bool) error
	DeleteNodeByID(nodeID interface{}) error

	Rebuild() error
	PartialRebuild(treeID int) error

	RefreshNode(node interface{}) error
	Node(node interface{}) TreeNode
}

TreeManager ...

func NewTreeManager

func NewTreeManager(db *gorm.DB, modelPtr interface{}, opts ...Option) (TreeManager, error)

NewTreeManager create mptt tree manager

type TreeNode

type TreeNode interface {
	GetAncestors(outListPtr interface{}, ascending, includeSelf bool) error
	GetDescendants(outListPtr interface{}, includeSelf bool) error
	GetFamily(outListPtr interface{}) error // my ancestors and my descendants
	GetChildren(outListPtr interface{}) error
	GetLeafNodes(outListPtr interface{}) error
	GetSiblings(outListPtr interface{}, includeSelf bool) error
	GetNextSibling(outPtr interface{}, conds ...interface{}) error
	GetPreviousSibling(outPtr interface{}, conds ...interface{}) error
	GetRoot(outPtr interface{}) error
	GetDescendantCount() int
	GetLevel() int
	IsChildNode() bool
	IsLeafNode() bool
	IsRootNode() bool
	IsDescendantOf(other interface{}, includeSelf bool) bool
	IsAncestorOf(other interface{}, includeSelf bool) bool
}