高效的数据库树遍历与Rails

在Rails API中，我们解决了树遍历的性能问题，特别是在计算数据库模式合并基准时。

每个数据库模式的变化被称为“模式快照”，类似于git提交，存储特定时间的模式状态。

在合并分支时，我们需要在每个变化的历史中进行广度优先搜索，以找到两个分支之间的共同祖先。

传统的逐个检查快照的方法在处理大量快照时会导致性能问题，尤其是网络请求的延迟。

为了解决N+1性能问题，我们创建了一个内存缓存来存储快照，从而减少数据库查询次数。

内存缓存使用简单的哈希结构，能够快速存取快照数据，并记录命中和未命中的统计信息。

通过预加载最近的快照，我们显著减少了对数据库的访问次数，提高了性能。

在推出新代码之前，我们进行了准确性测试，确保新方法返回正确结果，并使用特性标志逐步推出。

除了内存缓存，还有其他解决方案，如使用递归公共表表达式和物化路径技术，但在我们的情况下，内存缓存是最有效的选择。