An overview of the
The linked list in a linear list is a structure we are all familiar with. The addition and deletion of a linked list are better than that of an array, but random access is not supported. When a linked list is searched, it can only be traversed backwards from the beginning node. As the name suggests, a skip table is a table that can jump, and I drew a simple picture:
Create a new index linked list on the basis of the original list
The original access order of node 5 was: 1->2->3->4->5->6, and a total of 6 nodes were traversed
The order of access for 5 is 1->3->5->5->6(index first)
This linked list plus index structure is a skip table
To find the
As you can see from the introduction, adding a layer of indexes makes access more efficient. What about adding another layer?
We visit node 6 again, the order of access is: 1->5->5->5->6, the number of nodes to visit is reduced again, the original 6 times to visit node 6, now only 5 times to visit node 6
What, not much improvement in efficiency? Ok, I’ll increase the amount of data and you see:
The drawing is a little rough and ready. It used to need 128 traversal times to access node 128, but now it only needs 14 traversal times. It is obvious that hopping table can indeed improve query efficiency
Time complexity
In a linked list, the query time is O(n).
How much can the query time complexity of the hop table be optimized with the addition of indexes? As you can see from the example above, it’s a copy of binary search, time order logn.
Spatial complexity
It is clear that the solution to a skip table is to trade space for time
If the original linked list occupies N space, then the primary index occupies N /2 space and the secondary index occupies N /4 space
Total occupied space =n+ N /2+n/4+… +2=2n-2
So, the space complexity is order n.
Insert and delete
When linked lists have efficient lookups, efficient deletions and inserts are a natural progression.
Before you get too excited, when we insert and delete the data in the linked list, a new index problem arises. When updating the linked list, we also need to update the index. When we update data frequently between two nodes, this will result in too much data in the segment, the index will reduce its meaning, and in extreme cases will degenerate into a single linked list.
So how to ensure the balance of the hop table, avoid the jump table due to the insertion of complexity degradation?
One solution is to add the newly inserted data to the index of the hop table when the linked list inserts new data. This solves the index problem, but it is not desirable to update the node to all indexes and also reduces the efficiency of the query. In this case, a random function, such as: The linked list has a total of 3 level indexes, and the random number is 2, so the newly inserted node is added to the first and second level indexes, as shown below:
Above, is a simple introduction to the hop table!!