What you are talking about is a table scan. That is not how you want to
search SQL databases. You need an index which covers the fields you are
searching on and a query which is written so as not to force the SQL server
to do table scans when looking for data. Without seeing the SQL code or
knowing what SQL server you are using (i.e. Sybase, MS SQL, oracle etc..), it
is difficult to be more specific.
Now there is a downside to indexes, especially if you go "index happy", slow
inserts. This is beacuse every index needs to be updated when a record is
inserted. Also you may want to setup period index rebuilding on tables
which have regular large amounts of inserts. This can help with indexes
becoming fragmented on the drives.
ASA Network Computing