从多个源创建分页

Question

我需要创建一个带有分页的HTML表。数据来自两个不同的来源（可能是来自两个不同数据库的两个表，比如一个Oracle，另一个是MySQL），您不能使用JOIN select语句。为了使它更复杂，我需要以升序显示按时间戳排序的数据（其中一个属性是timestamp）。

例如，源A有45条记录，源B有55条记录。因此，该表将显示总共100条记录，但一次只显示15条记录。因此必须有7页（6页15条记录，1页10条记录）。

上面的例子总共有100条记录，这可能很容易让内存加载它们。但在实际生产中，它可能是数千或数百万张唱片。有人知道我可以使用的算法吗？我可以提供的参数是页码和每页记录的数量。

Answer 1

据我所知，你关心的是记忆。

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

如果表已经排序，则需要将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）。