org.helidb.util.bplus
Class LruCacheNodeRepository<K,V>

java.lang.Object
  org.entityfs.support.lang.ObjectProxySupport<NodeRepository<K>>
      org.helidb.util.bplus.LruCacheNodeRepository<K,V>

Type Parameters:

K - The type of keys in the node repository.

V - The type of values in the node repository.

All Implemented Interfaces:

NodeRepository<K>

public class LruCacheNodeRepository<K,V>
extends ObjectProxySupport<NodeRepository<K>>
implements NodeRepository<K>

This node repository has a LRU cache for the nodes read from another, proxied node repository. LRU stands for Least Recently Used and means that the least recently used node is purged from the cache when inserting a new node if the cache is at its maximum size.

A LRU cache is a good way to speed up a B+ Tree for a low cost in extra memory overhead since the tree's root node and the nodes near the root node is usually accessed far more often than each of the leaf nodes.

Since:

1.0

Author:

Karl Gustafsson

See Also:

LruCacheNodeRepositoryBuilder

In_jar:

helidb-core

Constructor Summary

LruCacheNodeRepository(NodeRepository<K> nr, int maxCacheSize)
Create a new LRU caching node repository.

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 dataLen) 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.

Methods inherited from class org.entityfs.support.lang.ObjectProxySupport

equals, getProxied, hashCode, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

LruCacheNodeRepository

public LruCacheNodeRepository(NodeRepository<K> nr,
                              int maxCacheSize)
                       throws IllegalArgumentException

Create a new LRU caching node repository.

Parameters:

nr - The proxied node repository.

maxCacheSize - The maximum size of the cache, in number of nodes.

Throws:

IllegalArgumentException - If the maximum cache size is less than 1.

Method Detail

getPositionOfRootNode

public long getPositionOfRootNode()

Description copied from interface: NodeRepository

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

Specified by:

getPositionOfRootNode in interface NodeRepository<K>

Returns:

The position of the root node in the node repository.

getMaxNumberOfRecordsForLeafNode

public int getMaxNumberOfRecordsForLeafNode(long pos)

Description copied from interface: NodeRepository

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.

Specified by:

getMaxNumberOfRecordsForLeafNode in interface NodeRepository<K>

Parameters:

pos - The position of the leaf node.

Returns:

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

getMaxNumberOfRecordsForNonLeafNode

public int getMaxNumberOfRecordsForNonLeafNode(long pos)

Description copied from interface: NodeRepository

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.

Specified by:

getMaxNumberOfRecordsForNonLeafNode in interface NodeRepository<K>

Parameters:

pos - The position of the non-leaf node.

Returns:

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

leafNodeHasPointersToAdjacentLeafNodes

public boolean leafNodeHasPointersToAdjacentLeafNodes()

Description copied from interface: NodeRepository

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

Specified by:

leafNodeHasPointersToAdjacentLeafNodes in interface NodeRepository<K>

Returns:

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

bookPositionForLeafNode

public long bookPositionForLeafNode()

Description copied from interface: NodeRepository

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

Specified by:

bookPositionForLeafNode in interface NodeRepository<K>

Returns:

The position of the booked leaf node.

See Also:

NodeRepository.bookPositionForNonLeafNode(), NodeRepository.returnBookedLeafNodePosition(long)

returnBookedLeafNodePosition

public void returnBookedLeafNodePosition(long p)

Description copied from interface: NodeRepository

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.

Specified by:

returnBookedLeafNodePosition in interface NodeRepository<K>

Parameters:

p - The position to return.

See Also:

NodeRepository.bookPositionForLeafNode(), NodeRepository.returnBookedNonLeafNodePosition(long)

bookPositionForNonLeafNode

public long bookPositionForNonLeafNode()

Description copied from interface: NodeRepository

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

Specified by:

bookPositionForNonLeafNode in interface NodeRepository<K>

Returns:

The position of the booked node.

See Also:

NodeRepository.bookPositionForLeafNode(), NodeRepository.returnBookedNonLeafNodePosition(long)

returnBookedNonLeafNodePosition

public void returnBookedNonLeafNodePosition(long p)

Description copied from interface: NodeRepository

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.

Specified by:

returnBookedNonLeafNodePosition in interface NodeRepository<K>

Parameters:

p - The position to return.

See Also:

NodeRepository.bookPositionForNonLeafNode(), NodeRepository.returnBookedLeafNodePosition(long)

readNode

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

Description copied from interface: NodeRepository

Read the node at the supplied position.

Specified by:

readNode in interface NodeRepository<K>

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

public K writeNode(BPlusTreeNode<K,?> node)

Description copied from interface: NodeRepository

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

Specified by:

writeNode in interface NodeRepository<K>

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

public void deleteNode(long pos,
                       boolean leafNode)

Description copied from interface: NodeRepository

Delete the node at the supplied position.

Specified by:

deleteNode in interface NodeRepository<K>

Parameters:

pos - The position of the node to delete.

leafNode - Is the node to delete a leaf node?

clear

public void clear()

Description copied from interface: NodeRepository

Remove all contents from the node repository.

Specified by:

clear in interface NodeRepository<K>

compact

public boolean compact()

Description copied from interface: NodeRepository

Defragment the node repository to recover wasted disk space.

Specified by:

compact in interface NodeRepository<K>

Returns:

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

writeContentsTo

public long writeContentsTo(OutputStream os)

Description copied from interface: NodeRepository

Write the contents of the node repository to the stream.

Specified by:

writeContentsTo in interface NodeRepository<K>

Parameters:

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

Returns:

The number of bytes written.

replaceContentsWith

public void replaceContentsWith(InputStream is,
                                long dataLen)

Description copied from interface: NodeRepository

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

Specified by:

replaceContentsWith in interface NodeRepository<K>

Parameters:

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

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

close

public void close()

Description copied from interface: NodeRepository

Close the node repository and release all its allocated resources.

Specified by:

close in interface NodeRepository<K>

verifyRepositoryIntegrity

public void verifyRepositoryIntegrity()

Description copied from interface: NodeRepository

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

Specified by:

verifyRepositoryIntegrity in interface NodeRepository<K>