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(32, 0.5)

s.Put([]byte("user:1"), []byte("Alice"))
val, _ := s.Get([]byte("user:1"))

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

s.Pop([]byte("user:1"))

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

Functions

func DefaultValues

func DefaultValues() (int, float64)

Return default values for maxlevel and p

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 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 level 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) ForEach

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

func (*SkipList) Get

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

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

func (s *SkipList) Len() int

Returns number of elements in a list

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

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

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

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