Ayuda con bd grandes

[syntex]

Hola buenas tengo un problema con una base de datos de unas visitas registradas en la web y tienen más de 1/2 millon.

No me anda por la cantidad almacenada.
He visto que se tienen que hacer index en las tablas, las utilizadas en where pero veo que en la bd de las visitas me las muestra todo y no se en que tabla hacer el index para ir mas rápido.

Necesito ayuda.

Os muestro la base de datos

Código PHP:

  mysql_query("CREATE TABLE IF NOT EXISTS `$DB`.`visitas` (
`id` INT UNSIGNED NOT NULL AUTO_INCREMENT ,
`id_usuario` INT( 15 ) NOT NULL ,
`id_agente` INT( 15 ) NOT NULL ,
`ip` VARCHAR( 80 ) NOT NULL ,
`url_access` VARCHAR( 80 ) NOT NULL ,
`explorador` VARCHAR( 80 ) NOT NULL ,
`idioma` VARCHAR( 80 ) NOT NULL ,
`visitado` VARCHAR( 150 ) NOT NULL ,
`url` VARCHAR( 100 ) NOT NULL ,
`fecha` DATE NOT NULL ,
`hora` TIME NOT NULL ,
PRIMARY KEY ( `id` )
) ENGINE = MYISAM",$conexion);  
   

Y como lo hago mostrar

include(pagina_medio.php);

Código PHP:

  <?
     if ($_GET[Pag] == ""){$PagI = 0;}
     elseif ($_GET[Pag] == 1){$pagI = 0;}
     else{$pagI = ((($_GET[Pag]-1)*$_SESSION[TABLCONT]));}
     $pagF = ($_SESSION[TABLCONT]);
     $limit = "$pagI,$pagF";
     $PAGS = $pagF;
?>   

Listado

Código PHP:

  <?
$BD = "visitas";
$WHERE = "";
$ORDENAR = "";
include("../estandar/pagina_medio.php");
?>
<?
$this->Bd->consultar($BD,$WHERE,"$ORDENAR LIMIT $limit");
$Rn = $this->Bd->num_rows();
while ($RR = $this->Bd->obtendatos()){
....................
....................
....................
}
$this->Bd->limpiaconsulta();
?>
<?
<?
$this->Bd->consultar($this->BD,$this->WHERE,$this->ORDENAR);
$Rn = $this->Bd->num_rows();
$this->Bd->limpiaconsulta();
?>
<tr>
<td colspan="20"><? include("../estandar/pagina_abajo.php"); ?></td>
</tr>
<tr>
<td colspan="20"><? include("../estandar/pagina_mas_arriba.php"); ?></td>
</tr>  

A donde pondriais el index en la tabla de la bd?
Como realizariais las consultas más rápidas?

Este script contiene paginaciones.
1. Cuenta resultados para hacer LIMIt paginacion
2. Muestra resultados con WHERE
3. Muestra las paginas para el link de paginacion.

Muchas gracias.