Card 02/ 07
Choosing Example: A Leaderboard That Changes Every Second
Scores change constantly, and the page shows the top ten and any player's rank.
A live leaderboard is a choice between structures that each look right at first, and listing its operations settles it. This card covers the operations a game's leaderboard performs, what a heap, a hash map and a balanced binary search tree each charge for them, and why the tree wins.
An online game has 200,000 players. Thousands of scores change every second, every page shows the top ten, and each player's page shows their rank: the number of players with a higher score, plus one. Written down with how often each runs, the operations are these, with n players.
| Operation | How often | Heap | Hash map | Balanced BST |
|---|---|---|---|---|
| Change a player's score | Thousands a second | O(n) to find the old score, then O(log n) | O(1) | O(log n) to remove the old score and insert the new |
| Show the top ten | Every page view | O(10 log n), removing ten and putting them back | O(n) to look at every score | O(log n + 10), walking from the largest key |
| Show a player's rank | Every page view | O(n) | O(n) to count the higher scores | O(log n) when each node stores the size of its subtree |
The hash map changes a score fastest, but it keeps no order, so both questions the page asks become a pass over all 200,000 players. The heap, a tree that keeps the largest score at its root, answers the top of the board cheaply and nothing else: a rank needs the order of every score, which a heap does not keep.
The balanced binary search tree, kept ordered by score with its height held at O(log n), answers all three in O(log n). A rank needs one addition: each node stores the size of its subtree, so a descent from the root adds up the players above a score instead of visiting them. A tree with those counts is called an order-statistic tree.
The tree is keyed by score, so moving a player means finding their old score first, which a hash map from player to score holds. Redis's sorted set, which many live leaderboards run on, pairs the same two: a hash table from member to score, and an ordered skip list, a structure with the costs of a balanced tree, which answers a rank in O(log n).
The deciding row is the rank. Without it, a heap beside the hash map would do; with it, the program asks for the order of every score, which only an ordered structure keeps.
← → move through sections and cards