Documentation
¶
Overview ¶
Package skip defines a skiplist datastructure. That is, a data structure that probabilistically determines relationships between keys. By doing so, it becomes easier to program than a binary search tree but maintains similar speeds.
Performance characteristics: Insert: O(log n) Search: O(log n) Delete: O(log n) Space: O(n)
Recently added is the capability to address, insert, and replace an entry by position. This capability is acheived by saving the width of the "gap" between two nodes. Searching for an item by position is very similar to searching by value in that the same basic algorithm is used but we are searching for width instead of value. Because this avoids the overhead associated with Golang interfaces, operations by position are about twice as fast as operations by value. Time complexities listed below.
SearchByPosition: O(log n) InsertByPosition: O(log n)
More information here: http://cglab.ca/~morin/teaching/5408/refs/p90b.pdf
SkipList* is a data structure combining elements of both a skiplist and the bottom half of a Y-fast trie. The idea is that you can quickly search for a sub branch of the skip list and that this branch can fit entirely within cache, thereby improving the performance characteristics over a standard skip list. This also keeps any memcopy operation limited to O(log M) where M is the size of the desired universe.
Performance vs standard skip list. BenchmarkInsert-8 2000000 976 ns/op BenchmarkGet-8 3000000 442 ns/op BenchmarkDelete-8 3000000 426 ns/op BenchmarkPrepend-8 2000000 932 ns/op BenchmarkStarInsert-8 3000000 398 ns/op BenchmarkStarGet-8 5000000 488 ns/op BenchmarkStarDelete-8 3000000 440 ns/op BenchmarkIterStar-8 30000 122984 ns/op BenchmarkStarPrepend-8 3000000 618 ns/op
Index ¶
- type Entries
- type Entry
- type Iterator
- type SkipList
- func (sl *SkipList) ByPosition(position uint64) Entry
- func (sl *SkipList) Delete(keys ...uint64) Entries
- func (sl *SkipList) Get(keys ...uint64) Entries
- func (sl *SkipList) GetWithPosition(key uint64) (Entry, uint64)
- func (sl *SkipList) Insert(entries ...Entry) Entries
- func (sl *SkipList) InsertAtPosition(position uint64, entry Entry)
- func (sl *SkipList) Iter(key uint64) Iterator
- func (sl *SkipList) Len() uint64
- func (sl *SkipList) ReplaceAtPosition(position uint64, entry Entry)
- type SkipListStar
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Entry ¶
type Entry interface {
// Key defines this entry's place in the skip list.
Key() uint64
}
Entry defines items that can be inserted into the skip list. This will also be the type returned from a query.
type Iterator ¶
type Iterator interface {
// Next returns a bool indicating if there is future value
// in the iterator and moves the iterator to that value.
Next() bool
// Value returns an Entry representing the iterator's current
// position. If there is no value, this returns nil.
Value() Entry
// contains filtered or unexported methods
}
Iterator defines an interface that allows a consumer to iterate all results of a query. All values will be visited in-order.
type SkipList ¶
type SkipList struct {
// contains filtered or unexported fields
}
Skip list is a datastructure that probabalistically determines relationships between nodes. This results in a structure that performs similarly to a BST but is much easier to build from a programmatic perspective (no rotations).
func New ¶
func New(ifc interface{}) *SkipList
New will allocate, initialize, and return a new skiplist. The provided parameter should be of type uint and will determine the maximum possible level that will be created to ensure a random and quick distribution of levels. Parameter must be a uint type.
func (*SkipList) ByPosition ¶
ByPosition returns the entry at the given position.
func (*SkipList) Delete ¶
Delete will remove the provided keys from the skiplist and return a list of in-order entries that were deleted. This is a no-op if an associated key could not be found. This is an O(log n) operation.
func (*SkipList) Get ¶
Get will retrieve values associated with the keys provided. If an associated value could not be found, a nil is returned in its place. This is an O(log n) operation.
func (*SkipList) GetWithPosition ¶
GetWithPosition will retrieve the value with the provided key and return the position of that value within the list. Returns nil, 0 if an associated value could not be found.
func (*SkipList) Insert ¶
Insert will insert the provided entries into the list. Returned is a list of entries that were overwritten. This is expected to be an O(log n) operation.
func (*SkipList) InsertAtPosition ¶
InsertAtPosition will insert the provided entry and the provided position. If position is greater than the length of the skiplist, the entry is appended. This method bypasses order checks and checks for duplicates so use with caution.
func (*SkipList) Iter ¶
Iter will return an iterator that can be used to iterate over all the values with a key equal to or greater than the key provided.
func (*SkipList) ReplaceAtPosition ¶
Replace at position will replace the entry at the provided position with the provided entry. If the provided position does not exist, this operation is a no-op.
type SkipListStar ¶
type SkipListStar struct {
// contains filtered or unexported fields
}
SkipList* implements all methods of a standard skip list but attempts to improve performance by ensuring cache locality.
func NewStar ¶
func NewStar(ifc interface{}) *SkipListStar
NewStar will allocate, initialize, and return a new SkipListStar. The Skip* list has an node size defined by the provided interface parameter. This parameter must be a uint type (uint8, uint16, etc).
func (*SkipListStar) Delete ¶
func (ssl *SkipListStar) Delete(keys ...uint64) Entries
Delete will remove the provided keys from the SkipList* and return a list of entries that were deleted.
func (*SkipListStar) Get ¶
func (ssl *SkipListStar) Get(keys ...uint64) Entries
Get will return a list of entries associated with the provided keys. A nil will be returned for any key not found.
func (*SkipListStar) Insert ¶
func (ssl *SkipListStar) Insert(entries ...Entry) Entries
Insert will insert the provded entries into the SkipList*. Any existing entry with a matching key will be overwritten. The returned list of a list of entries that were overwritten, in order. A nil will be in the in-order position for any non-overwritten entries.
func (*SkipListStar) Iter ¶
func (ssl *SkipListStar) Iter(key uint64) Iterator
Iter will return an iterator that will visit every value equal to or greater than the provided key.
func (*SkipListStar) Len ¶
func (ssl *SkipListStar) Len() uint64
Len returns the number of items in the SkipList*.
Source Files