Simple query, 10 million records...MySQL ten times faster

I have this table:

CREATE TABLE test_zip_assoc (
    id serial NOT NULL,
    f_id integer DEFAULT 0 NOT NULL,
    lat_radians numeric(6,5) DEFAULT 0.00000 NOT NULL,
    long_radians numeric(6,5) DEFAULT 0.00000 NOT NULL
);
CREATE INDEX lat_radians ON test_zip_assoc USING btree (lat_radians);
CREATE INDEX long_radians ON test_zip_assoc USING btree
(long_radians);



It's basically a table that associates some foreign_key (for an event,
for instance) with a particular location using longitude and
latitude.  I'm basically doing a simple proximity search.  I have
populated the database with *10 million* records.  I then test
performance by picking 50 zip codes at random and finding the records
within 50 miles with a query like this:

SELECT id
    FROM test_zip_assoc
    WHERE
        lat_radians > 0.69014816041
        AND lat_radians < 0.71538026567
        AND long_radians > -1.35446228028
        AND long_radians < -1.32923017502


On my development server (dual proc/dual core Opteron 2.8 Ghz with 4GB
ram) this query averages 1.5 seconds each time it runs after a brief
warmup period.  In PostGreSQL it averages about 15 seconds.

Both of those times are too slow.  I need the query to run in under a
second with as many as a billion records.  I don't know if this is
possible but I'm really hoping someone can help me restructure my
indexes (multicolumn?, multiple indexes with a 'where' clause?) so
that I can get this running as fast as possible.

If I need to consider some non-database data structure in RAM I will
do that too.  Any help or tips would be greatly appreciated.  I'm
willing to go to greath lengths to test this if someone can make a
good suggestion that sounds like it has a reasonable chance of
improving the speed of this search.  There's an extensive thread on my
efforts already here:

http://phpbuilder.com/board/showthread.php?t=10331619&page=10