Thanks for the tips.
I made a home-made spatial index by using a 2d collection (HashMap of HashMaps of Lists)-- where the first is ordered by X, and the second is ordered by Y, which then contains a list of points for that spatial index grid cell.
Instead of using every exact x/y value, I just used the lowest whole number multiple of 10. Example: When encountering Point(x,y) with a value of (19.9, 20.0) I would put this into my 2d hashmap spatial index grid location of (19,20).
My x hashmap has keys of ex: 10,20,30.... 400
MY Y hashmap has keys of ex: 10,20,30....200
Then when I receive the rectangle query that the user wants,.. I know (based on the rectangle top-left and bottom-right) - the exact hashmap index key values I need to look in for possible point matches. Once I get each list of possible results, - I can then filter them out based on their actual 2 float decimal places.
This ends up running lightning fast on a cheap computer,.. but not as fast as what I plan to change it to use - which is a "Quad Tree" data structure I see a lot of people using in GIS and video game programming. Sun/Oracle doesn't provide it,.. but there are a couple good examples around online.
Thanks!