skiplist

Simple skip list for Go.

Sorted []byte key/value store with expected O(log n) operations.

go get github.com/toastsandwich/skiplist

import "github.com/toastsandwich/skiplist"

s := skiplist.NewSkipList(0, 0) // defaults: max level 32, p 0.5

if err := s.Put([]byte("user:1"), []byte("Alice")); err != nil {
    // handle ErrNilKey, ErrNilVal, or ErrSkiplistFull
}

val, err := s.Get([]byte("user:1"))
if err == skiplist.ErrKeyNotFound {
    // missing key
}

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

s.ForEach(func(k, v []byte) bool {
    return true // return false to stop early
})

if err := s.Pop([]byte("user:1")); err != nil {
    // handle ErrKeyNotFound or ErrNilKey
}

n := s.Len() // O(1) entry count

Pass 0 for either NewSkipList argument to use defaults. DefaultValues() returns those defaults explicitly: (32, 0.5).

Set MaxLen on the list to cap how many distinct keys it holds. 0 means unlimited. Updates to existing keys still succeed when full; only new inserts return ErrSkiplistFull.

s := skiplist.NewSkipList(32, 0.5)
s.MaxLen = 1000

Exported errors: ErrNilKey, ErrNilVal, ErrKeyNotFound, ErrSkiplistFull.

Not safe for concurrent use.

Use SyncSkipList when multiple goroutines hit the same map. It wraps the same logic with an RWMutex — many readers, one writer at a time.

s := skiplist.NewSyncSkipList(0, 0)

if err := s.Put([]byte("user:1"), []byte("Alice")); err != nil {
    // handle error
}

val, err := s.Get([]byte("user:1"))

for k, v := range s.All() {
    // sorted order; holds a read lock for the whole scan
    // do not call Put, Pop, or Get from this loop
    _ = k
    _ = v
}

if err := s.Pop([]byte("user:1")); err != nil {
    // handle error
}

n := s.Len() // int64

Ownership: Put takes the key and value slices. Do not reuse or mutate them after the call.

Do not call Put, Pop, Get, or Reset from inside All(). Those methods take the same mutex and will deadlock. Copy k and v if you keep them after the loop.

A skip list is a sorted linked list with extra "express lane" layers on top.

Level 2: HEAD ----------------------> [50] ------------> NIL
Level 1: HEAD ----------> [20] --> [50] --> [80] --> NIL
Level 0: HEAD --> [10] --> [20] --> [50] --> [80] --> NIL

• Every element lives on level 0.
• On insert, a node is randomly assigned a height. With the default p=0.5:
  • ~50% stay at level 0
  • ~25% reach level 1
  • ~12.5% reach level 2, and so on
• Search starts at the highest level, skips forward while keys are smaller, then drops down levels.
• Higher levels act as shortcuts, giving expected O(log n) performance for put, get, and delete.

# SkipList
go test -run=^$ -bench='BenchmarkSkipList' -benchmem -count=3 -benchtime=1s

# SyncSkipList
go test -run=^$ -bench='BenchmarkSyncSkipList' -benchmem -count=3 -benchtime=1s

Notes for both:

• Get, Pop, and PutGetMix run against a preloaded list of 1M elements.
• Pop benchmark does pop + re-insert to keep size stable.

Get has zero allocations on hits for both types.

Three-way comparison of concurrent skip list implementations on Apple M2 (benchtime=1s, count=3). All use []byte keys (key-NNNNNNNN). MauriceGit is wrapped with sync.RWMutex; fast-skiplist uses its built-in mutex.

Head-to-head under parallel load: 100K preloaded keys (read-only) and 10K keys with mixed 33% Put / 33% Get / 33% Delete+reinsert.

MIT