skiplist

README

go-skiplist

Simple skip list for Go.

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

Install

go get github.com/toastsandwich/skiplist

Usage

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).

Optional size limit

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

API

Method	Returns	Notes
Put(key, val)	error	Insert or update
Get(key)	([]byte, error)	Zero allocs on hit
Pop(key)	error	Remove by key
All()	iter.Seq2[[]byte, []byte]	Sorted iteration via range
ForEach(fn)	—	Callback iteration; return false to stop
Len()	int	Current entry count

Exported errors: ErrNilKey, ErrNilVal, ErrKeyNotFound, ErrSkiplistFull.

Not safe for concurrent use.

How Skip Lists Work

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.

Benchmarks (heavy load)

Run on ~1 million elements (Intel Core i7-11800H):

go test -run=^$ -bench=. -benchmem -count=3 -benchtime=1s

Op	ns/op	allocs/op
Put	268	3
Get	244	0
Pop	572	4
PutGetMix	619	3
Iteration	6.3ms	0

• Get, Pop, and PutGetMix run against a preloaded list of 1M elements.
• Iteration = one full traversal over 500k elements.
• Pop benchmark does pop + re-insert to keep size stable.

Get has zero allocations on hits.

License

MIT

Documentation

Overview

Package skiplist is a sorted []byte key/value store.

Put, Get, and Pop are O(log n) on average. Keys sort with bytes.Compare. Not safe for concurrent use.

s := NewSkipList(0, 0) // defaults: max level 32, p 0.5
s.Put([]byte("a"), []byte("1"))
v, _ := s.Get([]byte("a"))
s.Pop([]byte("a"))
for k, v := range s.All() { _ = k; _ = v }

Example

Example demonstrates basic usage of SkipList.

s := NewSkipList(16, 0.5)

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

if v, err := s.Get([]byte("cat")); err == nil {
	fmt.Println("cat ->", string(v))
}

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

• Variables
• func DefaultValues() (int, float64)
• 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) ForEach(do func(key, value []byte) bool)
  • func (s *SkipList) Get(key []byte) ([]byte, error)
  • func (s *SkipList) Len() int
  • func (s *SkipList) NewElement(key, val []byte, l int) *Element
  • func (s *SkipList) Pop(key []byte) error
  • func (s *SkipList) Put(key, val []byte) error

Examples

• Package

Variables

var (
	ErrNilKey       = errors.New("key cannot be nil or zero len slice of byte")
	ErrNilVal       = errors.New("value cannot be nil or zero len slice of byte")
	ErrKeyNotFound  = errors.New("key not found")
	ErrSkiplistFull = errors.New("skip list is full")
)

Functions

func DefaultValues

func DefaultValues() (int, float64)

DefaultValues returns the default max level (32) and probability (0.5).

Types

type Element

type Element struct {
	Key, Value []byte
	Level      int
	// contains filtered or unexported fields
}

Element is one node in the list. Most callers use Put instead.

func (*Element) SetLevel

func (e *Element) SetLevel(l int)

SetLevel sets the node height. Does not update links.

type SkipList

type SkipList struct {
	Header   *Element
	MaxLevel int
	P        float64

	// MaxLen is the max number of entries. 0 means unlimited.
	MaxLen int
	// contains filtered or unexported fields
}

SkipList stores sorted []byte key/value pairs.

func NewSkipList

func NewSkipList(maxlevel int, p float64) *SkipList

NewSkipList creates a list. Pass 0 for either arg to use defaults (32, 0.5).

func (*SkipList) All

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

All iterates key/value pairs in sorted order. Don't modify the list while ranging.

func (*SkipList) ForEach

func (s *SkipList) ForEach(do func(key, value []byte) bool)

ForEach walks all pairs in sorted order. Return false from do to stop early.

func (*SkipList) Get

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

Get returns the value for key. ErrKeyNotFound if missing, ErrNilKey if empty.

func (*SkipList) Len

func (s *SkipList) Len() int

Len returns the number of entries.

func (*SkipList) NewElement

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

NewElement builds a node with level l. Use Put for normal inserts.

func (*SkipList) Pop

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

Pop removes key. ErrKeyNotFound if missing, ErrNilKey if empty.

func (*SkipList) Put

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

Put inserts or updates a key/value pair. ErrNilKey or ErrNilVal on empty input. ErrSkiplistFull if MaxLen is reached.