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 3000 483140 ns/op BenchmarkSimultaneousReadsAndWrites-8 300 4418123 ns/op BenchmarkBulkAdd-8 300 5569750 ns/op BenchmarkAdd-8 500000 2478 ns/op BenchmarkBulkAddToExisting-8 100 20552674 ns/op BenchmarkGet-8 2000000 629 ns/op BenchmarkBulkGet-8 5000 223249 ns/op BenchmarkDelete-8 500000 2421 ns/op BenchmarkBulkDelete-8 500 2790461 ns/op BenchmarkFindQuery-8 1000000 1166 ns/op BenchmarkExecuteQuery-8 10000 1290732 ns/op

Index

• type BTree
  • func New(bufferSize, ary uint64) BTree

Types

type BTree

type BTree interface {
	// Insert will insert the provided keys into the tree.
	Insert(...common.Comparator)
	// Delete will remove the provided keys from the tree.  If no
	// matching key is found, this is a no-op.
	Delete(...common.Comparator)
	// Get will return a key matching the associated provided
	// key if it exists.
	Get(...common.Comparator) common.Comparators
	// Len returns the number of items in the tree.
	Len() uint64
	// Query will return a list of Comparators that fall within the
	// provided start and stop Comparators.  Start is inclusive while
	// stop is exclusive, ie [start, stop).
	Query(start, stop common.Comparator) common.Comparators
	// 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(bufferSize, 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.