org.apache.directory.mavibot.btree

Interface Page<K,V>

Type Parameters:

K - The type for the Key

V - The type for the stored value

All Known Implementing Classes:

AbstractPage, InMemoryLeaf, InMemoryNode, PersistedLeaf, PersistedNode

interface Page<K,V>

A MVCC Page interface. A Page can be either a Leaf (containing keys and values) or a Node (containing keys and references to child pages).
A Page can be stored on disk. If so, we store the serialized value of this Page into one or more PageIO (they will be linked)

Method Summary

Modifier and Type	Method and Description
TupleCursor<K,V>	browse(K key, ReadTransaction<K,V> transaction, ParentPos<K,V>[] stack, int depth) Browses the tree, looking for the given key, and creates a Cursor on top of the found result.
TupleCursor<K,V>	browse(ReadTransaction<K,V> transaction, ParentPos<K,V>[] stack, int depth) Browses the whole tree, and creates a Cursor on top of it.
KeyCursor<K>	browseKeys(ReadTransaction<K,K> transaction, ParentPos<K,K>[] stack, int depth) Browses the keys of whole tree, and creates a Cursor on top of it.
boolean	contains(K key, V value) Checks if the page contains the given key with the given value.
DeleteResult<K,V>	delete(K key, V value, long revision) Deletes the value from an entry associated with the given key in this page.
java.lang.String	dumpPage(java.lang.String tabs) Pretty-prints the tree with tabs
Tuple<K,V>	findLeftMost() Finds the leftmost element in this page.
int	findPos(K key) Find the position of the given key in the page.
Tuple<K,V>	findRightMost() Finds the rightmost element in this page.
V	get(K key) Gets the value associated with the given key, if any.
K	getKey(int pos) Returns the key at a given position
K	getLeftMostKey() Finds the leftmost key in this page.
int	getNbElems()
long	getRevision()
K	getRightMostKey() Finds the rightmost key in this page.
ValueCursor<V>	getValues(K key) Gets the values associated with the given key, if any.
boolean	hasKey(K key) Checks if the given key exists.
InsertResult<K,V>	insert(K key, V value, long revision) Inserts the given key and value into this page.
boolean	isLeaf() Tells if the page is a leaf or not
boolean	isNode() Tells if the page is a node or not

Method Detail

getNbElems

int getNbElems()

Returns:

The number of keys present in this page

insert

InsertResult<K,V> insert(K key,
                         V value,
                         long revision)
                  throws java.io.IOException

Inserts the given key and value into this page. We first find the place were to inject the into the tree, by recursively browsing the pages :

• If the index is below zero, the key is present in the Page : we modify the value and return
• If the page is a node, we have to go down to the right child page
• If the page is a leaf, we insert the new element into the page, and if the Page is full, we split it and propagate the new pivot up into the tree

Parameters:

key - Inserted key

value - Inserted value

revision - The new revision for the modified pages

Returns:

Either a modified Page or an Overflow element if the Page was full

Throws:

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

delete

DeleteResult<K,V> delete(K key,
                         V value,
                         long revision)
                  throws java.io.IOException

Deletes the value from an entry associated with the given key in this page. We first find the place were to remove the into the tree, by recursively browsing the pages. 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:

revision - The new revision for the modified pages

key - The key to delete

value - The value to delete (can be null)

parent - The parent page

parentPos - The position of the current page in it's parent

Returns:

Either a modified Page if the key has been removed from the page, or a NotPresentResult.

Throws:

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

get

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

Gets the value associated with the given key, if any. If we don't have one, this method will throw a KeyNotFoundException.
Note that we may get back null if a null value has been associated with the key.

Parameters:

key - The key we are looking for

Returns:

The associated value, which can be null

Throws:

KeyNotFoundException - If no entry with the given key can be found

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

getValues

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

Gets the values associated with the given key, if any. If we don't have the key, this method will throw a KeyNotFoundException.
Note that we may get back null if a null value has been associated with the key.

Parameters:

key - The key we are looking for

Returns:

The associated value, which can be null

Throws:

KeyNotFoundException - If no entry with the given key can be found

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

java.lang.IllegalArgumentException - If duplicates are not enabled

contains

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

Checks if the page 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

browse

TupleCursor<K,V> browse(K key,
                        ReadTransaction<K,V> transaction,
                        ParentPos<K,V>[] stack,
                        int depth)
                 throws java.io.IOException

Browses the tree, looking for the given key, and creates a Cursor on top of the found result.

Parameters:

key - The key we are looking for.

transaction - The started transaction for this operation

stack - The stack of parents we go through to get to this page

Returns:

A Cursor to browse the next elements

Throws:

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

browse

TupleCursor<K,V> browse(ReadTransaction<K,V> transaction,
                        ParentPos<K,V>[] stack,
                        int depth)
                 throws EndOfFileExceededException,
                        java.io.IOException

Browses the whole tree, and creates a Cursor on top of it.

Parameters:

transaction - The started transaction for this operation

stack - The stack of parents we go through to get to this page

Returns:

A Cursor to browse the next elements

Throws:

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

EndOfFileExceededException

browseKeys

KeyCursor<K> browseKeys(ReadTransaction<K,K> transaction,
                        ParentPos<K,K>[] stack,
                        int depth)
                 throws EndOfFileExceededException,
                        java.io.IOException

Browses the keys of whole tree, and creates a Cursor on top of it.

Parameters:

transaction - The started transaction for this operation

stack - The stack of parents we go through to get to this page

Returns:

A Cursor to browse the keys

Throws:

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

EndOfFileExceededException

getRevision

long getRevision()

Returns:

the revision

getKey

K getKey(int pos)

Returns the key at a given position

Parameters:

pos - The position of the key we want to retrieve

Returns:

The key found at the given position

getLeftMostKey

K getLeftMostKey()

Finds the leftmost key in this page. If the page is a node, it will go down in the leftmost children to recursively find the leftmost key.

Returns:

The leftmost key in the tree

getRightMostKey

K getRightMostKey()

Finds the rightmost key in this page. If the page is a node, it will go down in the rightmost children to recursively find the rightmost key.

Returns:

The rightmost key in the tree

findLeftMost

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

Finds the leftmost element in this page. If the page is a node, it will go down in the leftmost children to recursively find the leftmost element.

Returns:

The leftmost element in the tree

Throws:

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

findRightMost

Tuple<K,V> findRightMost()
                  throws EndOfFileExceededException,
                         java.io.IOException

Finds the rightmost element in this page. If the page is a node, it will go down in the rightmost children to recursively find the rightmost element.

Returns:

The rightmost element in the tree

Throws:

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

EndOfFileExceededException

dumpPage

java.lang.String dumpPage(java.lang.String tabs)

Pretty-prints the tree with tabs

Parameters:

tabs - The tabs to add in front of each node

Returns:

A pretty-print dump of the tree

findPos

int findPos(K key)

Find the position of the given key in the page. If we have found the key, we will return its position as a negative value.

Assuming that the array is zero-indexed, the returned value will be :
position = - ( position + 1)
So for the following table of keys :

 +---+---+---+---+
 | b | d | f | h |
 +---+---+---+---+
   0   1   2   3
 

looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).
Computing the real position is just a matter to get -(position++).

If we don't find the key in the table, we will return the position of the key immediately above the key we are looking for.
For instance, looking for :

• 'a' will return 0
• 'b' will return -1
• 'c' will return 1
• 'd' will return -2
• 'e' will return 2
• 'f' will return -3
• 'g' will return 3
• 'h' will return -4
• 'i' will return 4

Parameters:

key - The key to find

Returns:

The position in the page.

hasKey

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

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

isLeaf

boolean isLeaf()

Tells if the page is a leaf or not

Returns:

true if the page is a leaf

isNode

boolean isNode()

Tells if the page is a node or not

Returns:

true if the page is a node