Mal rendimiento base de datos grande

[Rodrigo1982]

Hola necesito ayuda por favor!! tengo problemas de rendimiento con una base de datos de muchos registros. Solo tengo una tabla porque creo que no se puede inexar o por lo menos no se, las busquedas son lentas. la estructura de mi tabla es asi:

CREATE TABLE `tabla` (
`NOMBRE` varchar(255) default NULL,
`APE1` varchar(255) default NULL,
`APE2` varchar(255) default NULL,
`TLFS` varchar(255) default NULL,
`ROB` int(11) default NULL,
`ORIGEN` varchar(50) default NULL,
`XPROV` varchar(50) default NULL,
`XMUN` varchar(50) default NULL,
`XLOCA` varchar(50) default NULL,
`XCP` varchar(5) default NULL,
`XTV` varchar(5) default NULL,
`XNOMVIA` varchar(50) default NULL,
`XNUMVIA` varchar(150) default NULL,
`XSEX` varchar(1) default NULL
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Ojalá que alguien me pueda ayudar!!!

Gracias!!!