plus

Documentation

Overview

Package btree/plus implements the ubiquitous B+ tree. As of this writing, the tree is not quite finished. The delete-node merge functionaly needs to be added. There are also some performance improvements that can be made, with some possible concurrency mechanisms.

This is a mutable b-tree so it is not threadsafe.

Performance characteristics: Space: O(n) Insert: O(log n) Search: O(log n)

BenchmarkIteration-8 10000 109347 ns/op BenchmarkInsert-8 3000000 608 ns/op BenchmarkGet-8 3000000 627 ns/op

Index

• type Iterator
• type Key
• type Keys

Types

type Iterator

type Iterator interface {
	// Next will move the iterator to the next position and return
	// a bool indicating if there is a value.
	Next() bool
	// Value returns a Key at the associated iterator position.  Returns
	// nil if the iterator is exhausted or has never been nexted.
	Value() Key
	// contains filtered or unexported methods
}

Iterator will be called with matching keys until either false is returned or we run out of keys to iterate.

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(Key) int
}

type Keys

type Keys []Key

Keys is a typed list of Key interfaces.