Sounds like you have a candidate for splitting the data into multiple, related tables. What sort of database are you using? (i.e. MS Access, SQL, etc.) Incidentally, re speed - correct table design/separation within a relational database environment, coupled with good SQL query design, will undoubtedly speed up your searches. Think in terms of fractions of a second for a completed query.
