Jump table introduction

1、 brief introduction

Orderly collection is common in life , For example, ranking students according to their grades , Rank players according to their scores, etc . For the underlying implementation of ordered sets , You can use arrays 、 Balance tree 、 Chain list, etc . Insertion of array elements 、 Delete ; Although the balanced tree or red black tree is efficient, its structure is complex ; The linked list query needs to traverse all, which is inefficient .Redis Using a jump table . The efficiency of jump table is comparable to that of red and black tree , The implementation is much simpler than the red black tree .

2、 example

Compare ordered linked list and jump list , Find out from the linked list 51

1. Ordered list ：

  The value to find is 51 The elements of , You need to start with the first element and look for 、 Compare to find . A common need 6 Compare it to .

     2. Skip list

 

From 2 Layer start ,1 Node ratio 51 Small node , Compare back .

21 Node ratio 51 Small node , Continue to compare backward , The back is NULL 了 , So from 21 Node down to the 1 layer

In the 1 layer ,41 Node ratio 51 Small node , Keep going backwards ,61 Node ratio 51 Large node , So from 41 Down

In the 0 layer ,51 The node is the node to find , Node found , Co search 4 Time .

It can be seen that the efficiency of jump list is higher than that of ordered linked list