Skip to main content

merge_iterator.go

merge_iterator.go - Overview​

This file defines a MergeIterator that merges multiple iterators into a single iterator, handling duplicate keys and providing methods for navigation and access.

Detailed Documentation​

MergeIterator​

type MergeIterator struct {
	left  node
	right node
	small *node

	curKey  []byte
	reverse bool
}

Purpose: The MergeIterator merges multiple sorted iterators, presenting a single sorted view. It efficiently handles duplicate keys by advancing the iterator with the duplicate.

Fields:

  • left: A node representing the left iterator in the merge.
  • right: A node representing the right iterator in the merge.
  • small: A pointer to the node (either left or right) that currently holds the smallest key.
  • curKey: The current key of the iterator. Used to skip duplicate keys.
  • reverse: A boolean indicating whether the iteration is in reverse order.

node​

type node struct {
	valid bool
	key   []byte
	iter  y.Iterator

	// The two iterators are type asserted from `y.Iterator`, used to inline more function calls.
	// Calling functions on concrete types is much faster (about 25-30%) than calling the
	// interface's function.
	merge  *MergeIterator
	concat *ConcatIterator
}

Purpose: Represents a node in the merge iterator, holding an iterator and its current state.

Fields:

  • valid: Indicates whether the iterator in this node is currently valid.
  • key: The current key of the iterator.
  • iter: The underlying iterator.
  • merge: Type-asserted MergeIterator of iter for performance optimization. Can be nil.
  • concat: Type-asserted ConcatIterator of iter for performance optimization. Can be nil.

(n *node) setIterator​

func (n *node) setIterator(iter y.Iterator)

Purpose: Sets the iterator for a node and performs type assertions for optimization.

Parameters:

  • iter: The iterator to set. Type: y.Iterator

Returns: None

(n *node) setKey​

func (n *node) setKey()

Purpose: Sets the key and validity of the node based on the underlying iterator.

Parameters: None

Returns: None

(n *node) next​

func (n *node) next()

Purpose: Advances the underlying iterator to the next position and updates the node's key and validity.

Parameters: None

Returns: None

(n *node) rewind​

func (n *node) rewind()

Purpose: Rewinds the underlying iterator to the beginning and updates the node's key and validity.

Parameters: None

Returns: None

(n *node) seek​

func (n *node) seek(key []byte)

Purpose: Seeks the underlying iterator to the given key and updates the node's key and validity.

Parameters:

  • key: The key to seek to. Type: []byte

Returns: None

(mi *MergeIterator) fix​

func (mi *MergeIterator) fix()

Purpose: Maintains the invariant that mi.small points to the node with the smallest key. It also handles duplicate keys by advancing the right iterator.

Parameters: None

Returns: None

(mi *MergeIterator) bigger​

func (mi *MergeIterator) bigger() *node

Purpose: Returns a pointer to the node that is not currently considered the smallest.

Parameters: None

Returns:

  • *node: Pointer to the bigger node (not the small node).

(mi *MergeIterator) swapSmall​

func (mi *MergeIterator) swapSmall()

Purpose: Swaps the small pointer to point to the other node.

Parameters: None

Returns: None

(mi *MergeIterator) Next​

func (mi *MergeIterator) Next()

Purpose: Advances the iterator to the next valid key, skipping duplicates.

Parameters: None

Returns: None

(mi *MergeIterator) setCurrent​

func (mi *MergeIterator) setCurrent()

Purpose: Sets the current key (mi.curKey) to the key of the small node.

Parameters: None

Returns: None

(mi *MergeIterator) Rewind​

func (mi *MergeIterator) Rewind()

Purpose: Rewinds both underlying iterators and sets the current key to the smallest key.

Parameters: None

Returns: None

(mi *MergeIterator) Seek​

func (mi *MergeIterator) Seek(key []byte)

Purpose: Seeks both underlying iterators to the given key and sets the current key to the smallest key.

Parameters:

  • key: The key to seek to. Type: []byte

Returns: None

(mi *MergeIterator) Valid​

func (mi *MergeIterator) Valid() bool

Purpose: Returns whether the iterator is currently valid (i.e., not at the end).

Parameters: None

Returns:

  • bool: True if the iterator is valid, false otherwise.

(mi *MergeIterator) Key​

func (mi *MergeIterator) Key() []byte

Purpose: Returns the key of the current element.

Parameters: None

Returns:

  • []byte: The key of the current element.

(mi *MergeIterator) Value​

func (mi *MergeIterator) Value() y.ValueStruct

Purpose: Returns the value of the current element.

Parameters: None

Returns:

  • y.ValueStruct: The value of the current element.

(mi *MergeIterator) Close​

func (mi *MergeIterator) Close() error

Purpose: Closes both underlying iterators.

Parameters: None

Returns:

  • error: An error if either of the underlying iterators returns an error during closing.

NewMergeIterator​

func NewMergeIterator(iters []y.Iterator, reverse bool) y.Iterator

Purpose: Creates a new merge iterator from a slice of iterators. If the slice contains 0 or 1 iterators, it returns nil or the single iterator respectively. If the slice contains 2 iterators, it creates a MergeIterator with those two iterators. If the slice contains more than 2 iterators, it recursively merges the first half with the second half.

Parameters:

  • iters: A slice of iterators to merge. Type: []y.Iterator
  • reverse: A boolean indicating whether the iteration should be in reverse order.

Returns:

  • y.Iterator: A new MergeIterator that merges the given iterators, or nil if iters is empty, or the iterator if there is only one iterator.

Code Examples​

None

Getting Started Relevance​