Averrous Saloom
Being an Engineer by Averrous

Being an Engineer by Averrous

Redis sorted set; Different types of Binary Search Tree

Photo by Sigmund on Unsplash

Redis sorted set; Different types of Binary Search Tree

Part of "I just knew it today!" series. Episode 1: August 7th, 2022

Averrous Saloom's photo
Averrous Saloom
·Aug 6, 2022·

2 min read

Subscribe to my newsletter and never miss my upcoming articles

Table of contents

  • Redis Sorted Set
  • Different Types of Binary Search Tree

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.

 
Share this