Record seach options - millions of records

This is both a general Midrange and RPG question so I've put it here.

I've done the following a number times over the years but the metrics of
a current feature addition to some software will require handling larger
chunks of data than I've dealt with. I'm curious as to how others might
tackle it.

There are three parts:
1) Time required to build/rebuild the data to be searched. Done once a
month.
2) Speed of Searching the data.

Search Environment:
Some of the boxes will be at V4R3
Most will be model 170, 270 with 10 to 20 users using the pgm all day
Some boxes will have 150 to 200 users but tend to be boxes with tons of
horsepower.

Data build environment.
Model 170, max memory, fast disk. Perhaps a model 800 with good
performance.

The data is a proprietary database that arrives in text format and will
be from 2 to 5 million records. Once built into its as400 manifestation
the data will not change during use.
Data elements:
Product type is a 4 byte binary
Part number is a 14 byte char

The Question here (1) is WHAT to build, but wait until the search is
described before we tackle a suggested packaging of the data.

At the point of search the program, as it exists now, returns 1 to 50
records from another database that will wind up in a subfile. If a
retrieved record has data for which there is a match in this new hunk of
data, an "existence" byte will be placed in the subfile record.

I currently have a similar search in the program for which I use a user
index because it appeared to be noticeably faster than searching a key
file of 100,000 records.

So question (2) is: Will the user index be the most efficient method to
use for a search in ILE RPG or will the differences be without
distinction. There WILL be a hit at least 50% of the time. The search is
either 2 keys of 4 btyes and 14 bytes or just 17 bytes as a character
field.

The number keys begs the extra question for those down in guts of the
machine. Do I actually use the 4 byte BINARY number as a number or do I
leave it as 4 character bytes. (bits is bits) Does this effect
efficiency of keys in a keyed file. Doesn't matter to me as these data
elements are only used to search with.

Questions (1) will be based ultimately on the question the search method
use:
Do we build a user index or a keyed file where the key is the only data
in the records?

I will, of course, test to see the time to do the once a month build but
I wonder if anyone has any feel for the what would take longer to do.

Steve Moland
Access Paths Inc
12 Parmenter Rd Unit C4
Londonderry NH 03053
603 845-0190 Ext 2
steve@xxxxxxxxxxx