fijar barra de navegacion registros en paginacion

[kakitoski]

hola a todos, os cuento, estoy paginando una Base de datos en php, hasta ahi todo bien, genero dinamicamente una tabla y muestro los registro que quiero por pagina. El problema es la barra de paginacion, es decir, la que me sirve para avanzar una pagina, retrocecer o ir al principio y al fin y es que, al estar bajo la tabla de registros que se genera, dependiendo del tamaño de los campos de los registros esta sube o baja en la pagina final y queda bastante feo que, avanzando o retrocediendo paginas la barra de navegacion de registros vaya subiendo o bajando.
Me gustaria saber si hay alguna forma de aislarla o dejarla fija sea cual sea el tamaño de los registros mostrados.

Un saludo y Gracias!!