net.metanotion.io.block.index

Class BSkipList<K extends Comparable<? super K>,V>

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 Summary

Fields

Modifier and Type	Field and Description
BlockFile	bf Reference to the BlockFile
int	firstLevelPage Page number of the first level
int	firstSpanPage Page number of the first span
(package private) HashMap<Integer,SkipLevels<K,V>>	levelHash
int	skipPage Page number of this skiplist header
(package private) HashMap<Integer,BSkipSpan<K,V>>	spanHash

Fields inherited from class net.metanotion.util.skiplist.SkipList

first, P, rng, size, stack

Constructor Summary

Constructors

Constructor and Description
BSkipList(int spanSize, BlockFile bf, int skipPage, Serializer<K> key, Serializer<V> val) Create a BSkipList from a BlockFile.
BSkipList(int spanSize, BlockFile bf, int skipPage, Serializer<K> key, Serializer<V> val, boolean fileOnly) Create a BSkipList from a BlockFile.

Method Summary

Modifier and Type	Method and Description
boolean	bslck(boolean fix, boolean isMeta) Run an integrity check on the skiplist and all the levels in it.
void	close() Close this skiplist and flush all data to disk.
void	delete() Delete this skiplist and free all its pages.
SkipIterator<K,V>	find(K key) Find the entry with the given key.
void	flush() Flush all data to disk.
static void	init(BlockFile bf, int page, int spanSize) Initialize a new skiplist on disk.
SkipIterator<K,V>	iterator() Get an iterator over all entries in this skiplist.
int	maxLevels() Calculate the maximum number of levels for this skiplist.
String	toString() Get a string representation of this skiplist.

Methods inherited from class net.metanotion.util.skiplist.SkipList

addItem, balance, delItem, generateColHeight, get, put, remove, size

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

bf

public final BlockFile bf

Reference to the BlockFile

firstLevelPage

public int firstLevelPage

Page number of the first level

firstSpanPage

public int firstSpanPage

Page number of the first span

levelHash

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

skipPage

public int skipPage

Page number of this skiplist header

spanHash

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

Constructor Detail

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 BlockFile

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 BlockFile

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 Detail

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.

close

public void close()

Close this skiplist and flush all data to disk.

Specified by:

close in interface Closeable

Specified by:

close in interface AutoCloseable

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

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 search for

Returns:

a SkipIterator pointing to the entry, or end if not found

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>

init

public static void init(BlockFile bf,
                        int page,
                        int spanSize)
                 throws IOException

Initialize a new skiplist on disk.

Parameters:

bf - the BlockFile

page - the page number for the skiplist header

spanSize - the span size to use

Throws:

IOException - if an I/O error occurs

iterator

public SkipIterator<K,V> iterator()

Get an iterator over all entries in this skiplist.

Specified by:

iterator in interface Iterable<V>

Overrides:

iterator in class SkipList<K extends Comparable<? super K>,V>

Returns:

a SkipIterator

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

toString

public String toString()

Get a string representation of this skiplist.

Overrides:

toString in class Object

Returns:

a string representation