无限级

在程序设计中,有很多需求都是无限级的,例如:无限级菜单,邀请人,目录无限级,地区分类,等等

无限级的实现方案

最简单的实现方案则是增加一个pid,即可实现无限级:

## data_list
- id \`int\`
- pid \`int\`
- name \`string\`
``````sql
CREATE TABLE \`test\`.\`data_list\`  (
  \`id\` int(0) NOT NULL AUTO_INCREMENT,
  \`pid\` int(0) NULL COMMENT '上级id',
  \`name\` varchar(255) NULL COMMENT '名称',
  PRIMARY KEY (\`id\`),
  INDEX \`idx_pid\`(\`pid\`)
);

插入n条测试数据:

insert into data_list(id,pid,name) values(1,0,'顶级测试1');
insert into data_list(id,pid,name) values(2,0,'顶级测试2');
insert into data_list(id,pid,name) values(3,0,'顶级测试3');
insert into data_list(id,pid,name) values(4,1,'2级1测试1');
insert into data_list(id,pid,name) values(5,2,'2级2测试2');
insert into data_list(id,pid,name) values(6,2,'2级2测试3');
insert into data_list(id,pid,name) values(7,5,'3级5测试1');
insert into data_list(id,pid,name) values(8,7,'4级7测试1');

获取id8的上级代码为:

我们只需要查询出id 8 的消息,然后根据pid就可以找到id8的上级

package main

import (
   "fmt"
   _ "github.com/go-sql-driver/mysql"
   "github.com/jinzhu/gorm"
)

type dataStruct struct {
   Id   int
   Pid  int
   Name string
}

func main() {
   dbConn, err := gorm.Open("mysql", "root:123456@tcp(localhost:3306)/test?charset=utf8&parseTime=True&loc=Local")
   if err != nil {
      panic(err)
   }
   defer dbConn.Close()
   id := 8
   data := getInfo(dbConn, id)
   fmt.Println("data:", data)
   parentData := getInfo(dbConn, data.Pid)
   fmt.Println("parentData:", parentData)
}

func getInfo(db \*gorm.DB, id int) (data \*dataStruct) {
   data = &dataStruct{}
   db.Table("data_list").Where("id = ?", id).First(&data)
   return data
}

下面的go代码将简写,不再复制import代码,数据库初始化代码以及结构体

获取id2的直属下级的代码为:

我们只需要数据库查询pid=2的,即是2的下级

func getChildList(db *gorm.DB, id int) (data []dataStruct) {
   db.Table("data_list").Where("pid = ?", id).Find(&data)
   return data
}

func main() {
   id := 2
   list := getChildList(dbConn, id)
   fmt.Println(list)
}

如何获取id8的所有上级呢?

同上,我们先查出8的上级,再通过8的上级pid再查,如此往复.....

我们需要不断的循环递归进行获取:

func main() {
   id := 8
   ids := getParentIds(dbConn, id, []int{})
   fmt.Println(ids)
}

func getParentIds(db *gorm.DB, id int, ids []int) []int {
   ids = append(ids, id)
   //获取id的信息
   data := getInfo(db, id)
   //获取父级id
   parentId := data.Pid
   if parentId > 0 {
      return getParentIds(db, parentId, ids)
   }
   return ids
}

func getInfo(db \*gorm.DB, id int) (data \*dataStruct) {
   data = &dataStruct{}
   db.Table("data_list").Where("id = ?", id).First(&data)
   return data
}

获取id2的所有下级(下级的下级)

同上,我们需要先查出id2的直属下级,再遍历所有的下级的下级......

func main() {
   id := 2
   list := getAllChildList(dbConn, id)
   fmt.Println(list)
}

func getAllChildList(db *gorm.DB, id int) (data []dataStruct) {
   childList := getChildList(db, id)
   childDataList := make([]dataStruct, 0)
   childDataList = append(childDataList, childList...)
   for _, child := range childList {
      dataList := getAllChildList(db, child.Id)
      childDataList = append(childDataList, dataList...)
   }

   return childDataList
}
func getChildList(db *gorm.DB, id int) (data []dataStruct) {
   db.Table("data_list").Where("pid = ?", id).Find(&data)
   return data
}

就这样,很简单,我们已经实现了一个传统的无限级功能!那么能优化吗?

无限级的优化

在优化之前,我们需要讨论上面的无限级到底有什么问题,要怎么优化

我们可以看出,在查询单一层级的时候,都是需要一条sql即可完成,

而在查询所有上级和所有下级时,出现了各种递归查找,如果你有1万个下级,可能需要查询1万次数据!

透过问题看本质,为什么会需要这么多次查询,该怎么优化?递归查询到底会慢在哪里?

我们可以总结为2点:

1:查询了太多次数据库,每次都有网络io的产生,并且需要等待查询完才能进行下一次查询

2:递归遍历了多次,每次查询上下级,都得去算一遍上下级关系.理论上,上下级关系一旦确定是不会再发生更改的,不需要重新计算

针对这2点问题,我们可以规划优化方案

1:只算一次,将会员的计算结果缓存

2:将整个会员数据缓存,使用时不查数据库,查redis

3:将上下级的数据缓存,需要查询时,直接根据缓存的id去 "id in" 数据库

4:通过存储过程去查询所有数据,因为没有io消耗,会非常快

5:使用节点图数据库neo4j  或者jsonb方案存储

在本文中,将说明3,4 方案的实现

存储过程优化

存储过程优化点在于,可以节省程序查询数据库的部分,节省大量的io,从而提高查询速度:

查询所有下级:

DROP PROCEDURE IF EXISTS \`get_child_ids\` -- 如果存在,则删除存储过程

CREATE DEFINER=\`root\`@`%` PROCEDURE \`get_child_ids\`(dataId INT(11))
BEGIN
    #Routine body goes here...
    declare ids LONGTEXT default '';
    declare parentId INT(11) default '0';
    declare childIds LONGTEXT default '';
    declare oldChildIds LONGTEXT default '';
		declare i int default 0;
		SET SESSION group_concat_max_len=102400;
    select group_concat(id) into childIds from data_list where pid = dataId;
		set @i=1;
		
		-- select "开始循环",childIds;
    WHILE childIds != '' DO
				 set oldChildIds = childIds;
		     set ids = CONCAT(ids,",",childIds);
         select group_concat(id) into childIds from data_list where FIND_IN_SET(pid,childIds);
			   -- select "循环开始时childIds数据:",oldChildIds,"循环后数据",childIds,"ids",ids;
	 			 set i = i+1;
   END WHILE;
	 select ids;
	 -- select "几重循环:",i;
END

调用存储过程:

call get_child_ids(44);

输出:

查询所有上级

CREATE DEFINER=\`root\`@`%` PROCEDURE \`get_parent_ids\`(dataId INT(11))
BEGIN
    #Routine body goes here...
    declare ids LONGTEXT default '';
    declare parentId INT(11) default '0';
		declare i int default 0;
    select pid into parentId from data_list where id = dataId;
		set @i=1;
		
		-- select "开始循环",childIds;
    WHILE parentId >0 DO
		     set ids = CONCAT(ids,",",parentId);
         select pid into parentId from data_list where id=parentId;
			   -- select "循环开始时childIds数据:",oldChildIds,"循环后数据",childIds,"ids",ids;
	 			 set i = i+1;
   END WHILE;
	 select ids;
	 -- select "几重循环:",i;
END

调用:

call get_parent_ids(95474);

输出:

数据结构优化

我们在每条记录上新增 parent_data和child_data 字段,用于记录上级id以及自己下级的所有id,在查询时
只需要将id全部取出来,in操作,一条记录即可查询出所有数据:

parent_data

记录上级的id,从父级到父级的父级,以此类推

child_data

记录子级的关系节点,由json格式存储