Skip table is a kind of magical data structure, because almost all versions of undergraduate textbooks do not have this kind of data structure, and god book “Introduction to Algorithms”, “algorithm fourth edition” these two books also do not introduce skip table. However, the time complexity for inserting, deleting, and looking up elements is of the same order of magnitude as that for red-black trees (O(logn)), and there is one feature of the table that red-black trees cannot match (more on that later). So in industry, they’re used a lot. No more nonsense, start today’s skip watch study.

In this article, you can get the following information:

  • What is a skip watch?
  • The process of finding, inserting, and deleting elements in a hop table
  • The time complexity of lookup, insert, and delete elements in a hop table
  • How do I dynamically maintain an index when a hop table inserts an element?
  • Why does Redis choose to implement ordered collections using jumpers rather than red-black trees?
  • Other industrial scenarios that use jumpers

Friendship tip: below in the table insert data, will tell how to dynamically maintain the index, the implementation is relatively simple, the logic is more around, do not give up, come on!! If you don’t understand it again, you can choose to temporarily skip, after all, this piece of biased source code. However, the reader must know that the time complexity of the search, insert and delete of the hop table is O(logn), and the elements can be found in accordance with the range. When some scenarios are encountered in the work, it is necessary to think of the use of the hop table to solve the problem. After all, you would normally work directly with a wrapped hop table, such as ConcurrentSkipListMap() under java.util.concurrent.

To understand a skip list, start with a singly linked list

Here is a simple ordered single linked list. The property of a single linked list is that each element stores a reference to the next element. That is, the first element leads to the second element, the second element leads to the third element, and so on until the last element is found.

Now we have a scenario where to quickly find the element 10 in the above list, we have to start from the beginning of the list until we find the element we are looking for. Find paths: 1, 3, 4, 5, 7, 8, 9, 10. Such lookups are inefficient and have a high average time complexity O(n). Is there a way to speed up list lookup? As shown in the figure below, we extract every two elements from the linked list and add the primary index, which points to the original list. That is, 7 of the original list can be found through the down pointer of the primary index 7. Now how do we find the element 10?

First, we searched for 1, 4, 7 and 9 in the index. When we traversed to 9 of the first-level index, we found that the successor node of 9 was 13, which was larger than 10. Therefore, we stopped looking for 9 and found 9 of the original linked list through 9. Have you noticed that after adding the first-level index, the search path is: 1, 4, 7, 9 and 10. There are relatively fewer elements to traverse for the search node. We do not need to traverse all the data before 10, and the search efficiency is improved.

What if we add a secondary index? As shown in the figure below, search paths: 1, 7, 9, 10. Is it more efficient to find ten? This is the idea of “space for time” to improve the efficiency of lookup by indexing linked lists.

Students may think that from the above case, the efficiency of improvement is not obvious. Originally, 8 elements need to be traversed, and 4 elements need to be traversed after half a day of optimization. In fact, the amount of data is too small. As shown in the figure below, if the ordered single chain has 10,000 elements, they are 0~9999 respectively. Now we have a number of index levels, the highest index, just two elements 0, 5000, the second highest index, four elements 0, 2500, 5000, 7500, and so on, when we look at 7890, the search path is 0, 5000, 7500… 7890, the highest level index skips 5000 elements directly, and the lower level index skips 2500 elements directly, making binary lookup possible for linked lists. It can be seen that when the number of elements is large, the efficiency of index improvement is relatively large, similar to binary search.

So by now you have a sense of what a skip table is. A skip list is an ordered linked list that can achieve binary lookup.

The time complexity of the lookup

How much time does it take to find an element in a linked list? The process of finding an element starts with the highest-level index, works its way down to the original list. So, time complexity = height of index * number of elements traversed per index level.

Let’s find the index height of the hop table. As shown in the figure below, assuming that every two nodes will extract one node as the node of the upper level index, and the original linked list has N elements, the first level index has N /2 elements, the second level index has N /4 elements, and the k level index has N /2k elements. The highest level index usually has two elements, namely, the highest level index H satisfies 2 = n/2h, that is, H = log2n-1. The highest level index H is the height of the index layer plus the original data layer, and the total height of the hop table H = log2n.

If we look at the bold arrow in the figure above, it represents the path to find element X. What is the maximum number of elements traversed by each index in the search process?

As shown in the figure, we now reach the k-level index, and we find that the element we are looking for x is greater than y and smaller than Z, so we need to go down from y to k-1, and there is only one W in k-1 that is greater than y and smaller than Z, so in the k-1 index, At most, we iterate over y, w, and z, finding that x is larger than w and smaller than Z, and then dropping down to k-2. Therefore, the most traversal elements of k-2 index are W, u, and z. In fact, each level of the index is similar, each level of the index is two nodes extract a node as the node of the next level of the index. Now we conclude that when each level of the index is two nodes and one node is drawn as the node of the upper level of the index, each level traverses at most three nodes.

The index height of the hop table is H = log2n, and each index traverses a maximum of three elements. So the time complexity of finding an element in the hop table is O(3*logn), and the ellipsis constant is O(logn).

Spatial complexity

It is a typical idea of “space for time”, so some sacrifices are made in space. What is the space complexity?

If the original list contains N elements, the number of primary index elements is N /2, the number of secondary index elements is N /4, the number of tertiary index elements is N /8, and so on. So, the sum of index nodes is: n/2 + N /4 + n/8 +… + 8 + 4 + 2 = n-2, space complexity is O(n).

As shown in the figure below: If every three nodes are selected as an index, the total number of indexes is N /3 + N /9 + N /27 +… Plus 9 plus 3 plus 1 is n over 2, so it’s halved. Therefore, we can reduce the space complexity by reducing the number of indexes, but the corresponding search efficiency will definitely decrease to some extent. We can control the threshold according to our application scenarios, and see whether we pay more attention to time or space.

But, index nodes usually only need to store keys and a few Pointers, and do not need to store the whole object, so when the object is much larger than the index node, the extra space occupied by the index can be ignored. For example, we now need to index all students with a skip table. Students have many attributes: student ID, name, gender, ID number, age, home address, height, weight, etc. Student’s various attributes only need to store a copy in the original linked list, we only need to use the student number (int type data) to establish the index, so the index relative to the original data, the space occupied can be ignored.

Insert data

Inserting data also seems easy. The original linked list of the hop table needs to be kept in order, so we find where elements should be inserted just as we would find elements. As shown in the figure below, to insert data 6, the whole process is similar to finding 6, the entire search path is 1, 1, 1, 4, 4, 5. 5 is less than 6 but the subsequent node 7 is greater than 6, so 6 should be inserted after 5 and before 7. The total time is O(logn) to find the element.

As shown in the figure below, if you keep adding data to the original list without updating the index, there may be a very large number of data between the two index nodes. In extreme cases, the skip table degrades to a single linked list, which degrades the search efficiency from O(logn) to O(n). So how do you solve this problem? When inserting data, index nodes also need to increase or rebuild indexes accordingly to avoid degradation of search efficiency. So how do we maintain this index?

The easy way to do this is to completely rebuild the index, we insert data, we drop the index of the hop table and rebuild the whole, what is the time complexity of rebuilding the index? Because the space complexity of an index is O(n), that is, the number of index nodes is O(n) level, and the time complexity is also O(n) when an index of O(n) level is completely rebuilt every time. This results in O(n) time per insert in order to maintain the index.

Are there other efficient ways to maintain an index? If the probability of promotion at each level of the table is 1/2, the ideal index is to extract one element every other in the original list as the primary index. In other words, if we randomly select n/2 elements from the original list as the primary index, can we improve the efficiency of the search through the index? Of course you can, because the random selection is relatively uniform. As shown in the figure below, n/2 elements are randomly selected as the first-level index. Although one element is not extracted every other element, it has little impact on the search efficiency. For example, if we want to find element 16, we can still pass the first-level index, which reduces the traversal path by nearly half. If the elements of the extracted primary index are exactly the first half of elements 1, 3, 4, 5, 7, 8, then the search efficiency does not improve, but the probability is very small. We can assume that if the number of elements in the original list is large enough and the selection is random enough, the index we get is uniform. It is important to understand that well-designed data structures are designed to deal with large data volumes. If the original list had only five elements, it would not matter to iterate through five elements in sequence because there is too little data. So, we can maintain an index that randomly selects N /2 elements as the primary index, n/4 elements as the secondary index, n/8 elements as the tertiary index, and so on, all the way to the top level index. Here, the number of index elements of each layer has been determined, and the index elements of each layer are selected randomly enough, so the search efficiency of the hop table can be improved through the index.

So how does the code work to make the jumper look like this? Each time a new element is inserted, try to make it have a 1/2 chance of being indexed at level 1, a 1/4 chance of being indexed at level 2, a 1/8 chance of being indexed at level 3, and so on. Now we need a probabilistic algorithm to help us control the 1/2, 1/4, 1/8… Each time there is data to be inserted, the probability algorithm tells us how many index levels the element needs to be inserted into, and then starts to maintain the index and insert the data into the original list. Let’s start by explaining how this probabilistic algorithm code is implemented.

We can implement a randomLevel() method that randomly generates a number between 1 and MAX_LEVEL (the highest level of the index) with a 1/2 chance of returning 1, a 1/4 chance of returning 2, a 1/8 chance of returning 3, and so on.

  • The randomLevel() method returns 1 to indicate that the currently inserted element does not need to be indexed and only needs to be stored in the original list (probability 1/2)
  • The randomLevel() method returns 2 to indicate that the currently inserted element requires a level 1 index (probability 1/4).
  • RandomLevel () returns 3 to indicate that the currently inserted element needs a secondary index (probability 1/8)
  • The randomLevel() method returns 4 to indicate that the currently inserted element needs a tertiary index (probability 1/16).
  • . And so on

So, with the randomLevel() method, we can control the number of elements in the index at all levels of the table. The randomLevel() method returns 2 with a one-fourth chance of returning 2. We want the number of elements in the index to be 1/2 of the original number. How can the number of primary index elements become 1/4 of the original list? If we take a look at the picture below, it should make sense.

Assuming that when we insert element 6, the randomLevel() method returns 1, we do not index 6. When 7 is inserted, the randomLevel() method returns 3, so we need to create a secondary index for element 7. Here we find a feature: when creating a secondary index, it also creates a primary index; When a tertiary index is created, both primary and secondary indexes are created. So, the number of elements in the first-level index is equal to [number of original list elements] * [probability that randomLevel() returns a value greater than 1]. RandomLevel () returns a value greater than 1, so the ratio of the number of elements in the index to the number of original data is equal to the probability that randomLevel() returns a value greater than 1. What is the probability that randomLevel() returns a value greater than 1? Because randomLevel() randomly generates numbers from 1 to MAX_LEVEL, and randomLevel() returns a value of 1 with a probability of 1/2, randomLevel() returns a value greater than 1 with a probability of 1-1/2 = 1/2. That is, through the above process, the number of elements in the level 1 index accounts for 1/2 of the number of original data.

Similarly, when randomLevel() returns a value greater than 2, secondary or higher indexes will be created and elements will be added to the secondary index, so the ratio of the number of elements in the secondary index to the original data is the probability that randomLevel() returns a value greater than 2. The randomLevel() method returns a value greater than 2 with a probability of 1 minus the probability that randomLevel() = 1 or =2, i.e. 1-1/2-1/4 = 1/4. OK, we achieved our design goal: the number of elements in the secondary index is 1/4 of the original data.

By analogy, the following two conditions can be observed:

  • The randomLevel() method randomly generates a number between 1 and MAX_LEVEL (MAX_LEVEL represents the highest level of the index) with a 1/2 chance of returning 1, a 1/4 chance of returning 2, and a 1/8 chance of returning 3…
  • RandomLevel () returns 1 with no index, 2 with primary index, 3 with secondary index, 4 with tertiary index…

That is, the number of elements in the primary index should account for 1/2 of the original data, the number of elements in the secondary index should account for 1/4 of the original data, the number of elements in the tertiary index should account for 1/8 of the original data, and so on, all the way to the top-level index.

But how to design such a randomLevel() method? Direct masturbation code:

// The randomLevel method will randomly generate a number between 1 and MAX_LEVEL, and: // 1/2 returns 1/ / 1/4 returns 2 // 1/8 returns 3 and so on private intrandomLevel() { int level = 1; // When level < MAX_LEVEL and the random number is less than the set promotion probability, level + 1while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
    level += 1;
  return level;
}
Copy the code

The code above does what we do, and in our case SKIPLIST_P is 1/2 of the probability of promotion, i.e., one node out of every two is pulled out as the node of the upper index. If we want to save space, we can reduce the number of index elements by reducing SKIPLIST_P in Redis zset. SKIPLIST_P is 0.25. The zslRandomLevel function in Redis t_zset.c is implemented as follows:

Redis source code (random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF) is functionally equivalent to my code math.random () < SKIPLIST_P, It’s just that Redis author Antirez uses bit operations to make floating-point comparisons more efficient.

So you get the idea, what is the time complexity of maintaining the index when you insert data? The time complexity of inserting an element into a single linked list is O(1), and the height of our index is at most logn. When inserting an element X, the worst case is that element X needs to be inserted into each index, so the worst time complexity of inserting data into each index is O(logn).

The process is generally understood, and then through an example to describe the whole process of inserting data into the hop table. Now we want to insert data 6 into the table. RandomLevel () returns 3, indicating that we need to add element 6 to the primary and secondary indexes. Select * from 1; select * from 1; select * from 1; select * from 1;

If 6 is larger than 1 and smaller than 7, add an element 6 between 1 and 7 in the secondary index and continue to sink from element 1 to the primary index.

6 is larger than 1 and smaller than 4, so it is found that 6 is larger than 4 and smaller than 7. In this case, we need to add an element 6 between 4 and 7 in the first index, and point 6 of the second index to 6 of the first index. Finally, we continue to sink from element 4 to the original list.

The path of the whole insertion process is similar to the path of finding elements. The time complexity of inserting elements in each level index is O(1), so the time complexity of the whole insertion is O(logn).

Delete the data

When a jumper deletes data, the corresponding node in the index must also be deleted. As shown in the figure below, if you want to delete element 9, you need to delete both 9 in the original list and 9 in the first-level index.

What is the time complexity of deleting elements in a hop table?

The process of deleting an element is similar to that of finding an element, except that if the element x to be deleted is found along the path being searched, the deletion is performed. In a skip table, each index layer is actually an ordered single linked list. The time complexity of element deletion in a single linked list is O(1). The number of index layers is logn, which means that at most logn elements need to be deleted. Therefore, the total time of deleting an element is O(logn) + O(logn) = 2 O(logn). Ignoring the constant part, the time complexity of deleting an element is O(logn).

conclusion

  1. Skip list is an ordered linked list which can realize binary search.

  2. Randomly generate the level of each element as it is inserted;

  3. The lowest level contains all the elements;

  4. If an element appears at level(x), it must appear at levels below x;

  5. Each index node contains two Pointers, one down and one right; Redis zset does not have a pointer down, so how to jump from a secondary index to a primary index? Leave a suspense, see the source code, the end of the article has the source code to implement the hop table)

  6. The time complexity of query, insert and delete of hop table is O(log N), which is close to balanced binary tree.

Why does Redis choose to implement ordered collections using jumpers rather than red-black trees?

Ordered Collections (zset) in Redis supports the following operations:

  1. Insert an element

  2. Delete an element

  3. Finding an element

  4. Print all elements in order

  5. Find elements by range (such as data between [100, 356])

Among them, the first four operations of red-black tree can also be completed, and the time complexity is the same as the hop table. However, a red-black tree is not as efficient as a skip table in finding data by interval. When searching data according to the interval, the skip table can locate the starting point of the interval in order of O(logn) time complexity, and then iterate through the original linked list in order, which is very efficient.

Other industrial scenarios that use jumpers

I have never seen a student talk about the HBase MemStore data structure on my blog. In fact, HBase MemStore uses skip tables to store data internally. Why is that? HBase is an LSM Tree database. LSM Tree databases have a feature that data written in real time is first written to the memory. When the memory reaches the threshold and is flushed to disk, ordered files like StoreFile are generated. Therefore, the efficiency of flush is very high, and the performance of hop table lookup, insert, and delete is very high. This is one of the reasons why HBase MemStore uses hop tables to store data internally. ConcurrentSkipListMap() under java.util.concurrent is used in HBase.

LevelDB, Google’s open source key/value storage engine, and RocksDB, Facebook’s optimized based on LevelDB, are LSM Tree databases, and their internal MemTable uses the data structure of hop table.

I will post an in-depth analysis of the LSM Tree blog later, and then analyze the use of hops in combination with scenarios.

Reference:

Redis zset source

Geek Time – The Beauty of Data Structures and Algorithms

  • Professor Wang’s whole set of courses are excellent, students who want to improve the overall data structure and algorithm can subscribe

Wang Zheng SkipList teacher implementation

  • The implementation of this hop table is relatively simple, and it is recommended for beginners to refer to it. The whole project is the supporting code of Teacher Wang Zheng’s Geek time course, and other data structure implementation can also be referred to
  • While writing this blog, I committed pr to the project, which has been merged to re-implement the randomLevel() method, copying the Redis source code, but to make it easier to understand that the randomLevel() method did not use the Redis bit operation, resulting in a particularly redundant index. The number of elements in the index below level 5 is close to the number of all elements. Interested students can continue to study in depth

Source code 5: Lingbo micro – explore the “skip list” internal structure

  • Lao Qian’s Redis Deep Adventure series is highly recommended

Please, don’t ask me to skip the clock in the interview!

  • Most of the collection classes under the Java java.util.concurrent package are analyzed at the source level, which is highly recommended

Welcome to follow the author’s blog, and continue to update the following articles on data structure and algorithm, big data, Flink practice and fundamentals