gomapllrb

README

GoMapLLRB [Left-leaning red-black tree in Go]

GoMapLLRB is a Go package that implements an in-memory key/value store using LLRB algorithm. LLRB(Left-Leaning Red-Black) is a self-balancing binary search tree that keeps the keys in order, allowing ordered iteration and finding the nearest keys.

This is a GoLang version of the C implementation in qLibc library.

GoMapLLRB vs Built-in map

	GoMapLLRB	Built-in map
Data structure	Binary Tree	Hash Table
Iteration Order	Ordered	Random
Find nearest key	Yes	No
Performance	O(log n)	O(1)
Memory overhead	O(n)	O(n)

Usages

Simple Example

import "github.com/wolkykim/gomapllrb"

t := gomapllrb.New[string]()
t.Put("foo", "Hello World")
fmt.Println(t.Get("foo"))
t.Delete("key")

[Output]
Hello World

[Play the code]

Other getter methods: Exist(), Min(), Max(), Bigger(), Smaller(), EqualOrBigger(), EqualOrSmaller(), ... See API documents for details.

Iteration

t := New[int]()
for _, k := range []int{7, 1, 3, 9, 5} {
    t.Put(k, k*10)
}

for it := t.Iter(); it.Next(); {
    fmt.Printf("%d=%d ", it.Key(), it.Val())
}

for it := t.Range(3, 8); it.Next(); {
    fmt.Printf("%d:%d ", it.Key(), it.Val())
}

[Output]
1=10 3=30 5=50 7=70 9=90 3:30 5:50 7:70

[Play the code]

Students on DSA course

fmt.Println(t, t.Stats())

[Output]
    ┌──[9]
┌───7
│   └──[5]
3
└───1
 Variant:LLRB234, Put:5, Delete:0, Get:0, Rotate:0.80, Flip:0.20

[Play the code]

Performance 2-3-4 LLRB Vs. 2-3 LLRB

For anyone curious, here's the performance test result between 2-3-4 LLRB and 2-3 LLRB. Tested on 2021 Apple M1 Pro 10-core MacBook. GoMapLLRB supports 2-3-4 and 2-3 LLRB and ships by default to balance the tree structure in the 2-3-4 variant.

	2-3-4 LLRB	2-3 LLRB		2-3-4 LLRB	2-3 LLRB		2-3-4 LLRB	2-3 LLRB
Workload	1 million	1 million		3 million	3 million		10 million	10 million
Insert	602ms	654ms		2838ms	3185ms		13065ms	13412ms
Lookup	376ms	391ms		1860ms	1869ms		9480ms	10647ms
Delete	693ms	702ms		3201ms	3166ms		14199ms	15594ms
Rotations(Ins)	1.08	1.19		1.08	1.19		1.08	1.19
Rotations(Del)	16.46	19.45		17.43	21.77		18.64	23.53
Flips(Ins)	0.57	0.75		0.57	0.75		0.57	0.75
Flips(Del)	3.31	15.33		3.44	17.42		3.58	18.45

Copyright

GoMapLLRG is published under 2-clause BSD license known as Simplified BSD License. Please refer the LICENSE document included in the package for more details.

Wanna thank me? Give it a star to this project if it helps. That'll do it! https://github.com/wolkykim/GoMapLLRB

Documentation

Overview

Package gomapllrb implements an in-memory key/value store using LLRB algorithm. LLRB (Left-Leaning Red-Black) is a self-balancing binary search tree that stores the keys in order which allows ordered iteration and find nearest keys.

Copyright (c) 2023, Seungyoung Kim https://github.com/wolkykim/GoMapLLRB

Index

• Constants
• func IsLess[K constraints.Ordered](a, b K) bool
• type Comparator
• type Iter
  • func (it *Iter[K]) Key() K
  • func (it *Iter[K]) Next() bool
  • func (it *Iter[K]) Val() interface{}
• type Node
• type PerfStats
• type Stats
  • func (s Stats) String() string
• type Tree
  • func New[K constraints.Ordered]() *Tree[K]
  • func (tree *Tree[K]) Bigger(name K) (K, interface{}, bool)
  • func (tree *Tree[K]) Check() error
  • func (tree *Tree[K]) Clear()
  • func (tree *Tree[K]) Delete(name K) bool
  • func (tree *Tree[K]) EqualOrBigger(name K) (K, interface{}, bool)
  • func (tree *Tree[K]) EqualOrSmaller(name K) (K, interface{}, bool)
  • func (tree *Tree[K]) Exist(name K) bool
  • func (tree *Tree[K]) Get(name K) interface{}
  • func (tree *Tree[K]) Iter() *Iter[K]
  • func (tree *Tree[K]) Len() int
  • func (tree *Tree[K]) Map() map[K]interface{}
  • func (tree *Tree[K]) Max() (K, interface{}, bool)
  • func (tree *Tree[K]) Min() (K, interface{}, bool)
  • func (tree *Tree[K]) Put(name K, data interface{})
  • func (tree *Tree[K]) Range(start, end K) *Iter[K]
  • func (tree *Tree[K]) ResetStats()
  • func (tree *Tree[K]) SetLess(fn Comparator[K])
  • func (tree *Tree[K]) Smaller(name K) (K, interface{}, bool)
  • func (tree *Tree[K]) Stats() Stats
  • func (tree *Tree[K]) String() string

Constants

const (
	// LLRB234 sets the tree management property and algorithm.
	LLRB234 = true // true: 2-3-4 varian(default), false: 2-3 variant
)

Functions

func IsLess

func IsLess[K constraints.Ordered](a, b K) bool

IsLess is the default comparator.

Types

type Comparator

type Comparator[K constraints.Ordered] func(a, b K) bool

Comparator is the type.

type Iter

type Iter[K constraints.Ordered] struct {
	// contains filtered or unexported fields
}

Iter is a iterator object.

func (*Iter[K]) Key

func (it *Iter[K]) Key() K

Key returns the key name.

func (*Iter[K]) Next

func (it *Iter[K]) Next() bool

Next travels the keys in the tree.

func (*Iter[K]) Val

func (it *Iter[K]) Val() interface{}

Val returns the value data.

type Node

type Node[K constraints.Ordered] struct {
	// contains filtered or unexported fields
}

Node is like an apple on the apple trees.

type PerfStats

type PerfStats struct {
	Flip   uint64
	Rotate struct {
		Sum   uint64
		Left  uint64
		Right uint64
	}
}

PerfStats are global stats for debugging purpose.

type Stats

type Stats struct {
	Put struct {
		Sum    uint64
		New    uint64
		Update uint64
	}
	Delete struct {
		Sum      uint64
		Deleted  uint64
		NotFound uint64
	}
	Get struct {
		Sum      uint64
		Found    uint64
		NotFound uint64
	}
	Perf PerfStats
}

Stats provides usage statistics accessible via Stats() method.

func (Stats) String

func (s Stats) String() string

String returns a statistics data in a string.

type Tree

type Tree[K constraints.Ordered] struct {
	// contains filtered or unexported fields
}

Tree is the glorious tree struct.

func New

func New[K constraints.Ordered]() *Tree[K]

New creates a new tree.

func (*Tree[K]) Bigger

func (tree *Tree[K]) Bigger(name K) (K, interface{}, bool)

Bigger finds the next key bigger than given ken.

func (*Tree[K]) Check

func (tree *Tree[K]) Check() error

Check checks that the invariants of the red-black tree are satisfied.

Root property:  The root is black.
Red property:   If a node is red, then both its children are black.
Black property: For each node, all simple paths from the node to
                descendant leaves contain the same number of black nodes.
LLRB property:  3-nodes always lean to the left and 4-nodes are balanced.

func (*Tree[K]) Clear

func (tree *Tree[K]) Clear()

Clear empties the tree without resetting the statistic metrics.

func (*Tree[K]) Delete

func (tree *Tree[K]) Delete(name K) bool

Delete deletes the key. It returns an error if the key is not found.

func (*Tree[K]) EqualOrBigger

func (tree *Tree[K]) EqualOrBigger(name K) (K, interface{}, bool)

EqualOrBigger finds a matching key or the next bigger key.

func (*Tree[K]) EqualOrSmaller

func (tree *Tree[K]) EqualOrSmaller(name K) (K, interface{}, bool)

EqualOrSmaller finds a matching key or the next smaller key.

func (*Tree[K]) Exist

func (tree *Tree[K]) Exist(name K) bool

Exist checks if the key exists.

func (*Tree[K]) Get

func (tree *Tree[K]) Get(name K) interface{}

Get returns the value of the key. If key is not found, it returns Nil. When Nil value is expected as a actual value, use Exist() instead.

func (*Tree[K]) Iter

func (tree *Tree[K]) Iter() *Iter[K]

Iter returns an iterator.

func (*Tree[K]) Len

func (tree *Tree[K]) Len() int

Len returns the number of object stored.

func (*Tree[K]) Map

func (tree *Tree[K]) Map() map[K]interface{}

Map returns the tree in a map

func (*Tree[K]) Max

func (tree *Tree[K]) Max() (K, interface{}, bool)

Max returns a max key and value.

func (*Tree[K]) Min

func (tree *Tree[K]) Min() (K, interface{}, bool)

Min returns a min key and value.

func (*Tree[K]) Put

func (tree *Tree[K]) Put(name K, data interface{})

Put inserts a new key or replaces old if the same key is found.

func (*Tree[K]) Range

func (tree *Tree[K]) Range(start, end K) *Iter[K]

Range returns a ranged iterator.

func (*Tree[K]) ResetStats

func (tree *Tree[K]) ResetStats()

ResetStats resets all the satistics metrics.

func (*Tree[K]) SetLess

func (tree *Tree[K]) SetLess(fn Comparator[K])

SetLess sets a user comparator function.

func myLess[K constraints.Ordered](a, b K) bool {
  // return true if a < b, or false
}

func (*Tree[K]) Smaller

func (tree *Tree[K]) Smaller(name K) (K, interface{}, bool)

Smaller finds the next key bigger than given ken.

func (*Tree[K]) Stats

func (tree *Tree[K]) Stats() Stats

Stats returns a copy of the statistics metrics.

func (*Tree[K]) String

func (tree *Tree[K]) String() string

String returns a pretty drawing of the tree structure.

┌── 6
|   └──[5]
4
│   ┌── 3
└──[2]
    └── 1