Shulou(Shulou.com)06/01 Report--

In this issue, the editor will bring you about the SkipList used by both Redis and Kafka. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Jump table is widely used in a variety of cache implementation, its main advantage is that it can insert, query and delete stably like red-black tree, AVL and other balanced trees. The time complexity of the theoretical insertion query deletion algorithm is O (logN).

What is a jump watch?

Linked list, I believe we are not strange, to maintain an orderly linked list is a very simple thing, we all know that in an ordered linked list, the algorithm complexity of query and insertion is O (n).

Can we optimize it, for example, can we compare two at a time? Wouldn't that cut the time in half?

By the same token, if we were four to four, wouldn't it be faster?

Jump table is such a data structure, nodes are skipped part, thus speeding up the speed of the query. What's the difference between a meter and a red-black tree? Since the complexity of the two algorithms is similar, why should Redis use a jump table instead of a red-black tree? Compared with the red-black tree, the jump table mainly has the following advantages: 1. The code is relatively simple, it is possible to write a jump table by hand, try writing a red-black tree by hand. two。 If we want to query the values in an interval, it may be troublesome to use a balanced tree. The trouble here refers to the implementation and understanding, balanced binary tree query a section of the interval can also be done. 3. Delete an interval, if this is a balanced binary tree, it will be very difficult, after all, the design of the tree balance problem, but the jump table does not have this kind of worry. Well, I believe you already have some understanding of the jump table, let's briefly introduce a few basic operations of balanced binary tree.

Query

If we want to query 11, then we start from the top and find that the next one is 5, and the next one is 13, which is already greater than 11, so go to the next layer, the next one is 9, look for the next one, and the next one is 13 again. Enter the next layer again. Finally found 11.

Isn't it very simple? We can summarize the search process into a binary expression (is the next one greater than the result? Next: next floor). It is very important to understand the query process of skipping tables. Try querying other numbers. As long as you understand the query, the latter two are very simple.

insert

When you insert, you first make a query, and then start at the bottom and insert the inserted element. Then see if you need to insert layer by layer from the bottom up. But do you want to insert the upper layer or not? As we all know, we want each jump to be very efficient, and the more balanced it is, the better it is (level 1 at the first level, level 2 at the second level, level 4 at the third level, and level 8 at the fourth level). However, the implementation of the algorithm is indeed very complex, and we have to adjust the original structure strictly according to the exponent power of the two places. So the idea of the jump meter is to flip a coin, resign to fate, generate a random number, and then expand upward in 50% probability, otherwise it will end. In this way, the probability that each element can have an X layer is 0.5 ^ (Xmi 1). On the other hand, you can calculate the mathematical expectation of how many elements there are in layer X.

Delete

Like insertion, deletion is found first, and then deleted one by one from the bottom up. It's relatively simple, so I won't talk about it any more.

Kafka uses ConcurrentSkipListMap in each log object of Kafka to save each log segment, and the baseOffset of each log segment is used as key, so that the log segment where the message is located can be quickly located according to the specified offset.

Summary

Jump table, using a non-commonly used computer problem-solving ideas, random. Random is widely used in the field of deep learning and artificial intelligence.

The above is the editor for you to share the Redis and Kafka are used in SkipList is how, if you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.