palm

Documentation

Overview

Package palm implements parallel architecture-friendly latch-free modifications (PALM). Details can be found here:

http://cs.unc.edu/~sewall/palm.pdf

The primary purpose of the tree is to efficiently batch operations in such a way that locks are not required. This is most beneficial for in-memory indices. Otherwise, the operations have typical B-tree time complexities.

You primarily see the benefits of multithreading in availability and bulk operations.

Benchmarks:

BenchmarkReadAndWrites-8 1000 1543648 ns/op BenchmarkBulkAdd-8 1000 1705673 ns/op BenchmarkBulkAddToExisting-8 100 70056512 ns/op BenchmarkGet-8 100000 17128 ns/op BenchmarkBulkGet-8 3000 507249 ns/op

Index

• type BTree
  • func New(ary uint64) BTree
• type Key
• type Keys

Types

type BTree

type BTree interface {
	// Insert will insert the provided keys into the tree.
	Insert(...Key)
	// Get will return a key matching the associated provided
	// key if it exists.
	Get(...Key) Keys
	// Len returns the number of items in the tree.
	Len() uint64
	// Dispose will clean up any resources used by this tree.  This
	// must be called to prevent a memory leak.
	Dispose()
}

BTree is the interface returned from this package's constructor.

func New

func New(ary uint64) BTree

New will allocate, initialize, and return a new B-Tree based on PALM principles. This type of tree is suited for in-memory indices in a multi-threaded environment.

type Key

type Key interface {
	// Compare should return an int indicating how this key relates
	// to the provided key.  -1 will indicate less than, 0 will indicate
	// equality, and 1 will indicate greater than.  Duplicate keys
	// are allowed, but duplicate IDs are not.
	Compare(skip.Entry) int
}

Key defines items that can be inserted into or searched for in the tree.

type Keys

type Keys []Key

Keys is a typed list of Key interfaces.