skiplist

README

go-skip-list

A clean, efficient skip list implementation in Go.

This package provides a probabilistic sorted key-value store with expected O(log n) performance for search, insertion, and deletion.

Features

• Keys and values are []byte
• Keys are maintained in sorted order (bytes.Compare)
• Push acts as upsert (insert or update)
• Zero-allocation Get in the common case
• Iterator support via iter.Seq2 (All())
• Configurable max level and promotion probability

Installation

go get github.com/toastsandwich/skiplist

Quick Start

package main

import (
	"fmt"
	"github.com/toastsandwich/skiplist"
)

func main() {
	s := skiplist.NewSkipList(32, 0.5)

	s.Push([]byte("user:1001"), []byte("Alice"))
	s.Push([]byte("user:1002"), []byte("Bob"))
	s.Push([]byte("user:1001"), []byte("Alice Smith")) // update

	fmt.Println(string(s.Get([]byte("user:1001")))) // Alice Smith

	for k, v := range s.All() {
		fmt.Printf("%s => %s\n", k, v)
	}

	s.Pop([]byte("user:1002"))
}

Documentation

Run go doc or visit the generated documentation:

go doc github.com/toastsandwich/skiplist
# or
go doc -all .

How Skip Lists Work

A skip list is a layered linked list that allows fast search by "skipping" over many elements.

Structure

Level 3:  HEAD -----------------------------------------------> NIL
Level 2:  HEAD --------------------> [30] --------------------> NIL
Level 1:  HEAD --> [10] -----------> [30] -----------> [50] --> NIL
Level 0:  HEAD --> [10] --> [20] --> [30] --> [40] --> [50] --> NIL

• Every element lives on level 0.
• When inserting, we randomly decide how many levels the element should occupy.
• Higher levels contain fewer elements → they act as "express lanes".
• Search starts at the highest level and moves right, then drops down levels as needed.

Insertion Height

The height of a new node is chosen using a geometric distribution:

for l < maxLevel-1 && rand.Float64() < p {
    l++
}

With the default p = 0.5, roughly:

• 50% of nodes appear only on level 0
• 25% reach level 1
• 12.5% reach level 2
• ...and so on

This gives expected O(log n) search time with high probability.

Search Walk

To find a key:

1. Start at the top level from the header.
2. Move right while the next key is less than the search key.
3. When you can't move right, drop one level.
4. Repeat until level 0.
5. Check if the node at level 0 matches.

Why []byte?

Using byte slices makes the structure very flexible (you can encode strings, integers, composite keys, etc.). Ordering is defined by Go's bytes.Compare.

API

func NewSkipList(maxlevel int, p float64) *SkipList

func (s *SkipList) Push(key, val []byte)
func (s *SkipList) Get(key []byte) []byte
func (s *SkipList) Pop(key []byte) []byte
func (s *SkipList) All() iter.Seq2[[]byte, []byte]

NewSkipList

• maxlevel: maximum height of the skip list (defaults to 32 if ≤ 0)
• p: promotion probability (defaults to 0.5 if ≤ 0)

Recommended call:

s := skiplist.NewSkipList(32, 0.5)

Push / Get / Pop

• Push inserts or updates a key.
• Get returns nil for missing keys.
• Pop removes a key and returns its old value (or nil).

Iteration

for key, value := range s.All() {
    // keys are yielded in ascending order
}

The iterator reflects the state at the time of iteration. Modifying the list during iteration is not safe.

Examples

Basic Operations

s := skiplist.NewSkipList(16, 0.5)

s.Push([]byte("a"), []byte("1"))
s.Push([]byte("b"), []byte("2"))
s.Push([]byte("a"), []byte("updated"))   // overwrite

v := s.Get([]byte("a"))                   // []byte("updated")
old := s.Pop([]byte("b"))                 // []byte("2")

Benchmarks

Benchmarks were run on:

• CPU: Intel Core i7-11800H (2.3 GHz)
• OS: Linux
• Go: 1.26.4

go test -bench=. -benchmem -count=3 -benchtime=2s

Results

Benchmark	ns/op	B/op	allocs/op	Notes
Push	450	608	3	Insert new key
Get	181	0	0	Zero-allocation read path
Pop (+ reinsert)	688	864	4	Steady-state delete + restore
Iteration (10k elems)	~89 000	0	0	Full scan via All() (~89 µs)
PushGetMix	790	648	5	Combined insert + lookup workload

Note: The Pop benchmark measures a pop followed by a re-insert to keep the dataset size stable across iterations. All numbers are averages across multiple runs.

Key Observations

• Get performs zero allocations on hits.
• Full iteration over 10,000 elements completes in ~89 µs.
• The structure is very cache-friendly for sequential iteration.

Limitations

• Not thread-safe — external synchronization is required for concurrent use.
• Get cannot distinguish between a missing key and a key whose value is nil/[]byte{}.
• currMaxLevel is tracked internally but currently unused (the structure always uses the full configured MaxLevel).
• Designed primarily for in-memory use cases.

License

This project is licensed under the MIT License — see the LICENSE file for details.

---

Contributions and improvements are welcome!

Documentation

Overview

Package skiplist implements a probabilistic skip list, a sorted key-value store with expected O(log n) search, insert, and delete performance.

Skip lists maintain multiple levels of linked lists. Lower levels contain all elements; higher levels contain fewer elements and serve as shortcuts during search. The height of each inserted element is chosen randomly using a geometric distribution controlled by the probability parameter P.

Keys ([]byte) are ordered using bytes.Compare. Values are also []byte.

The implementation is not concurrent-safe.

Example:

s := NewSkipList(32, 0.5)
s.Push([]byte("alpha"), []byte("first"))
s.Push([]byte("beta"), []byte("second"))

v := s.Get([]byte("alpha")) // []byte("first")

for k, v := range s.All() {
    // iterates in sorted key order
}

s.Pop([]byte("beta"))

Example

Example demonstrates basic usage of SkipList.

s := NewSkipList(16, 0.5)

s.Push([]byte("cat"), []byte("meow"))
s.Push([]byte("dog"), []byte("woof"))
s.Push([]byte("cat"), []byte("purr")) // update

fmt.Println("cat ->", string(s.Get([]byte("cat"))))

fmt.Println("All entries:")
for k, v := range s.All() {
	fmt.Printf("  %s: %s\n", k, v)
}

s.Pop([]byte("dog"))
fmt.Println("After pop dog, len via iteration:")
count := 0
for range s.All() {
	count++
}
fmt.Println("count:", count)

Output:
cat -> purr
All entries:
  cat: purr
  dog: woof
After pop dog, len via iteration:
count: 1

Index

• type Element
  • func (e *Element) SetLevel(l int)
• type SkipList
  • func NewSkipList(maxlevel int, p float64) *SkipList
  • func (s *SkipList) All() iter.Seq2[[]byte, []byte]
  • func (s *SkipList) Get(key []byte) []byte
  • func (s *SkipList) NewElement(key, val []byte, l int) *Element
  • func (s *SkipList) Pop(key []byte) []byte
  • func (s *SkipList) Push(key, val []byte)

Examples

• Package

Types

type Element

type Element struct {
	// Key and Value hold the stored data. Keys are compared with bytes.Compare.
	Key, Value []byte

	// Level is the highest level this element participates in.
	Level int
	// contains filtered or unexported fields
}

Element represents one node in the skip list containing a key/value pair.

Level indicates the highest level (0-based) at which this element appears. Elements at level L are also linked into all levels 0 through L.

func (*Element) SetLevel

func (e *Element) SetLevel(l int)

SetLevel sets the Level of the element. It does not adjust any links.

type SkipList

type SkipList struct {
	// Header is the entry point for searches at every level.
	Header *Element

	// MaxLevel is the maximum height of the skip list.
	MaxLevel int

	// P controls the probability of promoting an element to a higher level.
	P float64
	// contains filtered or unexported fields
}

SkipList is a sorted collection of []byte key/value pairs implemented as a probabilistic skip list.

Header is a sentinel node. Its nexts slice contains the head pointers for each level of the skip list.

MaxLevel is the maximum number of levels in the skip list.

P is the probability used when choosing random heights for new elements (see NewSkipList).

func NewSkipList

func NewSkipList(maxlevel int, p float64) *SkipList

NewSkipList creates and returns a new SkipList.

maxlevel is the maximum height of the skip list. If <= 0, it defaults to 32.

p is the probability that an inserted element will be promoted to the next higher level (geometric distribution). The classic value is 0.5. If p <= 0, it defaults to 0.5.

Higher p values produce taller structures on average; lower values produce flatter ones. 0.5 is generally a good balance.

func (*SkipList) All

func (s *SkipList) All() iter.Seq2[[]byte, []byte]

All returns an iterator that yields all key/value pairs in ascending key order.

It satisfies the iter.Seq2 interface and can be used directly with range:

for key, value := range list.All() {
    ...
}

The iterator is valid only for the current state of the list. Modifying the list during iteration may produce unexpected results.

func (*SkipList) Get

func (s *SkipList) Get(key []byte) []byte

Get returns the value associated with key.

It returns nil if the key does not exist in the skip list. Note: because values are []byte, it is not possible to distinguish between a missing key and a key whose value is nil or empty using Get alone.

func (*SkipList) NewElement

func (s *SkipList) NewElement(key, val []byte, l int) *Element

NewElement creates a new Element with the provided key, value and level. The created element will have forward pointers allocated up to s.MaxLevel.

This is primarily intended for advanced use cases. Most callers should use SkipList.Push instead.

func (*SkipList) Pop

func (s *SkipList) Pop(key []byte) []byte

Pop removes the element with the given key and returns its previous value. If the key does not exist, Pop returns nil and leaves the list unchanged.

func (*SkipList) Push

func (s *SkipList) Push(key, val []byte)

Push inserts the key/value pair into the skip list. If the key already exists, its value is overwritten.

Elements are maintained in ascending order by key using bytes.Compare.