java.lang.Object
net.metanotion.util.skiplist.SkipSpan<K,V>
net.metanotion.io.block.index.BSkipSpan<K,V>
net.metanotion.io.block.index.IBSkipSpan<K,V>
Type Parameters:
K - type of keys maintained by this skip span
V - type of values stored in this skip span
All Implemented Interfaces:
Flushable
public class IBSkipSpan<K extends Comparable<? super K>, V>extends BSkipSpan<K,V>
Memory-efficient SkipList span implementation (I2P version).

Stores only first key in memory to reduce memory usage. Loads keys and values from disk on-demand during operations.

Comparison with BSkipSpan:

  • BSkipSpan stores all keys and values in-memory, backed by file
  • IBSkipSpan stores only first key, and no values, in-memory

For get(): performs linear search through span in file and loads only found value (super() does binary search in-memory).

For put() or remove(K, SkipList): loads all keys and values for span from file, makes modification, flushes out keys and values, and nulls out keys and values in-memory.

Recommended span size is 16.

  • Field Details

    • firstKey

      private K extends Comparable<? super K> firstKey
      Smallest key held in this span.

  • Constructor Details

    • IBSkipSpan

      private IBSkipSpan(BlockFile bf, BSkipList<K,V> bsl)
      Recreates a span from the file.
      Parameters:
      bf - the block file
      bsl - the B-skip list

    • IBSkipSpan

      public IBSkipSpan(BlockFile bf, BSkipList<K,V> bsl, int spanPage, Serializer<K> key, Serializer<V> val) throws IOException
      Opens the span on the given page and chains the remaining span pages of the list.
      Parameters:
      bf - the block file
      bsl - the B-skip list
      spanPage - page number of the span
      key - key serializer
      val - value serializer
      Throws:
      IOException - on I/O error

  • Method Details

    • newInstance

      public SkipSpan<K,V> newInstance(SkipList<K,V> sl)
      Create a new span instance for a page split.
      Overrides:
      newInstance in class BSkipSpan<K extends Comparable<? super K>, V>
      Parameters:
      sl - the parent skip list
      Returns:
      the new span

    • flush

      public void flush()
      Flush to disk and null out in-memory keys and values, saving only the first key
      Specified by:
      flush in interface Flushable
      Overrides:
      flush in class BSkipSpan<K extends Comparable<? super K>, V>

    • loadData

      protected void loadData() throws IOException
      I2P - second half of load() Load the whole span's keys and values into memory
      Overrides:
      loadData in class BSkipSpan<K extends Comparable<? super K>, V>
      Throws:
      IOException - if an I/O error occurs

    • loadFirstKey

      private void loadFirstKey() throws IOException
      Must already be seeked to the end of the span header via loadInit() or seekData()
      Throws:
      IOException - if the span's data pages cannot be read

    • seekData

      private void seekData() throws IOException
      Seek past the span header
      Throws:
      IOException - if the span was killed or its magic number is wrong

    • seekAndLoadData

      void seekAndLoadData() throws IOException
      Seek to the start of the span and load the data Package private so BSkipIterator can call it
      Throws:
      IOException - if the span was killed, its magic is wrong, or a record page cannot be read

    • getData

      private V getData(K key) throws IOException
      Linear search through the span in the file for the value.
      Parameters:
      key - the key to search for
      Returns:
      the value stored under key, or null if not found
      Throws:
      IOException - if the span was killed, its magic is wrong, or a record page cannot be read

    • repair

      private void repair()
      Nothing to repair in a B-skip span.

    • firstKey

      public K firstKey()
      Does not call super, we always store first key here
      Overrides:
      firstKey in class SkipSpan<K extends Comparable<? super K>, V>
      Returns:
      the first key, or null if empty

    • getSpan

      public SkipSpan<K,V> getSpan(K key, int[] search)
      Load whole span from file, do the operation, flush out, then null out in-memory data again. This is called only via SkipList.find()
      Overrides:
      getSpan in class SkipSpan<K extends Comparable<? super K>, V>
      Parameters:
      key - the key to locate, compared using its natural ordering
      search - search parameters and results
      Returns:
      the span carrying the matching key, with search[0] set to its index, or the empty span if the key is absent

    • get

      public V get(K key)
      Linear search if in file, Binary search if in memory
      Overrides:
      get in class SkipSpan<K extends Comparable<? super K>, V>
      Parameters:
      key - the key whose associated value is wanted
      Returns:
      the value, or null if not found

    • put

      public SkipSpan<K,V> put(K key, V val, SkipList<K,V> sl)
      Load whole span from file, do the operation, flush out, then null out in-memory data again.
      Overrides:
      put in class SkipSpan<K extends Comparable<? super K>, V>
      Parameters:
      key - the key to store the value under
      val - the value
      sl - the list to bump and split
      Returns:
      the new span if it caused a split, else null if it went in this span

    • remove

      public Object[] remove(K key, SkipList<K,V> sl)
      Load whole span from file, do the operation, flush out, then null out in-memory data again.
      Overrides:
      remove in class SkipSpan<K extends Comparable<? super K>, V>
      Parameters:
      key - the key whose entry is to be deleted
      sl - the list to shrink if this span empties out
      Returns:
      An array of two objects or null. rv[0] is the removed object. rv[1] is the deleted SkipSpan if the removed object was the last in the SkipSpan. rv is null if no object was removed.