Abstract: Do you really understand the five basic data structures of Redis? This is something you might want to look at.

This article is from The huawei cloud community “Do you really understand the 5 basic data structures of Redis? You may need to read these knowledge points”, by Li Ba.

A list,

All data structures in Redis use a unique string key to obtain the corresponding value data. Redis has five basic data structures, which are:

  • String (string)

  • List (list)

  • Hash (dictionary)

  • Set

  • Zset (Ordered set)

List, set, Hash, and zset are container data structures that share the following two general rules:

  • Create if not exists: Creates a container if it does not exist

  • Drop if no elements: If there are no elements in the container, the container is immediately dropped to free the memory

This article will detail the five basic data structures of Redis.

2, string (string)

1. Introduction to String (string)

1.1 Internal structure of a String

The string is the simplest and most widely used data structure in Redis. Inside it is an array of characters. As shown in the figure:

A string in Redis is a dynamic string that can be modified; Its implementation in structure is similar to that of ArrayList in Java (an initial array of size 10 is constructed by default), which is the idea of redundantly allocated memory, also known as preallocated memory; This idea reduces the performance cost of capacity expansion.

1.2 String Capacity Expansion

When the size of a string reaches the capacity expansion threshold, the string is expanded. The capacity expansion of the string is as follows:

  1. The length is less than 1MB, which is twice the original size after capacity expansion. length = length * 2

  2. If the length is greater than 1MB, add 1MB after capacity expansion. length = length + 1MB

  3. The maximum length of a character string is 512MB

2. The string instruction

2.1 Add, delete, change, and check a single key value pair

If the set -> key does not exist, the new key is added. If the set -> key exists, the new key is modified

set key value

Get -> query, return value of corresponding key, no return (nil)

get key

Del -> Delete the specified key(key can be multiple)

Del key [key]…

Example:

 1127.0.0.1:6379> set name liziba
 2OK
 3127.0.0.1:6379> get name
 4"liziba"
 5127.0.0.1:6379> set name liziba001
 6OK
 7127.0.0.1:6379> get name
 8"liziba001"
 9127.0.0.1:6379> del name
10(integer) 1
11127.0.0.1:6379> get name
12(nil)
Copy the code

2.2 Batch key-value pairs

The biggest advantage of batch key reading and writing is to save network transmission overhead

Mset -> Batch insert

Mset key value [key value…

Mget -> Batch fetch

Mget key [key]…

Example:

1127.0.0.1:6379> mset name1 liziba1 name2 liziba2 name3 liziba3
2OK
3127.0.0.1:6379> mget name1 name2 name3
41) "liziba1"
52) "liziba2"
63) "liziba3"
Copy the code

2.3 Expiration set command

Expiration set is a mechanism for setting the expiration time of a cache key so that the cache will be deleted automatically after the expiration. A:

expire key seconds

Example:

1127.0.0.1:6379> set name liziba 2OK 3127.0.0.1:6379> get name 4"liziba" 5127.0.0.1:6379> get name 10 # 10s later Return nil 6(integer) 1 7127.0.0.1:6379> get name 8(nil)Copy the code

Method 2:

setex key seconds value

Example:

1127.0.0.1:6379> setex name 10 liziba # 10s after get name return nil 2OK 3127.0.0.1:6379> get name 4(nil)Copy the code

2.4 No Creation Exists No update exists

The set operation above does not create, if it exists, update; Setnx -> Do not exist create do not exist do not update

setnx key value

Example:

1127.0.0.1:6379> get name 2(nil) 3127.0.0.1:6379> setnx name liziba 4(integer) 1 5127.0.0.1:6379> get name 6"liziba" 7127.0.0.1:6379> setnx name liziba_98 # 7127.0.0.1:6379> get name 10"liziba"Copy the code

2.5 count

A string can also be used to count, provided that value is an integer, which can then be incremented. Since the increase scope must be signed in long range access, [9223372036854775808922372368477808]

Incr -> increments by 1

incr key

Example:

1127.0.0.1:6379> set fans 1000 2OK 3127.0.0.1:6379> incr fans # self-increment 1 4(integer) 1001Copy the code

Incrby -> Custom cumulative value

incrby key increment

1127.0.0.1:6379> set fans 1000
2OK
3127.0.0.1:6379> incr fans
4(integer) 1001
5127.0.0.1:6379> incrby fans 999
6(integer) 2000
Copy the code

Tests the incrementing range of values to integers

Max:

1127.0.0.1:6379> set fans 9223372036854775808 2OK 3127.0.0.1:6379> Incr fans 4(error) ERR value is not an integer or out  of rangeCopy the code

The minimum:

1127.0.0.1:6379> Set money -9223372036854775808 2OK 3127.0.0.1:6379> Incrby money -1 4(error) ERR Increment or decrement  would overflowCopy the code

(1) I have a list of books.

1. Introduction to list

1.1 Internal structure of a list

Redis’s list is the equivalent of the LinkedList in the Java language, which is a bidirectional LinkedList data structure (but a clever one, described below) that supports sequential traversal. Linked list structure inserts and deletes quickly, time complexity O(1), query slow, time complexity O(n).

1.2 Application Scenarios of List

Redis is also used for asynchronous queues due to the nature of two-way lists. In actual development, the task structure that needs to be deferred is serialized into a string and placed in the queue of Redis, and another thread retrieves data from the list for subsequent processing. The flow is similar to the figure below:

2. The list instruction

2.1 Right In and Left Out – Queue

Queues are FIFO data structures (such as the order of queuing for tickets) and are often used for similar functions of message queues, such as message queuing, asynchronous processing and other scenarios. This ensures the order in which elements are accessed. Lpush -> adds elements from the left side

Lpush key value [value…

Rpush -> adds elements from the right

Rpush key value [value…]

Llen -> Get the length of the list

llen key

Lpop -> Pop the element from the left

lpop key

1127.0.0.1:6379> rpush code Java C Python # Add element 2(integer) 3 3127.0.0.1:6379> llen code # obtain list length 4(integer) 3 7127.0.0.1:6379> lPOP code 8"c" 9127.0.0.1:6379> lPOP code 10"python" 7127.0.0.1:6379> lPOP code 10"python" 11127.0.0.1:6379> llen code 12(integer) 0 13127.0.0.1:6379> lPOP code 14(nil)Copy the code

2.2 Right in, Right out — stack

The stack is a first in, last out (FILO) data structure in structure (for example, when a cartridge is pressed into a bullet, the order in which the bullets are fired is the stack), and this data structure is generally used for reverse output.

Lpush -> adds elements from the left side

Lpush key value [value…

Rpush -> adds elements from the right

Rpush key value [value…]

Rpop -> Pop the element from the right

rpop code

1127.0.0.1:6379> rpush code Java C Python 2(integer) 3 3127.0.0.1:6379> rpop code # pop the last element to be added 4"python" 5127.0.0.1:6379> Rpop code 6"c" 7127.0.0.1:6379> rpop code 8" Java "9127.0.0.1:6379> rpop code 10(nil)Copy the code

2.3 slow operation

List is a linked list data structure, and its traversal is a slow operation, so the traversal performance will increase with the increase of traversal range. Note that the list index runs negative, -1 for the first to last index, -2 for the second to last index, and so on. Lindex -> iterate to get the value at the specified index of the list

lindex key ind

Lrange -> get all values from index start to stop

lrange key start stop

Ltrim -> truncate all values from start to stop, other values will be deleted

ltrim key start stop

1127.0.0.1:6379> rpush code Java c python 2(integer) 3 3127.0.0.1:6379> lindex code 0 5127.0.0.1:6379> lindex code 1 # fetch data from index 1 6"c" 7127.0.0.1:6379> lindex code 2 # fetch data from index 2 8"python" 9127.0.0.1:6379> 101) "Java" 112) "c" 123) "python" 13127.0.0.1:6379> lrange code 0-1 # 14OK 15127.0.0.1:6379> lrange code 0-1 161) "Java" 172) "c" 183) "python" 19127.0.0.1:6379> Java 20OK 21127.0.0.1:6379> lrange code 0-1 221) "c" 232) "python" lrange code 0-1 221) "c" 232) "python"Copy the code

3, the list of in-depth understanding

The Redis underlying store list is not a simple LinkedList, but a quicklist — a “quicklist.” Quicklist is a quicklist, and I’m still learning about it. Quicklist is a bidirectional list of ziplists; And what is this ziplist? Ziplist refers to a contiguous memory storage space. Redis uses contiguous memory for list storage when the number of elements is small. This reduces the memory consumption caused by adding prev and next Pointers to each element, and most importantly, reduces memory fragmentation.

3.1 Schematic diagram of common linked list structure

Each node element holds a prev-> pointer to the previous node and a next-> pointer to the next node (reference). This structure supports sequential traversal, but it also carries a large memory overhead. A larger percentage of memory will be referenced.

3.2 Ziplist schematic diagram

A ziplist is a contiguous block of memory addresses that can be accessed through address order without holding prev and next Pointers between them.

3.3 QuickList schematic

Quicklist is a bidirectional linked list composed of multiple Ziplists.

4. Hash (dictionary)

1. Introduction to Hash (dictionary)

1.1 Internal structure of hash(dictionary

Redis hash(dictionary) is equivalent to the Java language HashMap, which is an unordered dictionary distributed according to hash values, and the internal elements are stored as key-value pairs.

The implementation of hash(dictionary) is the same as the structure of HashMap (JDK1.7) in Java. Its data structure is also a two-dimensional structure consisting of array and linked list. The node elements are hashed on the array, and the linked list is concatenated on the array nodes if a hash collision occurs.

1.2 Hash (Dictionary) Expansion

Redis hash(dictionary) stores values that can only be string values, and the expansion is different from Java HashMap. In Java, HashMap is completed at one time during expansion, while Redis adopts progressive Rehash strategy in pursuit of high performance considering that its core access is a performance problem of single thread.

Progressive rehash means that it is not done once, it is done multiple times, so the old hash structure needs to be factoring, so the hash(dictionary) in Redis will have both the old and new hash structures, and after the rehash is completed, that is, after the old hash has been moved to the new hash, The new hash completely replaces the old hash in function.

1.3 Usage scenarios of Hash (Dictionary)

A hash(dictionary) is used to store information about an object. A hash represents an object, a key of the hash represents an attribute of the object, and the value of the key represents the value of the attribute. The hash structure, unlike strings, does not require the entire object to be serialized and stored. This allows partial fetching at fetch time. So in contrast, hash(dictionary) has the following advantages and disadvantages:

  • Read Can be partially read to save network traffic

  • Storage consumes more storage than a single string

2 Hash (dictionary) instructions

2.1 Common Hash (dictionary) instructions

Hset -> hash(dictionary) inserts the value. If the dictionary does not exist, create key to represent the name of the dictionary, field equals key, and value is the value of key

hset key field value

Hmset -> batch set value

Hmset key field value [field value…

Example:

17.0.0.1:6379> hset book Java" Thinking in Java" # String containing Spaces requires "wrap 2(integer) 1 3127.0.0.1:6379> hset book python" python Code "4(integer) 1 5127.0.0.1:6379> hset book C "The best of C" 6(integer) 1 7127.0.0.1:6379> hmset book go "concurrency In go" mysql "high performance mysqlCopy the code

Hget -> get the value of the specified key in the dictionary

hget key field

Hgetall -> getall keys and values in the dictionary, newline output

hgetall key

Example:

1127.0.0.1:6379> hget book java
2"Thinking in Java"
3127.0.0.1:6379> hgetall book
41) "java"
52) "Thinking in Java"
63) "python"
74) "Python code"
85) "c"
96) "The best of c"
Copy the code

Hlen -> Get the number of keys for the specified dictionary

hlen key

For example:

1127.0.0.1:6379> hlen book
2(integer) 5
Copy the code

2.2 Hash Using Tips

You can use incr and incrby to auto-add strings whose values are integers. You can also auto-add a single child key if it is an integer in a hash structure.

Hincrby -> Add to the integer value of a key in the hash(dictionary)

hincrby key field increment

1127.0.0.1:6379> hset liziba money 10
2(integer) 1
3127.0.0.1:6379> hincrby liziba money -1
4(integer) 9
5127.0.0.1:6379> hget liziba money
6"9"
Copy the code

Note that an error is reported if it is not an integer.

1127.0.0.1:6379> hset liziba money 10.1
2(integer) 1
3127.0.0.1:6379> hincrby liziba money 1
4(error) ERR hash value is not an integer
Copy the code

A set of

1, Set (set) related introduction

1.1 Internal structure of a set

Redis’s set is the Java equivalent of HashSet, with unordered and unique key-value pairs. It internally implements a special dictionary where all values are null. After the last element in the collection is removed, the data structure is automatically deleted and the memory is reclaimed.

1.2 Usage scenarios of Sets

Set (set) can be used to store the ID of a winning user in an activity because of its special de-duplication function. This ensures that a user does not win twice.

2, set(set) related instructions

Sadd -> Add set member, key set name, member set element, element cannot be repeated

Sadd key member [member…]

1127.0.0.1:6379> Sadd Name Zhangsan 2(integer) 1 3127.0.0.1:6379> Sadd name Zhangsan Repeat 0 4(integer) 0 5127.0.0.1:6379> sadd name Lisi Wangwu Liumazi # Support adding multiple elements at once 6(integer) 3Copy the code

Smembers -> View all the elements in the collection, note that they are unordered

smembers key

1127.0.0.1:6379> smembers name = "lisi", "wangwu", "liumazi", "liumazi", "zhangsan"Copy the code

Sismember -> Queries whether the collection contains an element

sismember key member

1127.0.0.1:6379> sismember name lisi # contains return 12 (integer) 1 3127.0.0.1:6379> sismember name tianqi # Does not contain return 0 4(integer) 0Copy the code

Scard -> Gets the length of the collection

scard key

1127.0.0.1:6379> scard name
2(integer) 4
Copy the code

Spop -> Pop elements, count refers to the number of pop elements

spop key [count]

1127.0.0.1:6379> spop name # default popup a 2"wangwu" 3127.0.0.1:6379> spop name 3 41) "lisi" 52) "zhangsan" 63) "liumazi"Copy the code

Zset (Ordered Set)

1. Introduction to Zset (ordered set)

1.1 Internal structure of Zset (ordered set)

Zset (Ordered set) is the most frequently asked data structure in Redis. It is similar to the combination of SortedSet and HashMap in Java language. On the one hand, it ensures the uniqueness of internal values through set, and on the other hand, it sorts values through score (weight). This sorting is done through Skip lists. When the last element value of the zset is removed, the data structure is automatically deleted and the memory is reclaimed.

1.2 Usage scenarios of Zset (Ordered Set)

Taking advantage of zset’s de-weighting and ordered effects can be used in a number of scenarios, two examples:

  • Store a list of followers, where value is the ID of the followers and score is the timestamp of followers, so that followers can be sorted

  • Store the student’s score, value the student’s ID, score is the student’s score, which can be used to rank the student’s score

2, zset(ordered set) related instructions

Zadd -> add element to zset; add element to zset; add element to zset; add element to zset; add element to zset

Zadd key [NX | XX] [CH] [INCR] score member [score] member…

1127.0.0.1:6379> zadd name 10 zhangsan
2(integer) 1
3127.0.0.1:6379> zadd name 10.1 lisi
4(integer) 1
5127.0.0.1:6379> zadd name 9.9 wangwu
6(integer) 1
Copy the code

2. Zrange -> Gets all the elements in the output set from smallest to largest — but when you have the same weights, you get a lexicographical order for values.

Out-of-range subscripts do not cause errors. For example, when the value of start is greater than the maximum index of an ordered set, or start > stop, the zrange command simply returns an empty list. On the other hand, if the value of the stop argument is greater than the maximum index of the ordered set, Redis treats stop as the maximum index.

You can use the WITHSCORES option to return the member with its score value, returning the list as value1,score1… , valueN,scoreN. Client libraries may return more complex data types, such as arrays, tuples, and so on.

zrange key start stop [WITHSCORES]

1127.0.0.1:6379> zrange name 0-1 21) "wangwu" 32) "zhangsan" 43) "lisi" 5127.0.0.1:6379> zrange name 0 1 # Obtain elements for first and second slots 61) "wangwu" 72) "Zhangsan" 8127.0.0.1:6379> zadd name 10 tianqi # add element 9(integer) 1 10127.0.0.1:6379> zrange name 0 2 # 111) "wangwu" 122) "tianqi" 133) "Zhangsan" 14127.0.0.1:6379> zrange name 0-1 WITHSCORES # WITHSCORES 151) "wangwu" 162) "9.9000000000000004" 173) "Tianqi" 184) "10" 195) "Zhangsan" 206) "10" 217) "lisi" 228) "10.1"Copy the code

3, Zrevrange -> Elements in the output set from large to small according to the score weight. If the weight is the same, it is sorted according to the dictionary reverse order of value

Members are placed in descending order of score (from highest to lowest). Members with the same score value are arranged in reverse Lexicographical order. The ZREVRANGE command is the same as the ZRANGE key start stop [WITHSCORES] command, except that members are arranged in descending order of score

zrevrange key start stop [WITHSCORES]

1127.0.1:6379 > zrevrange name 0-1 WITHSCORES 21) "lisi" 32) "10.1" 43) "zhangsan" 54) "10" 65) "tianqi" 76) "10" 87) "Wangwu 98)" 9.9000000000000004 ""Copy the code

Zcard -> Return the cardinality of the ordered set if the key exists and is of the ordered set type. Returns 0 if key does not exist

zcard key

1127.0.0.1:6379> zcard name
2(integer) 4
Copy the code

Zscore -> return score of member of ordered set key. If member element is not a member of ordered set key, or key does not exist, return nil

zscore key member z

1127.0.0.1:6379> zscore name zhangsan
2"10"
3127.0.0.1:6379> zscore name liziba
4(nil)
Copy the code

6, zrank -> return member rank of ordered set key. Members of the ordered set are arranged in ascending order (from small to large) by score value.

The ranking is based on 0, which means that the member with the lowest score is ranked 0

zrank key member

1127.0.0.1:6379> zrange name 0-1 21) "wangwu" 32) "tianqi" 43) "zhangsan" 54) "lisi" 6127.0.0.1:6379> zrange name 0-1 21) "wangwu" 32) "tianqi" 43) "zhangsan" 54) "lisi" 6127.0.0.1:6379> zrank name wangwu  7(integer) 0Copy the code

Zrangebyscore -> return all members of the ordered set key whose score is between min and Max (including min or Max). Members of an ordered set are arranged in ascending order of score.

Min and Max can be -INF and + INF, so you can use commands like [ZRANGEBYSCORE] without knowing the lowest and highest score values for an ordered set.

By default, the value of an interval is a closed interval, or you can use the optional less than or greater interval by prefixing the parameter with (symbol)

zrangebyscore key min max [WITHSCORES] [LIMIT offset count]

1127.0.0.1:6379> zrange name 0-1 WITHSCORES # "Zhangsan" 76) "10" 87) "lisi" 98) "10.1" 10127.0.0.1:6379> zrangebyScore name 9 10 111)" "Zhangsan" 14127.0.1:6379 > zrangebyscore name 10 WITHSCORES "Tianqi" 184) "10" 195) "zhangsan" 206) "10" 21127.0.0.1:6379> zrangebyScore name - INF 10 # -INF from negative infinity 221)" 232) "tianqi" 243) "zhangsan" 25127.0.0.1:6379> zrangebyScore name - INF + INF # + INF to infinity 261) "wangwu" 272) "tianqi" 285) "zhangsan" 294) "lisi" 30127.0.0.1:6379> zrangebyScore name (10 11 # 10 < score <=11 311) "lisi" 30127.0.0.1:6379> Zrangebyscore name (10 (10.1 # 10 < socre < -11 33(empty list or set) 34127.0.0.1:6379> zrangeByScore name (10 (11 351) "lisi"Copy the code

Zrem -> Remove one or more members of the ordered set key. Non-existing members are ignored

Zrem key member [member…

1127.0.0.1:6379> zrange name 0-1 21) "wangwu" 32) "tianqi" 43) "zhangsan" 54) "lisi" 6127.0.0.1:6379> zrem name Zhangsan # delete element 7(integer) 1 8127.0.0.1:6379> Zrange name 0-1 91) "wangwu" 102) "tianqi" 113) "lisi"Copy the code

Seven, the Skip List

1, the introduction of

Skip table is called skip table, skip table for short. Skip table is a randomized data structure, in essence is a binary search ordered linked list. Skip table in the original ordered list above the increase of multi-level index, through the index to achieve fast search. Skip tables not only improve search performance, but also insert and delete performance.

Skip List, a random data structure, can be regarded as a variation of binary tree, which is very similar to red-black tree and AVL tree in performance. However, Skip List is much easier to implement than the previous two. The current Redis zSet implementation uses Skip List(LevelDB and others also use Skip List).

A simple comparison of RBT red-black trees with Skip List:

RBT red-black tree

  1. Insert and query time complexity O(logn)

  2. Natural order of data

  3. Realize complex, design discoloration, left – right rotation balance and other operations

  4. Need to lock

Skip List Skip List

  1. Insert and query time complexity O(logn)

  2. Natural order of data

  3. Simple implementation, linked list structure

  4. Don’t need to lock

2. Skip List algorithm analysis

2.1 Skip List papers

The Skip List paper is posted here. Please refer to the paper for detailed study. Some formulas, codes and pictures below are from the paper. Skip Lists: A Probabilistic Alternative to Balanced Trees

www.cl.cam.ac.uk/teaching/20…

2.2 Skip List dynamic diagram

To understand the process of inserting node elements in Skip List, use a GIF from Wikipedia.

2.3 Skip List algorithm performance analysis

2.3.1 Algorithm for computing random layers

The first analysis is the process of calculating random numbers during the insertion operation, which involves the calculation of layers, so it is very important. It has the following features for nodes:

  • Each node has a pointer to the first layer

  • The node has a pointer to layer I, so the probability of occurrence of layer I +1 is P

  • The node has a maximum layer limit, MaxLevel

Pseudo-code for computing random layers:

Examples in the paper

Java version

1public int randomLevel(){ 2 int level = 1; 4 while (random() < p && level < MaxLevel){5 level += 1; 6} 7 return level; 8}Copy the code

The code contains two variables P and MaxLevel. In Redis, the values of these two parameters are respectively:

1p = 1/4
2MaxLevel = 64
Copy the code

2.3.2 Average number of Pointers to a node

Skip List belongs to the data structure of space for time. The space here refers to the number of Pointers contained in each node. This part is the extra internal memory overhead, which can be used to measure the space complexity. Random () is a random number, so the higher the number of node layers generated, the lower the probability (the promotion rate data in Redis standard source code is 1/4, and the structure of Skip List is relatively flat with relatively low floors). Its quantitative analysis is as follows:

  • Level = 1 probability 1-p

  • Level >=2 probability p

  • Level = 2 probability p(1-p)

  • Level >= 3 with probability P ^2

  • Level = 3 probability p^2(1-p)

  • Level >=4 with probability P ^3

  • Level = 4 probability p^3(1-p)

  • …

Get the average number of layers of the node (the average number of Pointers contained by the node) :

Therefore, the average number of Pointers calculated by P =1/4 in Redis is 1.33

2.3.3 Time complexity Calculation

The following projections come from the paper

Given p=1/2, in a skip list of 16 elements generated with p=1/2, we might happen to have 9 elements, 1 level of 3 elements, 3 elements of 3 levels, and 1 element of 14 levels (unlikely, but it could happen). How do we deal with this situation? If we used the standard algorithm and started our search at level 14, we would be doing a lot of useless work. So where should we start searching? At this point we assume that there are n elements in SkipList and the expected number of LTH elements is 1/ P. The probability of each element appearing at level L is P ^(L-1), so the expected number of elements at level L is n * (p^L-1); So you get 1 over p is equal to n times p to the L minus 1.

11 / p = n * (p^L-1)
2n = (1/p)^L
3L = log(1/p)^n
Copy the code

Definition: MaxLevel = L(n) = log(1/p)^n

To calculate the time complexity of Skip List, we can use reverse thinking to start from node X with the number of layers I and return to the starting point to trace the time complexity. There are two situations at node X:

  • Node X has a (I +1) layer pointer, so climb up one level with probability P, which corresponds to Situation C in the following figure.

  • Node X does not have a (I +1) layer pointer, so climb one level to the left with a probability of 1-p, corresponding to Situation B below.

Suppose C(k) = the expected cost (i.e. length) of climbing k levels of the search path in an infinite list, then the deduction is as follows:

1 c (0) = 0, 2 c (k) = (1 - p) x search length (b) + p * (to find the length of condition c) 3 c (k) = (1 - p) (c (k) + 1) + p (c (k - 1) + 1) 4 c (k) = 1 / p + c (k - 1) 5 c (k) = k/pCopy the code

According to the above deduction, the expected length of climbing k levels is K/P, and the length of climbing one level is 1/ P.

Since MaxLevel = L(n), C(k) = k/p, the expected value is :(L(n) — 1)/p; L(n) = log(1/p)^n = (log(1/p)^ n-1) /p; Substituting p = 1/2 yields: 2 * log2^n – 2, the time complexity of O(logn).

3. Skip List feature and its implementation

3.1 Skip List features

Skip Lists typically have the following features

  1. Skip List contains multiple layers, each of which is called a level, and the level increases from 0

  2. Skip List 0, the lowest level, should contain all the elements

  3. Each level/ level is an ordered list

  4. X>Z>=0; X>Z>=0; X>Z>=0

  5. Each node element consists of a node key, a node value, and an array of Pointers to the level of the current node

3.2 Skip List Query

Assuming that these elements already exist in the initial Skip List, their distribution would look like this:

At this time, query node 88, and its query route is as follows:

  1. Start from level3 at the top level of Skip List, then query to 10 < 88&& the value of subsequent nodes is null && there is level2 at the bottom level

  2. Level2 10 iterate back, 27 < 88 && subsequent node value is null && there is a lower level1

  3. Level1 27 iterate, 88 = 88, query hit

3.3 Skip List Insertion

The initial structure of Skip List is the same as that in 2.3. At this time, it is assumed that the value of the new node element is 90, and the insertion route is as follows:

  1. The insertion position is queried in the same way as the Skip List query, where the position of the first node larger than 90 needs to be queried and inserted before the node, 88 < 90 < 100

  2. Create a new Node Node(90) and calculate a random level for the inserted Node(90). The probability of the number of layers is roughly calculated as (1/x)^level. If level is greater than the current maximum Level3, head and tail nodes need to be added

  3. Insert Node(88). Next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);

3.4 Delete Skip List

The process of deletion is to query the node, then delete it, and re-combine the nodes on the left and right sides of the deleted node in the form of a linked list. No diagrams are drawn here

4, handwriting to achieve a simple Skip List

Implementing a Skip List is relatively simple and consists of two steps:

  1. Node, which defines Skip List, is stored in the form of linked List among nodes. Therefore, Node holds Pointers of adjacent nodes. Prev and next are Pointers of nodes before and after the same level, and down and up are Pointers of nodes above and below multiple levels of the same Node

  2. The implementation class of Skip List is defined, including node insertion, deletion and query. The query operations are divided into ascending query and descending query (backward and forward query). The default elements of Skip List realized here are ascending linked List

4.1 Defining a Node

The Node class contains the following important attributes:

  1. Score -> The weight of the node, which is the same as score in Redis, used for sorting node elements

  2. Value -> The node stores real data. Only String data can be stored

  3. Prev -> Drives of the current node at the same level

  4. Next -> Next node of the current node, with the same level

  5. Down -> The lower level of the current node, different levels of the same node

  6. Up -> Upper layer node of the current node, different levels of the same node

4.2 Action classes for SkipList node elements

SkipList includes the following important attributes:

  1. Head -> the uppermost head node in SkipList. This node does not store elements and is used to build lists and start queries, as described in 2.3

  2. Tail -> The uppermost tail node of SkipList. This node also does not store elements and is the termination flag of a query for a particular level

  3. Level -> Total number of layers

  4. Size -> Number of node elements in Skip List

  5. Random.nextdouble () < 1/2 add the level of the current node. If the level of the current node exceeds the total level, add head and tail(total level).

Click to follow, the first time to learn about Huawei cloud fresh technology ~