java.lang.Object
net.metanotion.util.skiplist.SkipList<K,V>
net.metanotion.io.block.index.BSkipList<K,V>
Type Parameters:
K - type of keys maintained by this skip list
V - type of mapped values
All Implemented Interfaces:
Closeable, Flushable, AutoCloseable, Iterable<V>
public class BSkipList<K extends Comparable<? super K>, V>extends SkipList<K,V> implements Closeable
On-disk SkipList implementation for persistent key-value storage.

Provides efficient indexed storage with logarithmic search performance. Supports multiple spans and levels for scalable data organization.

On-disk format:

   Magic number (long)
   first span page (unsigned int)
   first level page (unsigned int)
   size (unsigned int)
   spans (unsigned int)
   levels (unsigned int)

Always fits on one page.

  • Field Details

    • MAGIC

      private static final long MAGIC
      Written first in a persisted list, so a wrong file is recognised
      See Also:

    • firstSpanPage

      public int firstSpanPage
      Page number of the first span

    • firstLevelPage

      public int firstLevelPage
      Page number of the first level

    • skipPage

      public int skipPage
      Page number of this skiplist header

    • bf

      public final BlockFile bf
      Reference to the BlockFile

    • isClosed

      private boolean isClosed
      Whether this skiplist is closed

    • spanHash

      final HashMap<Integer, BSkipSpan<K extends Comparable<? super K>, V>> spanHash
      Span cache

    • levelHash

      final HashMap<Integer, SkipLevels<K extends Comparable<? super K>, V>> levelHash
      Level cache

    • fileOnly

      private final boolean fileOnly
      True when the list is stored entirely on disk.

  • Constructor Details

    • BSkipList

      public BSkipList(int spanSize, BlockFile bf, int skipPage, Serializer<K> key, Serializer<V> val) throws IOException
      Create a BSkipList from a BlockFile.
      Parameters:
      spanSize - the size of spans
      bf - the backing file; the skiplist header and spans are read from and written to its pages
      skipPage - the page number of this skiplist
      key - the key serializer
      val - the value serializer
      Throws:
      IOException - if an I/O error occurs

    • BSkipList

      public BSkipList(int spanSize, BlockFile bf, int skipPage, Serializer<K> key, Serializer<V> val, boolean fileOnly) throws IOException
      Create a BSkipList from a BlockFile.
      Parameters:
      spanSize - the size of spans
      bf - the backing file; the skiplist header and spans are read from and written to its pages
      skipPage - the page number of this skiplist
      key - the key serializer
      val - the value serializer
      fileOnly - if true, only read from file (no caching)
      Throws:
      IOException - if an I/O error occurs

  • Method Details

    • close

      public void close()
      Close this skiplist and flush all data to disk.
      Specified by:
      close in interface AutoCloseable
      Specified by:
      close in interface Closeable

    • flush

      public void flush()
      Flush all data to disk.
      Specified by:
      flush in interface Flushable
      Overrides:
      flush in class SkipList<K extends Comparable<? super K>, V>

    • delete

      public void delete() throws IOException
      Delete this skiplist and free all its pages. Must be open (do not call close() first).
      Throws:
      IOException - if an I/O error occurs

    • init

      public static void init(BlockFile bf, int page, int spanSize) throws IOException
      Initialize a new skiplist on disk.
      Parameters:
      bf - the backing file; the skiplist header and spans are read from and written to its pages
      page - the page number for the skiplist header
      spanSize - the span size to use
      Throws:
      IOException - if an I/O error occurs

    • maxLevels

      public int maxLevels()
      Calculate the maximum number of levels for this skiplist.
      Overrides:
      maxLevels in class SkipList<K extends Comparable<? super K>, V>
      Returns:
      log2(span count), minimum 4

    • iterator

      public SkipIterator<K,V> iterator()
      Get an iterator over all entries in this skiplist.
      Specified by:
      iterator in interface Iterable<K extends Comparable<? super K>>
      Overrides:
      iterator in class SkipList<K extends Comparable<? super K>, V>
      Returns:
      a cached iterator when fileOnly is false, otherwise an IBSkipIterator that reads spans from disk

    • find

      public SkipIterator<K,V> find(K key)
      Find the entry with the given key.
      Overrides:
      find in class SkipList<K extends Comparable<? super K>, V>
      Parameters:
      key - the key to look up
      Returns:
      a SkipIterator pointing to the entry, or end if not found

    • bslck

      public boolean bslck(boolean fix, boolean isMeta)
      Run an integrity check on the skiplist and all the levels in it.
      Parameters:
      fix - if true, attempt to fix any corruption found
      isMeta - if true, this is a metaindex skiplist
      Returns:
      true if the levels were modified.

    • toString

      public String toString()
      Get a string representation of this skiplist.
      Overrides:
      toString in class Object
      Returns:
      a string representation