My assumption (probably erroneous) is that I need three byte offset indexes to handle my requirements.

I don't get what your getting here. In a 500 MB file, you will require 29-bits (2**29 == 512 MB) offsets to index the lines in the file, regardless of the length of the keys. Ie. You will need a full 32-bit integer to store those offsets. If your files are ever likely to get bigger than 4GB, you would need to move to using doubles--so 8 bytes per offset. The number of characters you select from the start of your lines to form the key will not affect the offset sizes.

Now the keys. You say you only need 3 characters. And in all your examples, you use only upper case letters. As I pointed out above, there are only 17,576 combinations, so unless your lines are very, very long, you must be expecting duplicate lines with the same first 3 characters?

If that is the case, and the file is sorted as you said above, then you only need build an index of the up to 17,576 starting points for groups of records that share the same first characters as you would have no way to select more closely than that.

Now the requirements. You say you'd like to return the first 25 matches of a partial input. Then in a 500MB file, assuming say 50-char lines (as suggested above) then you will have circa. 600 lines starting with 'AAA'.

Say the input was 'AA'. The first (sorted ordered) 25 entries will (on average) all start with 'AAA'.

Say the input was just 'A'. Again, the first 25 will all start with 'AAA'.

Now perhaps what you mean is that if the input is just 'A', you want to display the first one that starts 'AA', and the first that starts 'AB' ... the first that starts 'AX'?

And if the input is 'AA', then the first that starts 'AAA', the first that starts 'AAB', ... the first that starts 'AAX'? (Assuming there are actually lines in the file matching those.)

If so, then you needn't index any more lines, because you can achieve that with just the 17,576 entry index and a little code:

    my $input = ...;
    if( length( $in ) == 3 ) {
        seek DATA, $index{ $in }, 0;
        print scalar <DATA> for 1 .. 25
    }
    elsif( length( $in ) == 2 ) {
        for( 'A' .. 'X' ) {
            seek DATA, $index{ $in . $_ }, 0;
            print scalar <DATA>;
        }
    }
    elsif( length( $in ) == 1 ) {
        for( 'A' .. 'X' ) {
            seek DATA, $index{ $in . $_ . 'A' }, 0;
            print scalar <DATA>;
        }
    }
[download]

I'm not at all sure any of this is helpful because it is still very unclear what you are trying to achieve. Maybe a few sample lines of the data file with a couple of examples of inputs and outputs would clarify.

Finally, an explanation of why you are avoiding using a DB? If there is any concurrency involved, eg. a web app that maybe used by more than one user at a time; or if the data file is relatively unchanging, then a DB is far simpler. Maybe not the quickest, but certainly the easiest.

Once again, without a clearer idea of what you are trying to achieve, it's hard to be more specific.