Efficient data structure for a leaderboard, i.e., a list of records (name, points) - Efficient Search(name), Search(rank) and Update(points)

Question

Please suggest a data structure for representing a list of records in memory. Each record is made up of:

• User Name
• Points
• Rank (based on Points) - optional field - can be either stored in the record or can be computed dynamically

The data structure should support implementation of the following operations efficiently:

1. Insert(record) - might change ranks of existing records
2. Delete(record) - might change ranks of existing records
3. GetRecord(name) - Probably a hash table will do.
4. GetRecord(rank)
5. Update(points) - might change ranks of existing records

My main problem is efficient implementation of GetRecord(rank), because ranks can change frequently.

I guess an in-memory DBMS would be a good solution, but please don't suggest it; please suggest a data structure.

Answer 1

Basically, you'll just want a pair of balanced search trees, which will allow O(lg n) insertion, deletion, and getRecord operations. The trick is that instead of storing the actual data in the trees, you'll store pointers to a set of record objects, where each record object will contain 5 fields:

1. user name
2. point value
3. rank
4. pointer back to the node in the name tree that references the object
5. pointer back to the node in the point tree that references the object.

The name tree is only modified when new records are added and when records are deleted. The point tree is modified for insertions and deletions, but also for updates, where the appropriate record is found, has its point-tree pointer removed, its point count updated, then a new pointer added to the point-tree.

As you mention, you can use a hash table instead for the name tree if you like. The key here is that you simply maintain separate sorted indexes into a set of otherwise unordered records that themselves contain pointers to their index nodes.

---

The point tree will be some variation on an order statistic tree, which rather than being a specific data structure, is an umbrella term for a binary search tree whose operations are modified to maintain an invariant which makes the requested rank-related operations more efficient than walking the tree. The details of how the invariants are maintained depend on the underlying balanced search tree (red-black tree, avl tree, etc) used.

Answer 2

A skiplist + hashmap should work.

Here is an implementation in Go: https://github.com/wangjia184/sortedset

Every node in the set is associated with these properties.

• key is an unique identity of the node, which is "User name" in your case.
• value is any value associated with the node
• score a number decides the order(rank) in the set, which is "Points" in your case

Each node in the set is associated with a key. While keys are unique, scores may be repeated. Nodes are taken in order (from low score to high score) instead of ordered afterwards. If scores are the same, the node is ordered by its key in lexicographic order. Each node in the set also can be accessed by rank, which represents the position in the sorted set.

A typical use case of sorted set is a leader board in a massive online game, where every time a new score is submitted you update it using AddOrUpdate() method. You can easily take the top users using GetByRankRange() method, you can also, given an user name, return its rank in the listing using FindRank() method. Using FindRank() and GetByRankRange() together you can show users with a score similar to a given user. All very quickly.

Answer 3

Look for a DBMS that includes a function to select a record by sequential record number.

See: How to select the nth row in a SQL database table?

Construct a table with a UserName column and a Points column. Make UserName the primary index. Construct a secondary non-unique maintained index on Points.

To get the record with rank R, select the index on Points and move to record R.

This makes the DBMS engine do most of the work and keeps your part simple.