Teable 字段依赖拓扑排序与 Link 跨表级联计算从数据结构到源码实现解析【免费下载链接】teable✨ AI Spreadsheet for Business项目地址: https://gitcode.com/GitHub_Trending/te/teable导读在 Teable 这样的多维表格引擎中字段之间并非彼此孤立普通字段可以被公式字段、统计Rollup字段引用而 Link 字段则进一步把「一个记录的变化」扩散到「多个表、多个记录」。本文以仓库内 calculation/README.md 的设计文档为主线系统讲解其背后的核心数据结构——字段级有向无环图DAG与拓扑排序以及Link 字段导致的 record 裂变与跨表级联计算的整体思路。读完本文你将掌握如何用id dependencies表达字段依赖、如何从任意变更入口推导受影响记录集合、一对多/多对一关系下反向引用链的更新策略以及这些设计在 dfs.ts 与 link.service.ts 中的落地方式。一、问题域记录变化如何驱动依赖计算1.1 字段级依赖的数据结构设计文档给出的最基础抽象是「字段依赖拓扑项」id为 fieldIddependencies是当前字段所依赖的字段 id 列表。IFieldMap则是全部字段信息的 map其中字段类型在简化模型里分为other与link两类interface ITopologicalItem { id: string; dependencies: string[]; } interface IField { type: other | link; } type IFieldMap { [id: string]: IField };这套结构与仓库实现中的ITopoItem完全对应见 dfs.ts// topo item is for field level reference, all id stands for fieldId; export interface ITopoItem { id: string; dependencies: string[]; } export interface IGraphItem { fromFieldId: string; toFieldId: string; }其中IGraphItem用fromFieldId - toFieldId的有向边表达「to依赖from」的引用关系。字段引用关系在数据库中通过reference表持久化由ReferenceService.getFieldGraphItems()通过递归 CTE一次性取出与起始字段连通的所有引用边见 reference.service.ts。1.2 计算触发模型当一个 record 中的某个 field 变化后系统以 recordId 为入口按照拓扑排序得到的顺序依次计算每个 field 的值。这保证了任何字段在计算时它所依赖的字段一定已经处于最新状态。// 简单场景b1[fieldB] 变化 [ { id: fieldB, dependencies: [], recordId: [b1] }, { id: fieldLinkB, dependencies: [fieldB], recordId: [b1], targetRecordId: [a1, a2] }, // formula({fieldB}) ];这里出现了文档中反复强调的两个关键概念recordId参与计算的记录当前字段被算出来的记录targetRecordIdLink 字段「裂变」出来的关联表记录——Link 字段计算时需要携带关联表中的 recordId 与对应的 recordData 参与运算计算后的结果写入当前表对应 targetRecordId 的 link 字段下。recordId与targetRecordId的区分在源码的IRecordItem、IRecordMap等类型中也有体现见 reference.service.ts而多表记录按{ tableId - { recordId - { fieldId - value } } }聚合的结构则由IRecordMapByTableId表达见 link.service.ts。二、拓扑排序只保留从变更入口可达的子图2.1 多级传播示例设计文档用一条完整链路说明了「一次变化如何穿透多张表」[ { id: fieldB, dependencies: [], recordId: [b1] }, { id: fieldLinkB, dependencies: [fieldB], recordId: [b1], targetRecordId: [a1, a2] }, { id: fieldA, dependencies: [fieldLinkB], recordId: [a1, a2] }, { id: fieldLinkA, dependencies: [fieldA], recordId: [a1, a2], targetRecordId: [b1] }, ];链路语义为b1.fieldB变化 → 跨表裂变到a1、a2的fieldLinkB→ 驱动a1、a2的fieldA→ 再裂变回b1的fieldLinkA。可以看出拓扑序列本身只包含从变更入口出发可达的有向图无关字段如示例中被注释掉的fieldC、fieldLinkC不会进入序列。2.2 源码中的拓扑排序实现dfs.ts 的getTopoOrders()采用基于逆邻接表的 DFS对每个节点先递归处理其所有依赖入边再将该节点以{ id, dependencies }的形式推入结果数组从而保证「依赖先于被依赖者」出现// 关键逻辑简化 const dependencies reverseAdjList[node] || []; for (const dep of dependencies) { if (!visitedNodes.has(dep)) visit(dep); } sortedNodes.push({ id: node, dependencies });配套函数还包括hasCycle()检测引用环dfs.ts。真实的表单系统中字段循环引用是非法的getTopoOrders在遇到环时也会抛出带httpErrors.field.cycleDetected本地化文案的异常prependStartFieldIds()把变更入口字段补充到拓扑序列最前dfs.ts确保起点字段即使没有任何依赖也参与计算filterDirectedGraph()/pruneGraph()从全量引用图中裁剪出与入口字段连通的部分。这些函数的行为均有对应的单元测试佐证例如 dfs.spec.ts 覆盖了单链 DAG、多入口 DAG、环检测与图裁剪等场景可据此验证「拓扑排序只包含从变更入口开始的有向图」这一设计结论。2.3 运行时上下文ITopoOrdersContext在实际计算中拓扑序只是「骨架」还需要大量辅助元数据。FieldCalculationService.getTopoOrdersContext()见 field-calculation.service.ts组装出完整的计算上下文export interface ITopoOrdersContext { fieldMap: IFieldMap; // fieldId - 字段实例 allFieldIds: string[]; startFieldIds: string[]; directedGraph: IGraphItem[]; // 过滤后的引用有向图 fieldId2DbTableName: { [fieldId: string]: string }; topoOrders: ITopoItem[]; // 拓扑排序结果 tableId2DbTableName: { [tableId: string]: string }; dbTableName2fields: { [dbTableName: string]: IFieldInstance[] }; fieldId2TableId: { [fieldId: string]: string }; fkRecordMap?: IFkRecordMap; }其内部流程为读取引用图 → 通过flatGraph展平出全部关联字段 →createAuxiliaryData批量加载字段元数据、表名映射见 reference.service.ts→ 过滤掉指向已删除字段的边 →getTopoOrdersprependStartFieldIds生成最终拓扑序。三、单次查询从变更记录推导出全部受影响记录3.1 跨表拓扑顺序描述结构为了用「一次查询」回答「从 recordB1 出发最终会发生变化的 record 及它们与各 field 的关系」文档定义了一组带表信息的拓扑序列。tableName表示表名fieldName表示字段名targetLinkField表示存储关联记录的外键字段名linkedTable表示外键字段关联的表名dependencies表示关联后需要查询记录中的哪些字段值const topologicalOrder [ { tableName: A, fieldName: fieldA, dependencies: [] }, { tableName: B, fieldName: fieldLinkA, targetLinkField: __fk_fieldLinkA, linkedTable: A, dependencies: [fieldA], }, { tableName: C, fieldName: fieldLinkB, targetLinkField: __fk_fieldLinkB, linkedTable: B, dependencies: [fieldLinkA], }, ];3.2 示例数据推演对应 A / B / C 三张表JSON 表达如下// A 表 [ { id: idA1, fieldA: A1 }, { id: idA2, fieldA: A2 }, ]; // B 表 [ { id: idB1, fieldB: B1, fieldLinkA: A1, __fk_fieldLinkA: idA1 }, { id: idB2, fieldB: B2, fieldLinkA: A1, __fk_fieldLinkA: idA1 }, ]; // C 表 [ { id: idC1, fieldC: C1, fieldLinkB: A1, __fk_fieldLinkB: idB1 }, { id: idC2, fieldC: C2, fieldLinkB: A1, __fk_fieldLinkB: idB1 }, { id: idC3, fieldC: C3, fieldLinkB: A1, __fk_fieldLinkB: idB2 }, ];当idA1.fieldA变化时按照外键关系可推导从 A 表出发__fk_fieldLinkA idA1命中 B 表的idB1、idB2再从 B 表出发__fk_fieldLinkB分别命中idC1、idC2属于idB1与idC3属于idB2。最终受影响记录集合为[idB1, idB2]与[idC1, idC2, idC3]。文档的核心诉求正是把idA1和topologicalOrder作为参数传入用 SQL 一次性查出这些 recordId避免逐表逐条递归查询。3.3 源码中的等价实现思路虽然文档提出的是一段理想化的「动态 SQL」仓库实际实现采用的是批量构建查询 内存计算的组合策略这与文档目标殊途同归查询侧LinkService.getForeignKeys()/getJoinedForeignKeys()见 link.service.ts通过 Knex 在 link 外键宿主表上以whereIn一次取出成批的{ id, foreignId }外键对其中getJoinedForeignKeys使用子查询完成「由关联记录反查宿主记录」内存侧fetchRecordMap()link.service.ts按tableId - recordId - fieldId结构聚合记录并支持projectionByTable投影裁剪只拉取计算真正需要的字段列批量取数FieldCalculationService.getRecordsBatchByFields()field-calculation.service.ts按calcChunkSize阈值分页并发拉取各表记录最终合并去重。也就是说「一次性找出全部受影响 record」在实际工程中拆解为CTE 一次性取引用图 → 批量外键查询取跨表关系 → 按表批量拉记录三个层次。四、一对多关系下的反向引用计算链4.1 数据模型文档接着给出了一对多OneMany与多对一ManyOne共存的三表示例// A 表 { __id: idA1, fieldA: A1, oneToManyB: [C1,C2, C3] } // B 表 { __id: idB1, fieldB: C1,C2, manyToOneA: A1, __fk_manyToOneA: idA1, oneToManyC: [C1, C2] } { __id: idB2, fieldB: C3, manyToOneA: A1, __fk_manyToOneA: idA1, oneToManyC: [C3] } // C 表 { __id: idC1, fieldC: C1, manyToOneB: C1,C2, __fk_manyToOneB: idB1 } { __id: idC2, fieldC: C2, manyToOneB: C1,C2, __fk_manyToOneB: idB1 } { __id: idC3, fieldC: C3, manyToOneB: C3, __fk_manyToOneB: idB2 }其拓扑序描述结构注意出现了Relationship.OneMany/Relationship.ManyOne枚举与foreignKeyField外键列const topoOrder [ { dbTableName: B, fieldName: oneToManyC, foreignKeyField: __fk_manyToOneB, relationship: Relationship.OneMany, linkedTable: C, }, { dbTableName: A, fieldName: oneToManyB, foreignKeyField: __fk_manyToOneA, relationship: Relationship.OneMany, linkedTable: B, }, { dbTableName: C, fieldName: manyToOneB, foreignKeyField: __fk_manyToOneB, relationship: Relationship.ManyOne, linkedTable: B, }, ];4.2 语义解读A.idA1.oneToManyB [C1,C2, C3]取自 B 表idB1、idB2的fieldB值聚合为数组B.idB1.oneToManyC [C1, C2]取自 C 表idC1、idC2的fieldC聚合为数组B.idB2.oneToManyC [C3]同理C.idC1.manyToOneB C1,C2/C.idC2.manyToOneB C1,C2均引用 B 表idB1的fieldB。这正是「多值 lookup」的典型场景oneToManyC持有目标记录 id 列表[C1,C2]计算时按这些 id 到 C 表查fieldC再合并成数组。仓库中 Link 字段的 cell value 正是以{ id, title }数组形式存储的见ILinkCellValue的使用与fixLinkCellTitle()对 title 的补全逻辑link.service.ts。Relationship枚举的对称关系定义在 packages/core/src/models/field/constant.tsconst inverseRelationshipMap { [Relationship.OneMany]: Relationship.ManyOne, [Relationship.ManyOne]: Relationship.OneMany, [Relationship.ManyMany]: Relationship.ManyMany, [Relationship.OneOne]: Relationship.OneOne, };即 Link 字段成对出现一端的 OneMany 必对应另一端的 ManyOne多对多对称一对一对称。这解释了为什么文档中topoOrder里同时出现 OneMany 与 ManyOne 两种条目——它们是同一关联关系在两个方向上的视图。4.3 问题 1变更发生后如何更新两端文档提出C.idC1.fieldC从C1变为C11如何更新 A 表和 B 表的对应值先明确最终输出结构由「参与计算时如何进行多值 lookup 合并」决定例如B.oneToManyC [C1,C2]需要到 C 表取idC1、idC2的fieldC再合并成数组因此必须先确定哪些记录、哪些字段会作为 lookup 的来源。仓库中对应的是LinkService.getDerivateByLink()及其变体见 link.service.ts整体策略在源码注释中写得很清楚定义「主表」为外键所在表「外表」为外键指向表生成外键变化fk 变更缓存受影响记录 id主表、外表都要缓存按外键变化更新数据库提交原始 op依据缓存的记录 id 生成更新主表的 op再生成更新外表的 op。实现上getFkRecordMap()负责把 cell 上下文oldValue/newValue与数据库中现存外键对比产出IFkRecordMapoldKey/newKey其中null表示无外键或需删除外键随后按关系类型分派到四种更新逻辑updateForeignCellForManyMany/saveForeignKeyForManyMany差集增删 顺序列维护link.service.tsupdateForeignCellForManyOne/saveForeignKeyForManyOne单值外键更新并支持 PostgreSQL 行锁防并发lockForeignRecordslink.service.tsupdateForeignCellForOneMany/saveForeignKeyForOneMany数组重排或差集更新updateForeignCellForOneOne/saveForeignKeyForOneOne互斥单值绑定。getDerivateByCellContexts()则串起完整流水线构造记录结构 → 计算投影 → 读取原值 → 持久化外键 → 重读新值 → diff 出 cellChangeslink.service.ts最终diffLinkCellChange通过isEqual比较新旧值产出变更列表。4.4 问题 2值全为空时如何回填文档第二个问题假设A.oneToManyB与B.oneToManyC当前都为空如何利用topoOrder中的关系通过 SQL 查询 TS 计算得到它们的值这正是「由外键关系重建 lookup 值」的过程。仓库中的答案可以概括为三步SQL 层通过getForeignKeys()/getAllForeignKeys()从外键宿主表读出{ id, foreignId }全量映射必要时用getJoinedForeignKeys()反查内存层fetchRecordMap()按投影拉取目标表记录recordRaw2Record()reference.service.ts把数据库行的__id、__auto_number、__created_time等系统列与业务字段转换为IRecord合并层按照topoOrder给定的方向把目标记录的字段值聚合进持有外键列表的一端——即多值 lookup 合并。合并时changes.ts中的mergeDuplicateChange()changes.ts还会按tableId#fieldId#recordId去重避免同一格在 A→C→E、B→D→E 这类「汇合路径」中被重复计算。mergeDuplicateChange注释中给出的例子与文档的诉求完全吻合多个变更路径汇聚到同一目标字段时该字段会被多次算出必须合并以削减更新次数。五、变更结果如何落到应用层CellChange 与 OT 操作依赖计算的最终产物是一批「单元格变更」。仓库统一用ICellChange表达export interface ICellChange { tableId: string; recordId: string; fieldId: string; oldValue: unknown; newValue: unknown; }见 changes.ts。changeToOp()把单个变更转换为 OT 操作RecordOpBuilder.editor.setRecordformatChangesToOps()按tableId - recordId - IOtOperation[]重新组织方便按记录批量提交消费方如 record-update.service.ts 会先调用linkService.planDerivateByLink()规划 Link 派生变更不立即落库便于在事务内捕获旧值随后与普通字段的计算结果合并后统一提交。planDerivateByLink/commitForeignKeyChanges的「计划-提交」分离设计见 link.service.ts正是为了在复杂更新事务中保证外键写入与派生计算的一致性。这一环节回答了文档开头的问题「我们提供一个 recordId然后按照拓扑排序中的顺序依次计算每个 field 的值」——计算完成后每个被影响单元格的 old/new 值都会被汇总成ICellChange交给上层落库与广播。六、小结一张图看透整个链路把设计文档与源码实现合在一起可以总结出 Teable 字段级联计算的完整链路建图从变更字段出发用reference表的递归 CTE 取出连通引用边getFieldGraphItems裁剪filterDirectedGraph/pruneGraph只保留从入口可达的字段保证拓扑序最小化排序getTopoOrders基于逆邻接表 DFS 产出「依赖先算」的字段序列并检测循环引用装载getTopoOrdersContext/createAuxiliaryData批量加载字段元数据、表名映射、外键宿主信息裂变Link 字段把「一个记录的变化」扩散为targetRecordId集合IFkRecordMap跟踪 old/new 外键计算按表批量拉取记录分页 投影裁剪依据拓扑序逐字段计算多值 lookup 合并产出diffLinkCellChangemergeDuplicateChange汇总为去重后的ICellChange再转为 OT 操作提交。其中涉及的IGraphItem/ITopoItem类型与拓扑算法位于 dfs.ts引用图查询与元数据装配位于 reference.service.tsLink 外键的四种关系维护位于 link.service.ts批量取数与计算上下文组装位于 field-calculation.service.ts相关的单元测试dfs.spec.ts、link.service.spec.ts、field-calculation.service.spec.ts可作为深入研读的入口。说明本文基于 calculation/README.md 的技术设计展开文档中以伪代码形式提出的「单条动态 SQL 一次查出所有 recordId」属于理想化目标仓库实际采用「CTE 引用图 批量外键查询 分页批量取数」的组合方案达到同等效果两者可以互为印证。【免费下载链接】teable✨ AI Spreadsheet for Business项目地址: https://gitcode.com/GitHub_Trending/te/teable创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考