内存存储的树形数据结构如何实现分片（Shard）

分片模式选择 #

优先选基于子树的水平分片，仅固定层级的静态树可以考虑垂直分片：

• 垂直分片是把树的不同层级拆分到不同节点存储，仅适合层级固定、上层节点访问热度远高于下层的场景（比如固定5层的商品类目树）。缺陷非常明显：如果树支持任意层级动态生长，上层节点的子节点数量会持续膨胀，最终还是会突破单节点存储上限，扩展性极差。
• 水平分片是按子树维度把整棵树拆为多个独立子树，分别存储在不同节点，天然适配动态生长的场景，是绝大多数场景的首选。

分片层级选择 #

建议做两层拆分，固定公共前缀层，从指定层级开始分片：

1. 把根节点到第N层的所有节点设为公共元数据，要么全量同步到所有分片节点，要么单独用一个低容量高可用的小集群存储。这部分节点数量少、更新频率低，单节点完全可以承载，N的取值可以根据实际业务评估，只要保证公共层总大小不超过单节点存储容量的1/3即可，留出足够冗余应对未来增长。
2. 从第N层的子节点开始做路由分片，路由规则直接用「根节点到第N层节点的路径字符串哈希」取模计算分片ID，整棵子树都会落到同一个分片里。举个例子：如果N取2，路径为/电商/3C/手机/安卓的节点，就对前缀/电商/3C做哈希取模，整个/电商/3C下的所有子节点都存在同一个分片。

动态生长场景适配 #

针对树可以任意层级生长的特性，配套两个机制即可解决扩容问题：

• 分片分裂阈值：给每个分片设置存储水位阈值，比如单分片存储使用率达到80%时自动触发分裂：把当前分片内的子树再往下取一层路径做哈希，拆分到2~3个新分片，同时更新公共元数据层的路由映射即可，整个过程对上层访问透明。
• 虚拟分片预分配：提前预分配远大于当前物理节点数量的虚拟分片（比如当前只有10台物理节点，提前分配1024个虚拟分片），物理节点仅负责承载若干个虚拟分片，后续新增物理节点时只需要把高负载节点上的虚拟分片迁移到新节点即可，不需要调整哈希规则，避免大规模数据迁移。

落地注意事项 #

• 若业务存在跨子树的查询需求，单独配套一个异步同步的索引层，把需要检索的字段同步到索引层统一查询，不要直接跨分片遍历树，会产生严重的性能问题。
• 公共元数据层的更新要做分布式一致性保证，用Raft等共识协议同步多副本，避免路由规则不一致导致的访问错误。

内容的提问来源于stack exchange，提问作者Pragmatic