リーダーボードの効率的なデータ構造

Question

私はリーダーボードを実装したいと思いますが、これは単純なタスクであるように見えますが、これは非常に複雑になることがあります。私は単に適切なインデックスを持つデータベースを使用することができますが、以下の操作をサポートできる効率的なデータ構造があるかどうかを知りたいと思います。与えられたプレイヤー

現在のプレイヤーランク

サポートの上方および下方のスコアを持つ選手を取得与えられたプレイヤー

のためのランクを取得与えられたプレイヤー

のための最高のスコアを取得するための

• 追加スコア異なる時間枠：今日のスコア、今週、今年など
• 〜100,000人までのスケール
• メモリフットプリントは可能な限り小さいe（すなわち安い機械で走る）

ありがとう！

Answer 1

合計スコアに基づいてプレーヤ情報を格納するために、バイナリ検索ツリー（AVLまたは赤黒のような平衡型のもの）を使用できます。プレーヤー構造内では、トータルスコアとベストスコアの別々の変数を使用して、異なる時間枠で異なる配列を持つことができます。特定のプレイヤーの下または上のプレーヤーまたはランクを見つけるには、順番にトラバーサルが必要です。