前端生成parent_id关联的树结构数据

树结构的数据在后端有很多种存储方法，最常见的就是parent_id这种上下级关联表。当然还有其它的例如左右值树表等存储结构。
本文暂时只讨论parent_id关联的这种树结构，这时候后端范围的数据为所有树节点的list数据。
准备-测试数据生成代码
为了方便测试，先写一段随机生成parent_id关联list数据的代码
代码
// genTestData.js
function getRandomByRange(start, end) {
let length = end - start
return start + (Math.random() * length) >>> 0
}
function getRandomCode() {
return Math.random().toString(36).slice(2)
}
function getRandomCodeByData(data) {
return data[getRandomByRange(0, data.length)].code
}
export default function() {
let data = []
// 随机生成 20-30 个一级节点
for (let i = 0, l = getRandomByRange(20, 30); i < l; i++) {
data.push({
facode: '0',
code: getRandomCode()
})
}
// 随机生成 100-120 个随机关联节点
for (let i = 0, l = getRandomByRange(100, 120); i < l; i++) {
data.push({
facode: getRandomCodeByData(data),
code: getRandomCode()
})
}
return data.sort(() => (Math.random() - 0.5))
}
可修改 getRandomByRange 的参数，生成不同数量的测试数据
测试
测试生成效果如下
// demo.js
import genTestData from './genTestData.js'
const oriData = genTestData()
console.table(oriData)
这时候有了测试数据，现在开始进入正题
常规生成方法
思路
从根节点开始，遍历数据源，每次找到当前节点的子节点，挂到当前节点的 children 上，然后递归调用
代码
// tree.js
export class TreeCreate {
constructor(treeNode, treeConfig) {
this.treeNode = treeNode
this.treeConfig = Object.assign({
fId: 'pid', // 关联的 parent_id 字段名
id: 'id', // 关联的 parent_id 的 id 字段名
rootId: '0', // 开始的 根节点关联的 parent_id 对应的 字段名
}, treeConfig)
this.treeData = [] // 树数据
}
// 树生成, 递归调用
createTree(data, parent = null) {
let config = this.treeConfig
let TreeNode = this.treeNode
let treeData, pid, i, l, val, children
treeData = []
for (i = 0, l = data.length; i < l; i++) {
val = data[i]
if (parent === null) {
pid = config.rootId
} else {
pid = parent[config.id]
}
if (val[config.fId] === pid) {
let t = {}
TreeNode.call(t, val)
children = this.createTree(data, Object.assign(t, val))
treeData.push(t)
treeData[treeData.length - 1].children = children
}
}
return treeData
}
// 生成树
create(data) {
this.treeData = this.createTree(data)
}
// 获取树状的树数据(深拷贝)
getTreeData() {
// 演示简易处理，无法处理循环引用对象，如果树节点需要保留父级引用，则需要改为可以处理循环引用的深拷贝方法
return JSON.parse(JSON.stringify(this.treeData))
}
}
使用方式
treeNode 传入树节点数据生成函数，不能使用箭头函数，this为当前节点，默认空对象。 接受参数item为原始数据对象，根据需要为this对象赋值字段。如果简单需要全字段的，可以通过Object.keys遍历参数的所有字段，然后全部赋值到this的对应字段上。
treeConfig 为配置参数
FId 关联的 parent_id 字段名
Id 关联的 parent_id 的 id 字段名
rootId 开始的 根节点关联的 parent_id 对应的 字段名
测试性能
import genTestData from './genTestData.js'
import { TreeCreate } from './tree.js'
// 测试数据
const oriData = genTestData()
console.log(`树节点数量 ${oriData.length}`)
// 树
let demoTree = new TreeCreate(function(item) {
for (let key of Object.keys(item)) {
this[key] = item[key]
}
}, { fId: 'facode', id: 'code', rootId: '0' })
console.time('生成树时间')
demoTree.create(oriData, true)
console.timeEnd('生成树时间')
让我们测试下性能
百级数据
千级数据
可以看到性能已经有了明显的下降
万级数据
耗时将近3s多，会明显造成页面卡顿
这时候我们来找下原因，为什么会让生成函数随着n的增加下降这么严重。
如果仔细想想刚才的算法，不难发现其实其时间复杂度基本为O(n?)，会随着n的增加快速增加。
如果数据量改为十万级，基本处于页面卡死的状态，当然正常情况下不会出现前端需要处理十万级的数据，肯定是后端偷懒了，不过正常万级的数据还是有可能需要处理的。
如何优化
仔细思考代码重复跑的地方，发现每次找某个节点的children的时候，会遍历全部的数据源去判断是否是当前节点的children。
这时候第一反应的优化点就是，当A节点已经是B节点的children的时候，就从数据源中删除A节点，下次去查找C节点的children的时候就不会遍历到A节点了。
这个可以自己尝试下，有效果，不明显，因为没有改变某个节点被多次遍历的本质，例如A节点是最后一个节点的children，那么前面的children生成，还是每次会遍历到A节点，A节点还是会被遍历到多次。
而且从数据源中移除某个节点，其实也是耗时操作。
综上所述，耗时是因为节点被无效的多次遍历造成的，那么能不能只遍历一次然后用空间换时间的常规操作来优化遍历呢。
这时候我们就会想到js的map对象，hash存储，通过key可以直接得到value。
如果用fId作为key，存储所有children信息作为value，那这样每次查找当前节点的children的时候就从遍历查找变成了从map中取值，因为hash存储的关系，基本是忽略不计的取值时间。
快速生成方法
思路
思路上面的优化里面已经说了，用js的map的key-value的特性，遍历一次查找好所有的父子关系，然后递归的地方只管生成就行了
代码
// tree.js
export class TreeCreateFast {
constructor(treeNode, treeConfig) {
this.treeNode = treeNode
this.treeConfig = Object.assign({
fId: 'pid', // 关联的 parent_id 字段名
id: 'id', // 关联的 parent_id 的 id 字段名
rootId: '0', // 开始的 根节点关联的 parent_id 对应的 字段名
}, treeConfig)
this.treeData = [] // 树状的树数据
}
// 按 fId 分组
groupBy(data) {
let config = this.treeConfig
let group = []
data.forEach(v => {
let key = v[config.fId]
if (!group.hasOwnProperty(key)) {
group[key] = [v]
} else {
group[key].push(v)
}
})
return group
}
// 树生成, 递归调用
createTree(data, parent = null) {
let config = this.treeConfig
let TreeNode = this.treeNode
let treeData, pid, children
treeData = []
if (parent === null) {
pid = config.rootId
} else {
pid = parent[config.id]
}
if (data.hasOwnProperty(pid)) {
data[pid].forEach(val => {
let t = {}
TreeNode.call(t, val)
children = this.createTree(data, Object.assign(t, val))
treeData.push(t)
treeData[treeData.length - 1].children = children
})
}
return treeData
}
// 生成树
create(data) {
this.treeData = this.createTree(this.groupBy(data))
}
// 获取树状的树数据(深拷贝)
getTreeData() {
// 演示简易处理，无法处理循环引用对象，如果树节点需要保留父级引用，则需要改为可以处理循环引用的深拷贝方法
return JSON.parse(JSON.stringify(this.treeData))
}
}
使用方式
使用方式跟常规的树生成函数一致
测试性能
import genTestData from './genTestData.js'
import { TreeCreateFast } from './tree.js'
// 测试数据
const oriData = genTestData()
console.log(`树节点数量 ${oriData.length}`)
// 树
let demoTree = new TreeCreateFast(function(item) {
for (let key of Object.keys(item)) {
this[key] = item[key]
}
}, { fId: 'facode', id: 'code', rootId: '0' })
console.time('生成树时间')
demoTree.create(oriData, true)
console.timeEnd('生成树时间')
测试下性能，直接从万级开始
万级数据
在常规项目能接触的数据量上，已经处于无感了，基本就会卡个一帧
十万级数据
处于可以接受的范围，毕竟不可能有十万级的数据需要处理的
挑战下百万级
就玩玩试试，没任何实际意义
总结
通过map优化了遍历之后，解决多次重复的无用遍历之后，性能提升非常明显，基本常规项目使用场景下不会造成任何浏览器卡顿。
当然如果再使用 Web Worker 优化的话可以让用户在获得流畅的访问体验上，快速看到所需的数据。