net.metanotion.io.block.index

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

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(): 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 Summary

Fields inherited from class net.metanotion.io.block.index.BSkipSpan

bf, CONT_HEADER_LEN, HEADER_LEN, isKilled, keySer, MAGIC, nextPage, overflowPage, page, prevPage, spanSize, valSer

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

keys, MAX_SIZE, next, nKeys, prev, vals

Constructor Summary

Constructors

Constructor and Description
IBSkipSpan(BlockFile bf, BSkipList<K,V> bsl, int spanPage, Serializer<K> key, Serializer<V> val)

Method Summary

Modifier and Type	Method and Description
K	firstKey() Does not call super, we always store first key here
void	flush() Flush to disk and null out in-memory keys and values, saving only the first key
V	get(K key) Linear search if in file, Binary search if in memory
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.
protected void	loadData() I2P - second half of load() Load the whole span's keys and values into memory
SkipSpan<K,V>	newInstance(SkipList<K,V> sl) Create a new instance of this span type.
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.
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.
(package private) void	seekAndLoadData() Seek to the start of the span and load the data Package private so BSkipIterator can call it

Methods inherited from class net.metanotion.io.block.index.BSkipSpan

init, killInstance, loadData, loadInit, lostEntries, toString

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

getEnd, print

Methods inherited from class java.lang.Object

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

Constructor Detail

IBSkipSpan

public IBSkipSpan(BlockFile bf,
                  BSkipList<K,V> bsl,
                  int spanPage,
                  Serializer<K> key,
                  Serializer<V> val)
           throws IOException

Throws:

IOException

Method Detail

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

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>

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

Returns:

the value, or null if not found

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

search - search parameters and results

Returns:

the SkipSpan containing the key

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

newInstance

public SkipSpan<K,V> newInstance(SkipList<K,V> sl)

Description copied from class: BSkipSpan

Create a new instance of this span type.

Overrides:

newInstance in class BSkipSpan<K extends Comparable<? super K>,V>

Parameters:

sl - the SkipList to create the span for

Returns:

a new SkipSpan instance

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

val - the value

sl - the SkipList

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 to remove

sl - the SkipList

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.

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