Effective data structure for leaderboard i.e. list of entries (name, points) - Effective search (name), Search (rank) and Update (points)

Question

Please suggest a data structure to represent the list of records in memory . Each entry consists of:

• Username
• Points
• Rank (based on points) - optional field - can either be stored in the record or can be calculated dynamically

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

• Insert (record) - can change the rows of existing records
• Delete (record) - can change the ranking of existing records
• GetRecord (name) - A hash table may be created.
• GetRecord (rank)
• Update (points) - can change the rows of existing records

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

I assume that the built-in DBMS memory will be a good solution, but please do not offer it; please suggest a data structure.

Answer 1

Essentially, you just need a couple of balanced search trees that let O (lg n) insert, delete, and getRecord operations. The trick is that instead of storing the actual data in the trees, you will store pointers to a set of record objects, where each record object will contain 5 fields:

1. Username
2. point value
3. Rating
4. pointer back to a 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 only changes when new entries are added and when entries are deleted. The point tree is modified for insertions and deletions, as well as for updates, where the corresponding record is found, the pointer to the point tree is deleted, the point counter is updated, and then a new pointer to the point tree is added.

As you mentioned, you can use a hash table instead of a name tree if you want. The key point here is that you simply maintain separate sorted indexes as a set of unordered records that themselves contain pointers to their index nodes.

---

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

Answer 2

Skipista + hashmap should work.

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

Each node in the set is associated with these properties.

• key is a unique identifier for the node, which is the "username" in your case.
• value - any value associated with node
• score number decides the order (rank) in the set, which are the "points" in your case

Each node in the set is associated with a key. Although the keys are unique, points can be repeated. Nodes are accepted in order (from a low score to a high score) instead of ordering after. If the scores match, the node is ordered by its key in lexicographical order. Each node in can also be accessed by rank, which is a position in a sorted set.

A typical example of using a sorted set is a leaderboard in mass online game mode, where every time a new account appears, you update it using AddOrUpdate (). You can easily use the best users using GetByRankRange (), you can also, given the username, return it by rank in the list using the FindRank () method. Using FindRank () and GetByRankRange () together you can show users with an account similar to this user. Everything is very fast.

Answer 3

Find the DBMS that includes a function to select a record by the serial number of the record.

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

Build a table with a UserName column and a Points column. Make UserName the primary index. Build a secondary non-historical supported index in points.

To get a record with rank R, select the index by points and go to record R.

This forces the DBMS to do most of the work and simplifies your part.