README
¶
treap
Package treap implements a treap data structure that is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics.
It is a self-organizing and randomized data structure that doesn't require complex operations to to maintain balance. Search, insert, and delete operations are all O(log n). Both mutable and immutable variants are provided. The mutable variant is typically faster since it is able to simply update the treap when modifications are made. However, a mutable treap is not safe for concurrent access without careful use of locking by the caller and care must be taken when iterating since it can change out from under the iterator. The immutable variant works by creating a new version of the treap for all mutations by replacing modified nodes with new nodes that have updated values while sharing all unmodified nodes with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.
Usage
This package is only used internally in the database code and as such is not available for use outside of it.
License
Package treap is licensed under the copyfree ISC License.
Documentation
¶
Overview ¶
Package treap implements a treap data structure that is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics.
It is a self-organizing and randomized data structure that doesn't require complex operations to to maintain balance. Search, insert, and delete operations are all O(log n). Both mutable and immutable variants are provided. The mutable variant is typically faster since it is able to simply update the treap when modifications are made. However, a mutable treap is not safe for concurrent access without careful use of locking by the caller and care must be taken when iterating since it can change out from under the iterator. The immutable variant works by creating a new version of the treap for all mutations by replacing modified nodes with new nodes that have updated values while sharing all unmodified nodes with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.
Index ¶
- type Immutable
- func (t *Immutable) Delete(key []byte) *Immutable
- func (t *Immutable) ForEach(fn func(k, v []byte) bool)
- func (t *Immutable) Get(key []byte) []byte
- func (t *Immutable) Has(key []byte) bool
- func (t *Immutable) Iterator(startKey, limitKey []byte) *Iterator
- func (t *Immutable) Len() int
- func (t *Immutable) Put(key, value []byte) *Immutable
- func (t *Immutable) Size() uint64
- type Iterator
- func (iter *Iterator) First() bool
- func (iter *Iterator) ForceReseek()
- func (iter *Iterator) Key() []byte
- func (iter *Iterator) Last() bool
- func (iter *Iterator) Next() bool
- func (iter *Iterator) Prev() bool
- func (iter *Iterator) Seek(key []byte) bool
- func (iter *Iterator) Valid() bool
- func (iter *Iterator) Value() []byte
- type Mutable
- func (t *Mutable) Delete(key []byte)
- func (t *Mutable) ForEach(fn func(k, v []byte) bool)
- func (t *Mutable) Get(key []byte) []byte
- func (t *Mutable) Has(key []byte) bool
- func (t *Mutable) Iterator(startKey, limitKey []byte) *Iterator
- func (t *Mutable) Len() int
- func (t *Mutable) Put(key, value []byte)
- func (t *Mutable) Reset()
- func (t *Mutable) Size() uint64
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Immutable ¶
type Immutable struct {
// contains filtered or unexported fields
}
Immutable represents a treap data structure which is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics. It is a self-organizing and randomized data structure that doesn't require complex operations to maintain balance. Search, insert, and delete operations are all O(log n). In addition, it provides O(1) snapshots for multi-version concurrency control (MVCC). All operations which result in modifying the treap return a new version of the treap with only the modified nodes updated. All unmodified nodes are shared with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.
func NewImmutable ¶
func NewImmutable() *Immutable
NewImmutable returns a new empty immutable treap ready for use. See the documentation for the Immutable structure for more details.
func (*Immutable) Delete ¶
Delete removes the passed key from the treap and returns the resulting treap if it exists. The original immutable treap is returned if the key does not exist.
func (*Immutable) ForEach ¶
ForEach invokes the passed function with every key/value pair in the treap in ascending order.
func (*Immutable) Get ¶
Get returns the value for the passed key. The function will return nil when the key does not exist.
func (*Immutable) Iterator ¶
Iterator returns a new iterator for the immutable treap. The newly returned iterator is not pointing to a valid item until a call to one of the methods to position it is made. The start key and limit key parameters cause the iterator to be limited to a range of keys. The start key is inclusive and the limit key is exclusive. Either or both can be nil if the functionality is not desired.
func (*Immutable) Size ¶
Size returns a best estimate of the total number of bytes the treap is consuming including all of the fields used to represent the nodes as well as the size of the keys and values. Shared values are not detected, so the returned size assumes each value is pointing to different memory.
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator represents an iterator for forwards and backwards iteration over the contents of a treap (mutable or immutable).
func (*Iterator) First ¶
First moves the iterator to the first key/value pair. When there is only a single key/value pair both First and Last will point to the same pair. Returns false if there are no key/value pairs.
func (*Iterator) ForceReseek ¶
func (iter *Iterator) ForceReseek()
ForceReseek notifies the iterator that the underlying mutable treap has been updated, so the next call to Prev or Next needs to reseek in order to allow the iterator to continue working properly. NOTE: Calling this function when the iterator is associated with an immutable treap has no effect as you would expect.
func (*Iterator) Key ¶
Key returns the key of the current key/value pair or nil when the iterator is exhausted. The caller should not modify the contents of the returned slice.
func (*Iterator) Last ¶
Last moves the iterator to the last key/value pair. When there is only a single key/value pair both First and Last will point to the same pair. Returns false if there are no key/value pairs.
func (*Iterator) Next ¶
Next moves the iterator to the next key/value pair and returns false when the iterator is exhausted. When invoked on a newly created iterator it will position the iterator at the first item.
func (*Iterator) Prev ¶
Prev moves the iterator to the previous key/value pair and returns false when the iterator is exhausted. When invoked on a newly created iterator it will position the iterator at the last item.
func (*Iterator) Seek ¶
Seek moves the iterator to the first key/value pair with a key that is greater than or equal to the given key and returns true if successful.
type Mutable ¶
type Mutable struct {
// contains filtered or unexported fields
}
Mutable represents a treap data structure which is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics. It is a self-organizing and randomized data structure that doesn't require complex operations to maintain balance. Search, insert, and delete operations are all O(log n).
func NewMutable ¶
func NewMutable() *Mutable
NewMutable returns a new empty mutable treap ready for use. See the documentation for the Mutable structure for more details.
func (*Mutable) ForEach ¶
ForEach invokes the passed function with every key/value pair in the treap in ascending order.
func (*Mutable) Get ¶
Get returns the value for the passed key. The function will return nil when the key does not exist.
func (*Mutable) Iterator ¶
Iterator returns a new iterator for the mutable treap. The newly returned iterator is not pointing to a valid item until a call to one of the methods to position it is made. The start key and limit key parameters cause the iterator to be limited to a range of keys. The start key is inclusive and the limit key is exclusive. Either or both can be nil if the functionality is not desired. WARNING: The ForceSeek method must be called on the returned iterator if the treap is mutated. Failure to do so will cause the iterator to return unexpected keys and/or values. For example:
iter := t.Iterator(nil, nil)
for iter.Next() {
if someCondition {
t.Delete(iter.Key())
iter.ForceReseek()
}
}
func (*Mutable) Size ¶
Size returns a best estimate of the total number of bytes the treap is consuming including all of the fields used to represent the nodes as well as the size of the keys and values. Shared values are not detected, so the returned size assumes each value is pointing to different memory.
Source Files