关于树形结构持久化的思考

0x01 背景

最近的一个项目中，因为一个数据库表结构的设计，引发了长达半年的激烈讨论。

需求很简单：

1.png

需要设计一个支持无限层级的，有顺序的存储方式。支持对树结构中节点的曾、删、改以及整棵树的复制。

观点主要有两个，一方是认为，设计一个id/pid的经典结构（但是这里为了保存同一层级不同子节点的顺序，子节点还需要同时保存自己的order信息），另一方认为，每个节点保存一个数组，数组内容为子节点的有序id。

针对这两个设计，在可以实现所有需求的前提下，从不同角度对比下到底有什么优劣：

0x02 增加节点

0x03 删除节点

0x04 恢复树结构

0x05 复制树结构

经典结构、数组结构中，均可以通过增加一个冗余字段，使用SELECT INTO达到高效的复制。

0x06 对比

1. 增加、删除节点，看起来消耗一样，但是数组结构两个操作逻辑相同，经典结构需要两套逻辑，数据结构能够节省一半代码量；
2. 恢复树结构，数组结构相对经典结构，节省一次递归调用，能少约三分之一的代码。

所以，总体来说，我觉得数组结构是一个更优的选择。