intervalradix

README

Interval Radix

Interval radix tree with byte slice keys optimized for point query read performance.

tree := intvradix.New[int]()
tree.Insert([]byte(`alpha`), []byte(`bravo`), 100)
tree.Insert([]byte(`bravo`), []byte(`charlie`), 200)
c := tree.Insert([]byte(`bravo`), []byte(`delta`), 300)

items := tree.Find([]byte(`bravo`))  // [200, 300]
items = tree.Find([]byte(`charlie`)) // [300]

items = tree.FindAny([]byte(`alpha`), []byte(`bravo`), []byte(`charlie`)) // [100, 200, 300]

c.Remove()

items = tree.Find([]byte(`bravo`))   // [200]
items = tree.Find([]byte(`charlie`)) // []

Documentation

Index

• type Interval
  • func (i *Interval[V]) Remove()
• type Tree
  • func New[V any]() *Tree[V]
  • func (t *Tree[V]) Find(k []byte) (vals []V)
  • func (t *Tree[V]) FindAny(keys ...[]byte) (vals []V)
  • func (t *Tree[V]) Insert(start, end []byte, val V) (i *Interval[V])

Types

type Interval

type Interval[V any] struct {
	// contains filtered or unexported fields
}

Interval represnts an interval inserted into the tree.

func (*Interval[V]) Remove

func (i *Interval[V]) Remove()

Remove is the only way to remove items from the tree.

type Tree

type Tree[V any] struct {
	// contains filtered or unexported fields
}

Tree is a thread safe interval radix tree.

func New

func New[V any]() *Tree[V]

New returns a new interval radix tree.

func (*Tree[V]) Find

func (t *Tree[V]) Find(k []byte) (vals []V)

Find returns value of all intervals intersecting point key.

func (*Tree[V]) FindAny

func (t *Tree[V]) FindAny(keys ...[]byte) (vals []V)

FindAny returns value of all intervals intersecting any point in keys (no dupes).

func (*Tree[V]) Insert

func (t *Tree[V]) Insert(start, end []byte, val V) (i *Interval[V])

Insert makes the value available between interval [start, end). Exact matches on end are excluded.