从多个来源创建分页

Question

我需要创建一个带分页的HTML表.数据来自2个不同的来源(可能是来自2个不同数据库的2个表,如一个Oracle,另一个是MySQL),您无法使用连接的select语句.为了使它更复杂,我需要按升序显示按时间戳排序的数据(其中一个属性是时间戳).

例如,源A有45条记录,源B有55条记录.因此,该表将显示总记录100,但只显示一次说15条记录.所以必须有7页(6页有15条记录,1页有10条记录).

上面的示例总共只有100条记录,内存可能很容易加载它们.但在实际生产中,它可能是数千或数百万条记录.有谁知道我可以使用的任何算法？我可以提供的参数是页码和每页的记录数.

Answer 1

据我了解，您关心的是内存。

如果单个表（A 和 B）没有按时间戳排序，那么您需要将它们的所有记录合并到一个文件中，然后使用某种基于文件的排序算法（类似于 MergeSort，一次传递即可获得已排序的记录对，在第二次通过时，你会得到排序 4 等）。当您的文件中所有记录均按时间戳升序排列时，您可以将其分成几页。

如果表已经排序，那么您需要将N 个排序序列合并为一个。我建议您组织某种堆来跟踪 N 个源中哪一个具有最小时间戳的项目。在伪代码中它看起来像这样：

for i=1,N
{
  Add the 1st record from each table to the Heap
}
while(Heap not empty)
{
  x = take the smallest item from the heap, noting which table j this record belonged to
  Add x to output
  if (the j-th table is not completely processed)
  {
    take the next value from the j-th table and insert it into the heap
  }
}

复杂度为 O(M*logN)，其中 M 是表中的记录总数，N 是表的数量。只有当 N 足够大（我的猜测是 ~100）时，整个堆的事情才值得麻烦。否则我会使用线性搜索和 O(N*M)。