The Splay-List: A Distribution-Adaptive Concurrent Skip-List

Created on 2022-01-28T02:50:27-06:00

Return to the Index

This card pertains to a resource available on the internet.

This card can also be read via Gemini.

TODO come back and implement this in nim

Built on top of a standard skip-list.

Some probaility (1/c) of readers will increment a read count on a list node.

Based on conditions a node is allowed to be promoted or demoted in level.

Frequently requested nodes eventually rise to higher levels to be found faster while infrequent nodes are demoted.

Performs as well as a CBTree (over time) but uses more memory because of the pointers.