本文源于 Vue DevUI 开源组件库实际。
1 Tree 组件搜寻过滤性能简介
树节点的搜寻性能次要是为了不便用户可能疾速查找到本人须要的节点。过滤性能不仅要满足搜寻的个性，同时还须要暗藏掉与匹配节点同层级的其它未能匹配的节点。
搜寻性能次要包含以下性能：
- 与搜寻过滤字段匹配的节点须要进行标识，和一般节点进行辨别
- 子节点匹配时，其所有父节点须要开展，不便用户查看层级关系
- 对于大数据量，采纳虚构滚动时，搜寻过滤实现后滚动条需滚动至第一个匹配节点的地位
搜寻会将匹配到的节点高亮：
过滤除了将匹配到的节点高亮之外，还会将不匹配的节点筛除掉：
2 组件交互逻辑剖析
2.1 对于匹配节点的标识如何出现？
通过将节点与搜寻字段相匹配的 label 局部文字进行高亮加粗的形式进行标记。易于用户一眼就可能找到搜寻到的节点。
2.2 用户如何调用 tree 组件的搜寻过滤性能？
通过增加searchTree办法，用户通过ref的形式进行调用。并通过option参数配置辨别搜寻、过滤。
2.3 对于匹配的节点其父节点及兄弟节点如何获取及解决？
对于节点的获取及解决是搜寻过滤性能的外围。尤其在大数据量的状况下，带来的性能耗费如何优化，将在实现原理中详情论述。
3 实现原理和步骤
3.1 第一步：须要相熟 tree 组件整个代码及逻辑组织形式
tree组件的文件构造：
tree├── index.ts├── src| ├── components| | ├── tree-node.tsx| | ├── ...| ├── composables| | ├── use-check.ts| | ├── use-core.ts| | ├── use-disable.ts| | ├── use-merge-nodes.ts| | ├── use-operate.ts| | ├── use-select.ts| | ├── use-toggle.ts| | ├── ...| ├── tree.scss| ├── tree.tsx└── __tests__ └── tree.spec.ts能够看出，vue3.0中 composition-api 带来的便当。逻辑层之间的拆散，不便代码组织及后续问题的定位。可能让开发者只分心于本人的个性，十分有利于前期保护。
增加文件use-search-filter.ts, 文件中定义searchTree办法。
import { Ref, ref } from 'vue';import { trim } from 'lodash';import { IInnerTreeNode, IUseCore, IUseSearchFilter, SearchFilterOption } from './use-tree-types';export default function () { return function useSearchFilter(data: Ref<IInnerTreeNode[]>, core: IUseCore): IUseSearchFilter { const searchTree = (target: string, option: SearchFilterOption): void => { // 搜寻主逻辑 }; return { virtualListRef, searchTree, }; }}SearchFilterOption的接口定义，matchKey 与 pattern的配置削减了搜寻的匹配形式多样性。
export interface SearchFilterOption { isFilter: boolean; // 是否是过滤节点 matchKey?: string; // node节点中匹配搜寻过滤的字段名 pattern?: RegExp; // 搜寻过滤时匹配的正则表达式}在tree.tsx主文件中增加文件use-search-fliter.ts的援用, 并将searchTree办法裸露给第三方调用者。
import useSearchFilter from './composables/use-search-filter'; setup(props: TreeProps, context: SetupContext) { const userPlugins = [useSelect(), useOperate(), useMergeNodes(), useSearchFilter()]; const treeFactory = useTree(data.value, userPlugins, context); expose({ treeFactory, }); }3.2 第二步：须要相熟 tree 组件整个nodes数据结构是怎么的。nodes数据结构间接决定如何拜访及解决匹配节点的父节点及兄弟节点
在use-core.ts文件中能够看出， 整个数据结构采纳的是扁平构造，并不是传统的树结构，所有的节点蕴含在一个一维的数组中。
const treeData = ref<IInnerTreeNode[]>(generateInnerTree(tree));// 外部数据结构应用扁平构造export interface IInnerTreeNode extends ITreeNode { level: number; idType?: 'random'; parentId?: string; isLeaf?: boolean; parentChildNodeCount?: number; currentIndex?: number; loading?: boolean; // 节点是否显示加载中 childNodeCount?: number; // 该节点的子节点的数量 // 搜寻过滤 isMatched?: boolean; // 搜寻过滤时是否匹配该节点 childrenMatched?: boolean; // 搜寻过滤时是否有子节点存在匹配 isHide?: boolean; // 过滤后是否不显示该节点 matchedText?: string; // 节点匹配的文字（须要高亮显示）}3.3 第三步： 解决匹配节点及其父节点的开展属性
节点中增加以下属性，用于标识匹配关系
isMatched?: boolean; // 搜寻过滤时是否匹配该节点 childrenMatched?: boolean; // 搜寻过滤时是否有子节点存在匹配 matchedText?: string; // 节点匹配的文字（须要高亮显示）通过 dealMatchedData 办法来解决所有节点对于搜寻属性的设置。
它次要做了以下事件：
- 将用户传入的搜寻字段进行大小写转换
- 循环所有节点，先解决本身节点是否与搜寻字段匹配，匹配就设置
selfMatched = true。首先判断用户是否通过自定义字段进行搜寻 (matchKey参数)，如果有，设置匹配属性为node中自定义属性，否则为默认label属性；而后判断是否进行正则匹配 (pattern参数)，如果有，就进行正则匹配，否则为默认的疏忽大小写的含糊匹配。 - 如果本身节点匹配时, 设置节点
matchedText属性值，用于高亮标识。 - 判断本身节点有无
parentId，无此属性值时，为根节点，毋庸解决父节点。有此属性时，须要进行内层循环解决父节点的搜寻属性。利用set保留节点的parentId, 顺次向前查找，找到parent节点，判读是否该parent节点被解决过，如果没有，设置父节点的childrenMatched和expanded属性为true，再将parent节点的parentId属性退出set中，while循环反复这个操作，直到遇到第一个曾经解决过的父节点或者直到根节点进行循环。 - 整个双层循环将所有节点处理完毕。
dealMatchedData外围代码如下：
const dealMatchedData = (target: string, matchKey: string | undefined, pattern: RegExp | undefined) => { const trimmedTarget = trim(target).toLocaleLowerCase(); for (let i = 0; i < data.value.length; i++) { const key = matchKey ? data.value[i][matchKey] : data.value[i].label; const selfMatched = pattern ? pattern.test(key) : key.toLocaleLowerCase().includes(trimmedTarget); data.value[i].isMatched = selfMatched; // 须要向前找父节点，解决父节点的childrenMatched、expand参数(子节点匹配到时，父节点须要开展) if (selfMatched) { data.value[i].matchedText = matchKey ? data.value[i].label : trimmedTarget; if (!data.value[i].parentId) { // 没有parentId示意时根节点，不须要再向前遍历 continue; } let L = i - 1; const set = new Set(); set.add(data.value[i].parentId); // 没有parentId时，示意此节点的纵向parent已拜访结束 // 没有父节点被解决过，示意时第一次向上解决以后纵向父节点 while (L >= 0 && data.value[L].parentId && !hasDealParentNode(L, i, set)) { if (set.has(data.value[L].id)) { data.value[L].childrenMatched = true; data.value[L].expanded = true; set.add(data.value[L].parentId); } L--; } // 循环完结时须要额定解决根节点一层 if (L >= 0 && !data.value[L].parentId && set.has(data.value[L].id)) { data.value[L].childrenMatched = true; data.value[L].expanded = true; } } }};const hasDealParentNode = (pre: number, cur: number, parentIdSet: Set<unknown>) => { // 当拜访到同一层级前曾经有匹配时前一个曾经解决过父节点了，不须要持续拜访 // 当拜访到第一父节点的childrenMatched为true的时，不再须要向上寻找，避免反复拜访 return ( (data.value[pre].parentId === data.value[cur].parentId && data.value[pre].isMatched) || (parentIdSet.has(data.value[pre].id) && data.value[pre].childrenMatched) );};3.4 第四步： 如果是过滤性能时，须要将未匹配到的节点进行暗藏
节点中增加以下属性，用于标识节点是否暗藏。
isHide?: boolean; // 过滤后是否不显示该节点同3.3中外围解决逻辑大同小异，通过双层循环， 节点的 isMatched 和 childrenMatched 以及父节点的 isMatched 设置本身节点是否显示。
外围代码如下：
const dealNodeHideProperty = () => { data.value.forEach((item, index) => { if (item.isMatched || item.childrenMatched) { item.isHide = false; } else { // 须要判断是否有父节点有匹配 if (!item.parentId) { item.isHide = true; return; } let L = index - 1; const set = new Set(); set.add(data.value[index].parentId); while (L >= 0 && data.value[L].parentId && !hasParentNodeMatched(L, index, set)) { if (set.has(data.value[L].id)) { set.add(data.value[L].parentId); } L--; } if (!data.value[L].parentId && !data.value[L].isMatched) { // 没有parentId, 阐明曾经拜访到以后节点所在的根节点 item.isHide = true; } else { item.isHide = false; } } });};const hasParentNodeMatched = (pre: number, cur: number, parentIdSet: Set<unknown>) => { return parentIdSet.has(data.value[pre].id) && data.value[pre].isMatched;};3.5 第五步：解决匹配节点的高亮显示
如果该节点被匹配，将节点的label解决成[preMatchedText, matchedText, postMatchedText]格局的数组。 matchedText增加 span标签包裹，通过CSS款式显示高亮成果。
const matchedContents = computed(() => { const matchItem = data.value?.matchedText || ''; const label = data.value?.label || ''; const reg = (str: string) => str.replace(/[-[\]{}()*+?.,\\^$|#\s]/g, '\\$&'); const regExp = new RegExp('(' + reg(matchItem) + ')', 'gi'); return label.split(regExp);});<span class={nodeTitleClass.value}> { !data.value?.matchedText && data.value?.label } { data.value?.matchedText && matchedContents.value.map((item: string, index: number) => ( index % 2 === 0 ? item : <span class={highlightCls}>{item}</span> )) }</span>3.6 第六步：tree组件采纳虚构列表时，需将滚动条滚动至第一个匹配的节点，不便用户查看
先失去目前整个树显示进去的节点，找到第一个匹配的节点下标。调用虚构列表组件的 scrollTo 办法滚动至该匹配节点。
const getFirstMatchIndex = (): number => { let index = 0; const showTreeData = getExpendedTree().value; while (index <= showTreeData.length - 1 && !showTreeData[index].isMatched) { index++; } return index >= showTreeData.length ? 0 : index;};const scrollIndex = getFirstMatchIndex();virtualListRef.value.scrollTo(scrollIndex);通过 scrollTo 办法定位至第一个匹配项效果图：
原始树结构显示图：
过滤性能：
4 遇到的难点问题
4.1 搜寻的外围在于对匹配节点的所有父节点的拜访以及解决
整棵树数据结构就是一个一维数组，向上须要将匹配节点所有的父节点全副开展， 向下须要晓得有没有子节点存在匹配。传统tree组件的数据结构是树形构造，通过递归的形式实现节点的拜访及解决。对于扁平的数据结构应该如何解决？
- 计划一：扁平数据结构 --> 树形构造 --> 递归解决 --> 扁平数据结构 （NO）
- 计划二： node增加parent属性，保留该节点父级节点内容 --> 遍历节点解决本身节点及parent节点 （No）
- 计划三： 同过双层循环，第一层循环解决以后节点，第二层循环解决父节点 （Yes）
计划一：通过数据结构的转换解决，不仅丢掉了扁平数据结构的劣势，还减少了数据格式转换的老本，并带来了更多的性能耗费。
计划二：parent属性增加其实就是一种树形构造的模拟，减少内存耗费，保留很多无用反复数据。循环拜访节点时也存在节点的反复拜访。节点越靠后，反复拜访越重大，无用的性能耗费。
计划三： 利用扁平数据结构的劣势，节点是有程序的。即：树节点的显示程序就是节点在数组中的程序，父节点肯定是在子节点之前。父节点拜访解决只须要遍历该节点之前的节点，通过 childrenMatched属性标识该父节点有子节点存在匹配。 不必增加parent字段存取所有的父节点信息，不必通过数据转换，再递归寻找解决节点。
4.2 解决父级节点时进行优化，避免内层遍历反复解决曾经拜访过的父级节点，带来性能晋升
外层循环，如果该节点没有匹配搜寻字段，将不进行内层循环，间接跳过。 详见3.3中的代码
通过对内层循环终止条件的优化，避免反复拜访同一个父节点
let L = index - 1;const set = new Set();set.add(data.value[index].parentId);while (L >= 0 && data.value[L].parentId && !hasParentNodeMatched(L, index, set)) { if (set.has(data.value[L].id)) { set.add(data.value[L].parentId); } L--;}const hasDealParentNode = (pre: number, cur: number, parentIdSet: Set<unknown>) => { // 当拜访到同一层级前曾经有匹配时前一个曾经解决过父节点了，不须要持续拜访 // 当拜访到第一父节点的childrenMatched为true的时，不再须要向上寻找，避免反复拜访 return ( (data.value[pre].parentId === data.value[cur].parentId && data.value[pre].isMatched) || (parentIdSet.has(data.value[pre].id) && data.value[pre].childrenMatched) );};4.3 对于过滤性能，还需解决节点的显示暗藏
同样通过双层循环、以及解决匹配数据时减少的isMatched 、 childrenMatched属性来独特决定节点的isHide属性，详见3.4中的代码、
通过对内层循环终止条件的优化，与设置 childrenMatched时的判断有所区别。
const hasParentNodeMatched = (pre: number, cur: number, parentIdSet: Set<unknown>) => { return parentIdSet.has(data.value[pre].id) && data.value[pre].isMatched;};5 小结
尽管是一个组件下一个小个性的开发，然而从个性的交互剖析开始，一步步到最终的性能实现，整个过程还是播种满满。平时开发中很少可能从方案设计到性能实现有一个整体的布局，往往都是先上手代码，在开发过程中才发现计划选取不合理，就会走很多弯路。所以，刚开始的个性剖析和方案设计就显得尤为重要。
剖析 --> 设计 --> 计划探讨 --> 计划确定 --> 性能实现 --> 逻辑优化。每个过程都能锤炼晋升本人的能力。
文/DevUI社区 daviForevel