org.helidb.util.bplus
Interface NodeRepository<K>

Type Parameters:

K - The type of keys in the node.

All Known Implementing Classes:

FileBackedNodeRepository, LruCacheNodeRepository

public interface NodeRepository<K>

The BPlusTree uses a NodeRepository to store and retrieve tree nodes.

When updating a tree, the BPlusTree may book nodes before actually writing something to them. See bookPositionForLeafNode() and bookPositionForNonLeafNode().

Since:

1.0

Author:

Karl Gustafsson

See Also:

BPlusTree

In_jar:

helidb-core

Method Summary

long	bookPositionForLeafNode() Book a position for a future leaf node.
long	bookPositionForNonLeafNode() Book a position for a future non-leaf node.
void	clear() Remove all contents from the node repository.
void	close() Close the node repository and release all its allocated resources.
boolean	compact() Defragment the node repository to recover wasted disk space.
void	deleteNode(long pos, boolean leafNode) Delete the node at the supplied position.
int	getMaxNumberOfRecordsForLeafNode(long pos) Get the maximum number of records for a leaf node in the tree at the supplied position.
int	getMaxNumberOfRecordsForNonLeafNode(long pos) Get the maximum number of records for a non-leaf node in the tree at the supplied position.
long	getPositionOfRootNode() Get the root node's position in the node repository.
boolean	leafNodeHasPointersToAdjacentLeafNodes() Does leaf nodes have pointers to their adjacent leaf nodes? If so, the tree supports iteration.
BPlusTreeNode<K,?>	readNode(long pos, K keyForFirstPointer) Read the node at the supplied position.
void	replaceContentsWith(InputStream is, long dataSize) Replace the contents of the node repository with data read from the stream.
void	returnBookedLeafNodePosition(long p) Return a previously booked position for a leaf node.
void	returnBookedNonLeafNodePosition(long p) Return a previously booked position for a non-leaf node.
void	verifyRepositoryIntegrity() Verify the node repository's integrity.
long	writeContentsTo(OutputStream os) Write the contents of the node repository to the stream.
K	writeNode(BPlusTreeNode<K,?> node) Write the node to the repository.

Method Detail

getMaxNumberOfRecordsForLeafNode

int getMaxNumberOfRecordsForLeafNode(long pos)

Get the maximum number of records for a leaf node in the tree at the supplied position. This number is determined by the NodeRepository's NodeSizeStrategy, and by what extra metadata the NodeRepository stores for each leaf nodes.

Parameters:

pos - The position of the leaf node.

Returns:

The maximum number of records per leaf node in the tree.

getMaxNumberOfRecordsForNonLeafNode

int getMaxNumberOfRecordsForNonLeafNode(long pos)

Get the maximum number of records for a non-leaf node in the tree at the supplied position. This number is determined by the NodeRepository's NodeSizeStrategy, and by what extra metadata the NodeRepository stores for each non-leaf nodes.

Parameters:

pos - The position of the non-leaf node.

Returns:

The maximum number of records per non-leaf node in the tree.

getPositionOfRootNode

long getPositionOfRootNode()

Get the root node's position in the node repository. The root node is the beginning of all searches, etc.

Returns:

The position of the root node in the node repository.

leafNodeHasPointersToAdjacentLeafNodes

boolean leafNodeHasPointersToAdjacentLeafNodes()

Does leaf nodes have pointers to their adjacent leaf nodes? If so, the tree supports iteration.

Returns:

true if leaf nodes have pointers to their adjacent leaf nodes.

bookPositionForLeafNode

long bookPositionForLeafNode()

Book a position for a future leaf node. The position must be used for writing a new node, or returned by calling returnBookedLeafNodePosition(long).

Returns:

The position of the booked leaf node.

See Also:

bookPositionForNonLeafNode(), returnBookedLeafNodePosition(long)

returnBookedLeafNodePosition

void returnBookedLeafNodePosition(long p)

Return a previously booked position for a leaf node. This is used when recovering from an error that prevented us to write a new leaf node.

Parameters:

p - The position to return.

See Also:

bookPositionForLeafNode(), returnBookedNonLeafNodePosition(long)

bookPositionForNonLeafNode

long bookPositionForNonLeafNode()

Book a position for a future non-leaf node. The position must be used for writing a new node, or returned by calling returnBookedNonLeafNodePosition(long).

Returns:

The position of the booked node.

See Also:

bookPositionForLeafNode(), returnBookedNonLeafNodePosition(long)

returnBookedNonLeafNodePosition

void returnBookedNonLeafNodePosition(long p)

Return a previously booked position for a non-leaf node. This is used when recovering from an error that prevented us to write a new non-leaf node.

Parameters:

p - The position to return.

See Also:

bookPositionForNonLeafNode(), returnBookedLeafNodePosition(long)

readNode

BPlusTreeNode<K,?> readNode(long pos,
                            K keyForFirstPointer)

Read the node at the supplied position.

Parameters:

pos - The position to read the node at. The root node has position 0.

keyForFirstPointer - The key for the node's first pointer, if this is a non-leaf node. The key for the root node's first pointer is null.

Returns:

The node, or null if the node position is beyond the end of the file.

writeNode

K writeNode(BPlusTreeNode<K,?> node)

Write the node to the repository. The node contains information about its own position in the repository.

Parameters:

node - The node to write.

Returns:

The key for the first record in the node, if the node is a leaf node, or the key for the node's leftmost pointer if the node is a non-leaf node.

deleteNode

void deleteNode(long pos,
                boolean leafNode)

Delete the node at the supplied position.

Parameters:

pos - The position of the node to delete.

leafNode - Is the node to delete a leaf node?

writeContentsTo

long writeContentsTo(OutputStream os)
                     throws WrappedIOException

Write the contents of the node repository to the stream.

Parameters:

os - The stream to write to. The stream is not closed after writing.

Returns:

The number of bytes written.

Throws:

WrappedIOException - On I/O errors.

replaceContentsWith

void replaceContentsWith(InputStream is,
                         long dataSize)
                         throws WrappedIOException,
                                NotEnoughDataException

Replace the contents of the node repository with data read from the stream.

Parameters:

is - The stream to read from. The stream is not closed after reading.

dataSize - The total number of bytes to read from the stream.

Throws:

WrappedIOException - On I/O errors.

NotEnoughDataException - If there is not enough data available in the stream.

clear

void clear()

Remove all contents from the node repository.

compact

boolean compact()

Defragment the node repository to recover wasted disk space.

Returns:

true if the node repository was defragmented, or false if there was nothing to defragment right now.

close

void close()

Close the node repository and release all its allocated resources.

verifyRepositoryIntegrity

void verifyRepositoryIntegrity()

Verify the node repository's integrity. This should only be used for testing purposes.