Comment by bob1029 | Hacker News Reader

Comment by bob1029 | Hacker News Reader

Parent Full thread

> Wouldn't a better skip list have "down pointers" at each node so you don't have to retrace your work at each layer?

You don't have to retrace your work, per this example on 5 you could imagine there being implicit "down" pointers in that aggregate block, so you would go from L3 straight down to the data item once you hit that first logical element. This would be 2 I/O operations in my implementations.

Think:

  public class SkipListNode
  {
    public SkipListNode? Layer3;
    public SkipListNode? Layer2;
    public SkipListNode? Layer1;
    public SkipListNode Layer0;
  }

Once you find the one that has all 4 non-null, you can just grab the item at Layer0 without anymore searching.

I discussed this method a little more in a blog post (https://blog.twitter.com/engineering/en_us/topics/infrastruc...), if you are trying to get an intuition here:

> we only allocate one pointer for every level of the skip list. In a typical skip list, a node will have a value, a pointer to the next largest element in the list and a pointer to the lower level of the skip list. This means that a new value allocated into the second level will require the space for two values and four pointers. We avoid this by always allocating skip list towers contiguously. Each level K pointer will only point to other level K pointers, so to extract the value associated with a level K pointer P, you read the value at P - K. Once you reach a node with a value greater than the one you are searching for, you go back to the previous node, and descend a level by simply subtracting one from the pointer. This lets us allocate a value into the second level by just consuming the space for the value and two pointers. It also reduces the amount of time we need to spend chasing pointers, because a pointer into a tower is likely to be on the same cache line as the lower pointers in that tower.

Reply on news.ycombinator.com