If you're only doing exact matches on the sequence tags, a database is overkill, and will probably be slower than an in-memory hash. If a hash mapping tags to sequences is too big, you can save quite a bit of space by (once) mapping tags to file offsets in your original file (untested): 
use Storable;

open IN, "input.fa";
my %id2off;
while (<IN>) {
    next unless /^>/;
    chomp;
    $id2off{substr($_, 1)} = tell(IN); # file pointer points to start
                                       # of next line
}

store \%id2off, 'input.idx';

[download]
Then later (many times) using this index to retrieve the sequence data (also untested): 
use Storable;
$id2off = retrieve 'input.idx';
open IN, 'input.fa';
while (<>) {
    chomp;
    next unless exists $id2off->{$_};
    print ">$_\n";
    seek(IN, $id2off->{$_}, 0); # move file pointer to start of sequen
+ce
    while (<IN>) {              # print until we reach next sequence
        last if /^>/;
        print;
    }
}

[download]
Sorting your data won't really work so well since, with variable-length records, you have to do a linear scan of the file to find the linebreaks.

In reply to Re: Efficient way to handle huge number of records? by educated_foo
in thread Efficient way to handle huge number of records? by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.