Indexing of geometric data

Greetings,

I'm investigating the use of PostgreSQL to maintain a database of
mapping data.  My dataset currently stored latitudes and longitudes as
fixed-precision integers (ie, 37.234 is stored as 37234) in separate
columns: one for latitude, one for longitude.

Postgres has geometric data types, such as point, line, etc, but I'm a
little leary of using them because of performance reasons.  For one, the
internal representation of a point is a pair of double-precision floating
point numbers.  For a dataset containing millions of points, working
with floats could be expensive, both in storage and computation costs.

Second, I want to be able to do queries like "find all line segments
(or points) that overlap or intersect with a given bounding box."  I'm
afraid that without an appropriate index on the set of data points, a
query like that will be extremely slow.

So my questions are: what data structure is used to index a set of points?
Is it a spatially-oriented structure, such as a quadtree, that would make
queries like the example above very fast?  Can Postgres be adapted to
use integers instead of floats to store point coordinates?

Thanks!

Barry