Optimizar base de dato con 18 millones de registro

[ceysmar]

Buenas tengo un problema necesito optimizar una base de dato con 18 millones de registro en la tabla cliente estoy usando Access pero al hacer esta consulta:

Código:

OleDbConnection conexion = new OleDbConnection("Provider=Microsoft.Jet.OLEDB.4.0;Data Source=DataBase\\DataBase.mdb;Jet OLEDB:Database Password=xxxxxx");
            string comando = "SELECT COUNT(id) FROM clientes WHERE cedula=buscar";
            OleDbCommand existe = new OleDbCommand(comando, conexion);
            existe.Parameters.AddWithValue("buscar", buscar);
            conexion.Open();
            int consulta_existe = Convert.ToInt32(existe.ExecuteScalar());

            if (consulta_existe == 1)
            {
                textBox3.Text = Convert.ToString("si existe");
            }
            else {
                textBox3.Text = Convert.ToString("no existe");
            }

            conexion.Close();

Tarda aproximadamente 10 o 15 segundos en darme una respuesta, el código de arriba lo implemente para testear el rendimiento la verdad me tarda aproximadamente el tiempo mencionado en darme una respuesta la pregunta es cómo hago que el resultado sea instantáneo o en 2 segundo que me dicen ustedes… gracias