Similarity information in skip lists

A non-transitory computer-readable medium having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:

• storing a set of records in a memory of the computer system in a non-key-sorted order;
• maintaining an in-memory skip list that allows for the set of records to be accessed from the memory in key-sorted order, wherein the skip list includes a set of towers of varying depths having entries that store indirect pointers to other towers, and wherein an indirect pointer at a particular depth of a first tower links the first tower to a location corresponding to a second tower and stores an offset value code representing a first amount of similarity between a key of the first tower and a key of the second tower;
• and
• performing a traversal of the skip list for a search key, wherein the performing includes:
• generating a search offset value code representing a second amount of similarity between the key of the first tower and the search key;
• and
• comparing the stored offset value code and the search offset value code to determine whether to advance the traversal to the second tower using the indirect pointer or descend the first tower, wherein the comparing is performed without acquiring a latch on the location corresponding to the second tower.

A system, comprising:

• at least one processor;
• and
• memory having program instructions stored thereon that are executable by the at least one processor to cause the system to perform operations comprising:
• storing a set of records in a memory of the system in a non-key-sorted order;
• maintaining an in-memory skip list that allows for the set of records to be accessed from the memory in key-sorted order, wherein the skip list includes a set of towers of varying depths having entries that store indirect pointers to other towers, and wherein an indirect pointer at a particular depth of a first tower links the first tower to a location corresponding to a second tower and stores an offset value code representing a first amount of similarity between a key of the first tower and a key of the second tower;
• and
• performing a traversal of the skip list for a search key, wherein the performing includes:
• generating a search offset value code representing a second amount of similarity between the key of the first tower and the search key;
• and
• comparing the stored offset value code and the search offset value code to determine whether to advance the traversal to the second tower using the indirect pointer or descend the first tower, wherein the comparing is performed without acquiring a latch on the location corresponding to the second tower.