败者树(Loser Tree)

败者树(Loser Tree)是一种支持高效多路归并的树形选择结构,属于选择树的一种。它把多个有序序列的当前首元素作为叶子,内部节点存放两两比较中失败者的下标,顶端额外一个节点记录当前的全局最小胜者。

概述

在外部排序中,当数据量超过内存容量时,常把数据分成若干有序归并段,再用多路归并合并。若采用简单的线性扫描,每输出一个元素需比较所有归并段的首元素;败者树把这一选择过程组织成树,使每次选出最小元素后重新调整的代价降到对数级,大幅减少比较次数。

核心原理

• 叶子结点对应各路归并段当前待比较的元素,内部结点保存比较中的败者索引。
• 每场比较中较小者为胜者继续向上参赛,较大者为败者留在内部结点。
• 全局最小元素被输出后,只需用该路的下一个元素替换对应叶子。
• 沿从该叶子到根的路径逐层与结点中的败者比较,更新败者并向上传递新的胜者,只需对数次比较。

应用场景

败者树最典型的用途是外部排序的多路归并阶段,尤其在归并路数较多时,它比逐路扫描高效得多。数据库系统在处理大规模排序、聚合与连接时,底层归并常借助此类选择树。它也可用于合并多个有序数据流,如日志合并与检索系统中的多路倒排表求交。

常见问题

问:败者树和胜者树有什么区别?答:胜者树内部结点保存比较的胜者,更新时需与兄弟结点比较;败者树保存败者,更新时只需与路径上的父结点比较,因此实现中调整过程更简洁、比较次数略少。

问:归并路数为 k 时性能如何?答:选出一个最小元素后重新调整的比较次数约为以二为底 k 的对数级,故总体归并所有元素的比较代价与元素数乘以路数对数成正比。