Crear paginación desde múltiples fuentes

Question

Necesito crear una tabla HTML con paginación. Los datos provienen de 2 fuentes diferentes (pueden ser 2 tablas de 2 bases de datos diferentes, como un Oracle y otra es MySQL) que no se puede usar con una declaración de selección. Para hacerlo más complicado, necesito mostrar los datos ordenados por marca de tiempo (uno de la propiedad es marca de tiempo) en orden ascendente.

Por ejemplo, la fuente A tiene 45 registros, la fuente B tiene 55 registros. Entonces, la tabla mostrará registros totales de 100, pero solo mostrará, digamos, 15 registros a la vez. Entonces tiene que haber 7 páginas (6 páginas con 15 registros y 1 página con 10 registros).

El ejemplo anterior es solo un total de 100 registros que pueden ser fáciles de cargar para la memoria. Pero en la producción real, podría ser de miles o millones de registros. ¿Alguien sabe algún algoritmo que pueda usar? Los parámetros que puedo proporcionar son el número de página y el número de registro por página.

Answer 1

Según tengo entendido, su preocupación es la memoria.

Si las tablas individuales (A y B) no están ordenadas por fecha y hora, debe fusionar todos sus registros en un archivo y luego utilizar algoritmos de clasificación basados ​​en archivos (algo así como MergeSort, en un paso obtiene pares ordenados registros, en el segundo pase se ordena 4s etc.). Cuando tiene un archivo con todos los registros en orden ascendente de marcas de tiempo, puede dividirlo en páginas.

Si las tablas ya están ordenadas de lo que necesita fusionar N secuencias ordenadas en una. Le sugiero que organice una especie de Heap para realizar un seguimiento de cuál de las N fuentes tiene el elemento con la marca de tiempo más pequeña. En pseudocódigo se vería así:

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 
    } 
} 

La complejidad es O (M * logN) donde M es el número total de registros en las tablas y N es el número de mesas. Todo este asunto de Heap solo vale la molestia si N es lo suficientemente grande (mi suposición es ~ 100). De lo contrario, iría con la búsqueda lineal y O (N * M).