ジオロケーションのアルゴリズムで相談をお願いします。

データレコード
struct
{
float　　x；
float　　y；
String　buffer;
};
が数千件あるテーブルがあるとします。

その中からユーザーの座標(float ux. float ,uy)の半径 R(float)以内にある
データレコードのbufferを取り出すにはどうすれば一番効率が良くなるでしょうか？

テスト段階での条件では
範囲としては関東全域
Rの値は最大 100m
サーバー側のクロックは
CPUクロック：3GB
使用可能メモリ：6GB〜10GB
レコードの平均使用容量：112byte

クライアント側はAndroidを利用してサーバーからへ座標を渡して、情報をリクエスト、
また新しい情報をポストするのみになります。
送受信にはUDPパケットの使用を考えています。

また挿入や削除がしやすいというのが第一の条件となっています。
なのでデータはすべてメモリ上におき、テキストエディタみたくギャップバッファと地域の細分化、リンクドリストを
複合的に持ち合わせて、定期的にＤＢへのアップデートを行っていこうと考えております。
以上を踏まえてどなたかアドバイスなどをいただけないでしょうか？