org.apache.directory.mavibot.btree

Interface BTree<K,V>

Type Parameters:

K - The Key type

V - The Value type

All Known Implementing Classes:

AbstractBTree, InMemoryBTree, PersistedBTree

public interface BTree<K,V>

A B-tree interface, to be implemented by the PersistedBTree or the InMemoryBTree

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	ALLOW_DUPLICATES The B-tree allows duplicate values
static int	DEFAULT_PAGE_SIZE Default page size (number of entries per node)
static long	DEFAULT_READ_TIMEOUT Define a default delay for a read transaction.
static int	DEFAULT_WRITE_BUFFER_SIZE Default size of the buffer used to write data on disk.
static boolean	FORBID_DUPLICATES The B-tree forbids duplicate values

Method Summary

Modifier and Type	Method and Description
TupleCursor<K,V>	browse() Creates a cursor starting at the beginning of the tree
TupleCursor<K,V>	browse(long revision) Creates a cursor starting at the beginning of the tree, for a given revision
TupleCursor<K,V>	browseFrom(K key) Creates a cursor starting on the given key
TupleCursor<K,V>	browseFrom(long revision, K key) Creates a cursor starting on the given key at the given revision
KeyCursor<K>	browseKeys() Creates a cursor starting at the beginning of the tree
void	close() Close the B-tree, cleaning up all the data structure
boolean	contains(K key, V value) Checks if the B-tree contains the given key with the given value.
boolean	contains(long revision, K key, V value) Checks if the B-tree contains the given key with the given value for a given revision
Tuple<K,V>	delete(K key) Delete the entry which key is given as a parameter.
Tuple<K,V>	delete(K key, V value) Delete the value from an entry associated with the given key.
void	flush() Flush the latest revision to disk.
V	get(K key) Find a value in the tree, given its key.
V	get(long revision, K key) Find a value in the tree, given its key, at a specific revision.
java.util.Comparator<K>	getKeyComparator()
ElementSerializer<K>	getKeySerializer()
java.lang.String	getKeySerializerFQCN()
java.lang.String	getName()
long	getNbElems()
int	getPageSize()
long	getReadTimeOut()
long	getRevision()
Page<K,V>	getRootPage() Get the current rootPage
Page<K,V>	getRootPage(long revision) Get the rootPage associated to a given revision.
BTreeTypeEnum	getType()
java.util.Comparator<V>	getValueComparator()
ValueCursor<V>	getValues(K key)
ElementSerializer<V>	getValueSerializer()
java.lang.String	getValueSerializerFQCN()
int	getWriteBufferSize()
boolean	hasKey(K key) Checks if the given key exists.
boolean	hasKey(long revision, K key) Checks if the given key exists for a given revision.
V	insert(K key, V value) Insert an entry in the B-tree.
boolean	isAllowDuplicates()
void	setAllowDuplicates(boolean allowDuplicates)
void	setKeySerializer(ElementSerializer<K> keySerializer)
void	setName(java.lang.String name)
void	setPageSize(int pageSize) Set the maximum number of elements we can store in a page.
void	setReadTimeOut(long readTimeOut)
void	setValueSerializer(ElementSerializer<V> valueSerializer)
void	setWriteBufferSize(int writeBufferSize)

Field Detail

DEFAULT_PAGE_SIZE

static final int DEFAULT_PAGE_SIZE

Default page size (number of entries per node)

See Also:

Constant Field Values

DEFAULT_WRITE_BUFFER_SIZE

static final int DEFAULT_WRITE_BUFFER_SIZE

Default size of the buffer used to write data on disk. Around 1Mb

See Also:

Constant Field Values

DEFAULT_READ_TIMEOUT

static final long DEFAULT_READ_TIMEOUT

Define a default delay for a read transaction. This is 10 seconds

See Also:

Constant Field Values

ALLOW_DUPLICATES

static final boolean ALLOW_DUPLICATES

The B-tree allows duplicate values

See Also:

Constant Field Values

FORBID_DUPLICATES

static final boolean FORBID_DUPLICATES

The B-tree forbids duplicate values

See Also:

Constant Field Values

Method Detail

close

void close()
    throws java.io.IOException

Close the B-tree, cleaning up all the data structure

Throws:

java.io.IOException

setPageSize

void setPageSize(int pageSize)

Set the maximum number of elements we can store in a page. This must be a number greater than 1, and a power of 2. The default page size is 16.
If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.
If the provided size is not a power of 2, we will select the closest power of 2 higher than the given number

Parameters:

pageSize - The requested page size

getPageSize

int getPageSize()

Returns:

the number of elements per page

insert

V insert(K key,
         V value)
  throws java.io.IOException

Insert an entry in the B-tree.

We will replace the value if the provided key already exists in the B-tree.

Parameters:

key - Inserted key

value - Inserted value

Returns:

Existing value, if any.

Throws:

java.io.IOException - TODO

delete

Tuple<K,V> delete(K key)
           throws java.io.IOException

Delete the entry which key is given as a parameter. If the entry exists, it will be removed from the tree, the old tuple will be returned. Otherwise, null is returned.

Parameters:

key - The key for the entry we try to remove

Returns:

A Tuple containing the removed entry, or null if it's not found.

Throws:

java.io.IOException

delete

Tuple<K,V> delete(K key,
                  V value)
           throws java.io.IOException

Delete the value from an entry associated with the given key. If the value If the value is present, it will be deleted first, later if there are no other values associated with this key(which can happen when duplicates are enabled), we will remove the key from the tree.

Parameters:

key - The key for the entry we try to remove

value - The value to delete (can be null)

Returns:

A Tuple containing the removed entry, or null if it's not found.

Throws:

java.io.IOException

get

V get(K key)
throws java.io.IOException,
      KeyNotFoundException

Find a value in the tree, given its key. If the key is not found, it will throw a KeyNotFoundException.
Note that we can get a null value stored, or many values.

Parameters:

key - The key we are looking at

Returns:

The found value, or null if the key is not present in the tree

Throws:

KeyNotFoundException - If the key is not found in the B-tree

java.io.IOException - TODO

getRootPage

Page<K,V> getRootPage(long revision)
               throws java.io.IOException,
                      KeyNotFoundException

Get the rootPage associated to a given revision.

Parameters:

revision - The revision we are looking for

Returns:

The rootPage associated to this revision

Throws:

java.io.IOException - If we had an issue while accessing the underlying file

KeyNotFoundException - If the revision does not exist for this B-tree

getRootPage

Page<K,V> getRootPage()

Get the current rootPage

Returns:

The current rootPage

getValues

ValueCursor<V> getValues(K key)
                  throws java.io.IOException,
                         KeyNotFoundException

Throws:

java.io.IOException

KeyNotFoundException

See Also:

Page.getValues(Object)

get

V get(long revision,
      K key)
throws java.io.IOException,
      KeyNotFoundException

Find a value in the tree, given its key, at a specific revision. If the key is not found, it will throw a KeyNotFoundException.
Note that we can get a null value stored, or many values.

Parameters:

revision - The revision for which we want to find a key

key - The key we are looking at

Returns:

The found value, or null if the key is not present in the tree

Throws:

KeyNotFoundException - If the key is not found in the B-tree

java.io.IOException - If there was an issue while fetching data from the disk

hasKey

boolean hasKey(K key)
        throws java.io.IOException,
               KeyNotFoundException

Checks if the given key exists.

Parameters:

key - The key we are looking at

Returns:

true if the key is present, false otherwise

Throws:

java.io.IOException - If we have an error while trying to access the page

KeyNotFoundException - If the key is not found in the B-tree

hasKey

boolean hasKey(long revision,
               K key)
        throws java.io.IOException,
               KeyNotFoundException

Checks if the given key exists for a given revision.

Parameters:

revision - The revision for which we want to find a key

key - The key we are looking at

Returns:

true if the key is present, false otherwise

Throws:

java.io.IOException - If we have an error while trying to access the page

KeyNotFoundException - If the key is not found in the B-tree

contains

boolean contains(K key,
                 V value)
          throws java.io.IOException

Checks if the B-tree contains the given key with the given value.

Parameters:

key - The key we are looking for

value - The value associated with the given key

Returns:

true if the key and value are associated with each other, false otherwise

Throws:

java.io.IOException

contains

boolean contains(long revision,
                 K key,
                 V value)
          throws java.io.IOException,
                 KeyNotFoundException

Checks if the B-tree contains the given key with the given value for a given revision

Parameters:

revision - The revision we would like to browse

key - The key we are looking for

value - The value associated with the given key

Returns:

true if the key and value are associated with each other, false otherwise

Throws:

KeyNotFoundException - If the key is not found in the B-tree

java.io.IOException

browse

TupleCursor<K,V> browse()
                 throws java.io.IOException,
                        KeyNotFoundException

Creates a cursor starting at the beginning of the tree

Returns:

A cursor on the B-tree

Throws:

java.io.IOException

KeyNotFoundException

browse

TupleCursor<K,V> browse(long revision)
                 throws java.io.IOException,
                        KeyNotFoundException

Creates a cursor starting at the beginning of the tree, for a given revision

Parameters:

revision - The revision we would like to browse

Returns:

A cursor on the B-tree

Throws:

java.io.IOException - If we had an issue while fetching data from the disk

KeyNotFoundException - If the key is not found in the B-tree

browseFrom

TupleCursor<K,V> browseFrom(K key)
                     throws java.io.IOException

Creates a cursor starting on the given key

Parameters:

key - The key which is the starting point. If the key is not found, then the cursor will always return null.

Returns:

A cursor on the B-tree

Throws:

java.io.IOException

browseFrom

TupleCursor<K,V> browseFrom(long revision,
                            K key)
                     throws java.io.IOException,
                            KeyNotFoundException

Creates a cursor starting on the given key at the given revision

Parameters:

The - revision we are looking for

key - The key which is the starting point. If the key is not found, then the cursor will always return null.

Returns:

A cursor on the B-tree

Throws:

java.io.IOException - If wxe had an issue reading the B-tree from disk

KeyNotFoundException - If we can't find a rootPage for this revision

browseKeys

KeyCursor<K> browseKeys()
                 throws java.io.IOException,
                        KeyNotFoundException

Creates a cursor starting at the beginning of the tree

Returns:

A cursor on the B-tree keys

Throws:

java.io.IOException

KeyNotFoundException

getKeyComparator

java.util.Comparator<K> getKeyComparator()

Returns:

the key comparator

getValueComparator

java.util.Comparator<V> getValueComparator()

Returns:

the value comparator

setKeySerializer

void setKeySerializer(ElementSerializer<K> keySerializer)

Parameters:

keySerializer - the Key serializer to set

setValueSerializer

void setValueSerializer(ElementSerializer<V> valueSerializer)

Parameters:

valueSerializer - the Value serializer to set

flush

void flush()
    throws java.io.IOException

Flush the latest revision to disk. We will replace the current file by the new one, as we flush in a temporary file.

Throws:

java.io.IOException

getReadTimeOut

long getReadTimeOut()

Returns:

the readTimeOut

setReadTimeOut

void setReadTimeOut(long readTimeOut)

Parameters:

readTimeOut - the readTimeOut to set

getName

java.lang.String getName()

Returns:

the name

setName

void setName(java.lang.String name)

Parameters:

name - the name to set

getWriteBufferSize

int getWriteBufferSize()

Returns:

the writeBufferSize

setWriteBufferSize

void setWriteBufferSize(int writeBufferSize)

Parameters:

writeBufferSize - the writeBufferSize to set

getKeySerializer

ElementSerializer<K> getKeySerializer()

Returns:

the keySerializer

getKeySerializerFQCN

java.lang.String getKeySerializerFQCN()

Returns:

the keySerializer FQCN

getValueSerializer

ElementSerializer<V> getValueSerializer()

Returns:

the valueSerializer

getValueSerializerFQCN

java.lang.String getValueSerializerFQCN()

Returns:

the valueSerializer FQCN

getRevision

long getRevision()

Returns:

The current B-tree revision

getNbElems

long getNbElems()

Returns:

The current number of elements in the B-tree

isAllowDuplicates

boolean isAllowDuplicates()

Returns:

true if this B-tree allow duplicate values

setAllowDuplicates

void setAllowDuplicates(boolean allowDuplicates)

Parameters:

allowDuplicates - True if the B-tree will allow duplicate values

getType

BTreeTypeEnum getType()

Returns:

the type