无限级
在程序设计中,有很多需求都是无限级的,例如:无限级菜单,邀请人,目录无限级,地区分类,等等
无限级的实现方案
最简单的实现方案则是增加一个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格式存储
