redis sorted set and different types of binary search tree
Part of "I just knew it today!" series. Episode 1: August 7th, 2022
Redis Sorted Set
Redis sorted set is a tool to store sorted data. It sort the data in ascending, and all of the operation is in O(log N) except the data retrieval, as it needs O(log N + M) with M, the count of data retrieved. This cool tool is implemented with skip list and a hash table, as the documentation said: *"Sorted sets are implemented via a dual-ported data structure containing both a skip list and a hash table, so every time we add an element Redis performs an O(log(N)) operation" *
Let's take a look to its commands.
Insert a data
A data in redis sorted set composed from:
<key> <score> <member>
- key is in which sorted set is the data stored
- score is how big is the score of each particular member
- member is the node identifier,
it can be in the form of unique id of the data
To add a member score to the set, use zadd
command:
zadd <key> <score> <member>
zadd leaderboard 20 "uid14"
1
Redis client will return the count of data you add with the command.
Increment/Decrement the score
We can use zincrby
command: zincrby leaderboard -5 "uid14" "15"
Which again, required a key, then amount of the change to the score, and the member id. Redis client will return the end result of the score we modificate
Retrieve a data
We can use zrange
// show the asc sorted data from index 0 to index 10 (included), and also return its score zrange leaderboard 0 10 withscore // show the desc sorted data from index 0 to index 10 //(included) (reversed index), and also return its score zrange leaderboard rev 0 10 withscore
Remove a data
We can use zrem
// remove data member in leaderboard set with member id "uid14" zrem leaderboard "uid14"
Different Types of Binary Search Tree
Been a year since my algorithm and data structure course, and I've been forgetting many of the materials. Balanced binary search tree and its derivation are ones among the coolest data structure I've ever found, it allow us to do read, insert, delete, update in around O(log N) complexity.
AVL tree
AVL tree is a binary search tree with additional property of balanced. The balance is maintained during insert, delete, and build procedure using a subroutine called rotation. Rotation run in constant time.