关于树形结构持久化的思考
原创
0x01 背景
最近的一个项目中，因为一个数据库表结构的设计，引发了长达半年的激烈讨论。
需求很简单：
需要设计一个支持无限层级的，有顺序的存储方式。支持对树结构中节点的曾、删、改以及整棵树的复制。
观点主要有两个，一方是认为，设计一个id/pid的经典结构（但是这里为了保存同一层级不同子节点的顺序，子节点还需要同时保存自己的order信息），另一方认为，每个节点保存一个数组，数组内容为子节点的有序id。
针对这两个设计，在可以实现所有需求的前提下，从不同角度对比下到底有什么优劣：
0x02 增加节点
步骤 | 经典结构 | 数组结构 |
|---|---|---|
1 | 插入新节点 | 插入新节点 |
2 | 对排在新节点后的节点的order加1 | 更新父节点数组 |
0x03 删除节点
步骤 | 经典结构 | 数组结构 |
|---|---|---|
1 | 删除节点包括子节点 | 删除节点包括子节点 |
2 | 对排在新节点后的节点的order-1 | 更新父节点数组 |
0x04 恢复树结构
步骤 | 经典结构 | 数组结构 |
|---|---|---|
1 | 遍历所有节点，构造节点字典 | 遍历所有节点，构造节点字典 |
2 | 遍历所有节点，将自己插入到父节点children字段中 | 遍历所有节点，获取所有的子节点，插入自己的children字段中 |
3 | 深度\广度遍历树，对每个节点children字段中的节点排序 | 无 |
0x05 复制树结构
经典结构、数组结构中，均可以通过增加一个冗余字段，使用SELECT INTO达到高效的复制。
0x06 对比
- 增加、删除节点，看起来消耗一样，但是数组结构两个操作逻辑相同，经典结构需要两套逻辑，数据结构能够节省一半代码量；
- 恢复树结构，数组结构相对经典结构，节省一次递归调用，能少约三分之一的代码。
所以，总体来说，我觉得数组结构是一个更优的选择。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。