私がYelpのようなレストラン推奨のためのシステムを設計しているとします。私が実装する必要がある基本的なもののいくつかは次のようになります：実際にシステム設計で検索を高速化するために作成されるデータ構造はどのようになっていますか？
- ユーザーはプレイスを追加/削除/更新できます。
- 位置（経度/緯度）が指定されている場合、ユーザーは指定された半径内のすべての近隣の場所を見つけることができるはずです。
- ユーザーは、場所に関するフィードバック/レビューを追加できるはずです。フィードバックには、写真、テキスト、および評価が含まれます。
私は、ストレージの観点から、場所、緯度、経度、名前、説明、評価ごとにLocationIdのようなフィールドを持つことにしました。ロケーションIDと緯度と経度ごとに約8バイトと仮定すると、システムを5億のロケーションに設計すると、〜500 x 10^6 MBのストレージ要件が発生します。ここまでは順調ですね。
ロケーションクエリーの結果を高速に取得するために、各グリッドが500のロケーションで構成されるグリッドからなるイメージに示すようにQuadtreeを使用することにしました。グリッドが500の場所を超えている場合、それは別のグリッドを形成するために分割され、各レベルの最大グリッドは4になります。私はQuadtreeも作成しました。私はQuatreeを作成した後、それがわからないとどのように私たちはこのツリーを格納していますか？私は考えることができ
1つの可能な方法は、我々は、n分木をシリアライズし、テキストファイルに保存しように私は四分木をシリアル化し、いくつかのような行になることです。ツリーのノードにLocationId、Longitude、Latitudeの詳細を保存することを考慮すると、各フィールドが8バイトであれば、すべての場所に24kbのデータを格納する必要があります。そのような場所が500の場合、私のツリーの合計メモリ要件は〜24 * 500M = 12 GBになります。マシンを再起動するたびに、私はちょうど格納されたツリーをデシリアライズし、サーバーが要求したクエリ操作を実行します。
このアプローチで見られる1つの問題は、場所に関する最新の情報を保持するために、一定の間隔を置いて毎回ファイルを更新する必要があることです。
他のどのような方法でQuadTreeを保存することができますか、どこに保存しますか？上記のようにQuadTreeを保存する方がはるかに優れていると思います。