Package com.semedy.reasoner.edb.persistentstore.bplustree

Class BPlusTree<KeyType,KeyBufferType>

java.lang.Object

com.semedy.reasoner.edb.persistentstore.bplustree.BPlusTree<KeyType,KeyBufferType>

Type Parameters:

KeyType -

KeyBufferType -

All Implemented Interfaces:

Closeable, AutoCloseable

public class BPlusTree<KeyType,KeyBufferType>
extends Object
implements Closeable

This class implements a B+ Tree on disk.
The disk IO is handled by the BPlusTreeFile class.

Author:

angele

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	BPlusTree.BplusIterator

Field Summary

Fields

Modifier and Type	Field	Description
BPlusTreeFile<KeyType,KeyBufferType>	_treeFile	the file

Constructor Summary

Constructors

Constructor	Description
BPlusTree(String filename, int numberOfKeys, int keyLengthInBytes, KeysFactory<KeyType,KeyBufferType> keysFactory, LeafFactory<KeyType,KeyBufferType> leafFactory, int additionalHeadSpace, long[] grounds, boolean compress)	Initializes a fixed key number and fixed key length tree
BPlusTree(String filename, int numberOfKeys, KeysFactory<KeyType,KeyBufferType> keysFactory, int nodeLengthInBytes, LeafFactory<KeyType,KeyBufferType> leafFactory, long[] grounds, boolean compress)	Initializes a variable key number, key length tree

Method Summary

Modifier and Type	Method	Description
boolean	addKey(KeyType key, boolean shadow)	Add a key (without a value)
boolean	addKey(KeyType key, long value, boolean shadow)	Inserting a record into the tree.
void	bulkAddKey(KeyType key, long record, boolean shadow)	bulk add a new record
boolean	checkSanity(String message, DataFile df, boolean shadow)	check sanity of whole tree
void	close()	close a bplus tree Dirty nodes are flushed to file File is closed.
boolean	containsKey(KeyType key, boolean shadow)	Contains given key
boolean	containsKeyBuffer(KeyBufferType key, boolean shadow)	Contains given key
void	create()	create a new bplus tree Existing file is overwritten
boolean	delete()	delete files close must have been called first
void	finishBulkLoading()	close bulk loading mode
KeyType	firstKey(boolean shadow)
void	firstKeyBuffer(KeyBufferType key, boolean shadow)
void	flush()
void	flushDirtyNodes()	Flushing dirty nodes to file
long	get(KeyType key, boolean shadow)	Attempts to find the record for the key within the tree.
long	getBuffer(KeyBufferType key, boolean shadow)	Attempts to find the record for the key within the tree.
BPlusNode<KeyType,KeyBufferType>	getChild(int offset, BPlusInternalNode<KeyType,KeyBufferType> node, int index, boolean shadow)
int	getFlags()
byte[]	getHeader()	Get all header info
Object	getInsertPosition(KeyType key, boolean shadow)	Attempts to find the insert position within the tree. Returns position (leaf and index in leaf)
Object	getInsertPositionByBuffer(KeyBufferType key, boolean shadow)	Attempts to find the insert position within the tree. Returns position (leaf and index in leaf)
BPlusNode<KeyType,KeyBufferType>	getNode(int offset, boolean shadow)
BPlusNode<KeyType,KeyBufferType>	getRoot()
Object	getSearchResult(KeyType key, boolean shadow)	Attempts to find the key within the tree. Returns search result (leaf and index in leaf)
Object	getSearchResultBuffer(KeyBufferType key, boolean shadow)	Attempts to find the key within the tree. Returns search result (leaf and index in leaf)
long	getSizeOnDisc()	size on disc
boolean	isEmpty()	The root should never be null, but we check anyway.
Iterator<KeyType>	iterator()
KeyType	nextKey(KeyType key, boolean shadow)
KeyType	nextKeyAfter(KeyType key, boolean shadow)
void	nextKeyAfterBuffer(KeyBufferType key, boolean next, KeyBufferType result, boolean shadow)
void	nextKeyAfterBuffer(KeyBufferType key, KeyBufferType result, boolean shadow)
boolean	open()	open an existing bplus tree
void	printTree(boolean shadow)	Prints the tree.
boolean	removeKey(KeyType key, boolean shadow)	Removes the record from the tree.
BPlusNode<KeyType,KeyBufferType>	rightBrother(BPlusNode<KeyType,KeyBufferType> b, boolean shadow)	get the right brother of a node
BPlusNode<KeyType,KeyBufferType>	rightSibling(BPlusNode<KeyType,KeyBufferType> b, boolean shadow)	get the right sibling of a node
BPlusPosition<KeyType,KeyBufferType>	searchFor(KeyBufferType key, boolean next, boolean shadow)	Search for a key inside tree
BPlusPosition<KeyType,KeyBufferType>	searchFor(KeyBufferType key, BPlusNode<KeyType,KeyBufferType> sRoot, boolean next, boolean shadow)	Search for a key inside tree
boolean	searchForRecord(long record, boolean shadow)
void	setCompressCache(boolean b)
boolean	setRecord(KeyType key, long value, boolean shadow)	Set the record for a given key.
void	setWriteThrough(boolean writethrough)	if writeThrough is true, all insert or remove operations are directly written to file Thus after an insert or remove operation tree is is always consistent on the disc Otherwise nodes are cached and written to the file by calling flushDirtyNodes or close
long	size()	number of elements in bplus tree
void	startBulkLoading()	Start bulk loading.
void	transactionBegin()
void	transactionCommit()
void	transactionRollback()
void	writeAdditionalHeadSpace(int additional)
void	writeFlags(int flags)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

_treeFile

public BPlusTreeFile<KeyType,KeyBufferType> _treeFile

the file

Constructor Details

BPlusTree

public BPlusTree(String filename,
 int numberOfKeys,
 int keyLengthInBytes,
 KeysFactory<KeyType,KeyBufferType> keysFactory,
 LeafFactory<KeyType,KeyBufferType> leafFactory,
 int additionalHeadSpace,
 long[] grounds,
 boolean compress)

Initializes a fixed key number and fixed key length tree

Parameters:

filename - , file name for the bpus nodes file

numberOfKeys - , @keyLengthInBytes, length of keys in bytes

keyLengthInBytes -

keysFactory -

leafFactory -

additionalHeadSpace -

BPlusTree

public BPlusTree(String filename,
 int numberOfKeys,
 KeysFactory<KeyType,KeyBufferType> keysFactory,
 int nodeLengthInBytes,
 LeafFactory<KeyType,KeyBufferType> leafFactory,
 long[] grounds,
 boolean compress)

Initializes a variable key number, key length tree

Parameters:

filename - , file name for the bpus nodes file

numberOfKeys -

keysFactory -

nodeLengthInBytes -

leafFactory -

Method Details

setCompressCache

public void setCompressCache(boolean b)

getSizeOnDisc

public long getSizeOnDisc()

size on disc

Returns:

getHeader

public byte[] getHeader()

Get all header info

Returns:

open

public boolean open()
             throws IOException,
EDBException

open an existing bplus tree

Throws:

IOException

EDBException

create

public void create()
            throws IOException,
EDBException

create a new bplus tree
Existing file is overwritten

Throws:

IOException

EDBException

close

public void close()
           throws IOException

close a bplus tree
Dirty nodes are flushed to file File is closed.

Specified by:

close in interface AutoCloseable

Specified by:

close in interface Closeable

Throws:

IOException

flush

public void flush()
           throws IOException

Throws:

IOException

delete

public boolean delete()

delete files
close must have been called first

Returns:

flushDirtyNodes

public void flushDirtyNodes()
                     throws IOException,
EDBException

Flushing dirty nodes to file

Throws:

IOException

EDBException

size

public long size()

number of elements in bplus tree

Returns:

printTree

public void printTree(boolean shadow)
               throws IOException

Prints the tree.

Throws:

IOException

setWriteThrough

public void setWriteThrough(boolean writethrough)

if writeThrough is true, all insert or remove operations are directly written to file
Thus after an insert or remove operation tree is
is always consistent on the disc
Otherwise nodes are cached and written to the file
by calling flushDirtyNodes or close

Parameters:

writethrough -

removeKey

public boolean removeKey(KeyType key,
 boolean shadow)
                  throws IOException,
EDBException

Removes the record from the tree.

Parameters:

key -

shadow -

Throws:

IOException

EDBException

isEmpty

public boolean isEmpty()

The root should never be null, but we check anyway.

Returns:

the status of the tree.

get

public long get(KeyType key,
 boolean shadow)
         throws IOException

Attempts to find the record for the key within the tree.

Parameters:

key -

shadow - , read from shadow tree

Returns:

the record for the key, or null if not found.

Throws:

IOException

getSearchResult

public Object getSearchResult(KeyType key,
 boolean shadow)
                       throws IOException

Attempts to find the key within the tree.
Returns search result (leaf and index in leaf)

Parameters:

key -

shadow - , read from shadow tree

Returns:

the record for the key, or null if not found.

Throws:

IOException

getSearchResultBuffer

public Object getSearchResultBuffer(KeyBufferType key,
 boolean shadow)
                             throws IOException

Attempts to find the key within the tree.
Returns search result (leaf and index in leaf)

Parameters:

key -

shadow - , read from shadow tree

Returns:

the record for the key, or null if not found.

Throws:

IOException

getInsertPosition

public Object getInsertPosition(KeyType key,
 boolean shadow)
                         throws IOException

Attempts to find the insert position within the tree.
Returns position (leaf and index in leaf)

Parameters:

key -

shadow - , read from shadow tree

Returns:

the insert position as BplusPosition

Throws:

IOException

getInsertPositionByBuffer

public Object getInsertPositionByBuffer(KeyBufferType key,
 boolean shadow)
                                 throws IOException

Attempts to find the insert position within the tree.
Returns position (leaf and index in leaf)

Parameters:

key -

shadow - , read from shadow tree

Returns:

the insert position as BplusPosition

Throws:

IOException

getBuffer

public long getBuffer(KeyBufferType key,
 boolean shadow)
               throws IOException

Attempts to find the record for the key within the tree.

Parameters:

key -

shadow - , read from shadow tree

Returns:

the record for the key, or null if not found.

Throws:

IOException

containsKey

public boolean containsKey(KeyType key,
 boolean shadow)
                    throws IOException

Contains given key

Parameters:

key -

shadow - , read from shadow tree

Returns:

Throws:

IOException

containsKeyBuffer

public boolean containsKeyBuffer(KeyBufferType key,
 boolean shadow)
                          throws IOException

Contains given key

Parameters:

key -

shadow - , read from shadow tree

Returns:

Throws:

IOException

getRoot

public BPlusNode<KeyType,KeyBufferType> getRoot()

rightSibling

public BPlusNode<KeyType,KeyBufferType> rightSibling(BPlusNode<KeyType,KeyBufferType> b,
 boolean shadow)
                                              throws IOException

get the right sibling of a node

Parameters:

b - , node the right sibling is looked for

shadow - , read from shadow tree

Returns:

the right sibling node

Throws:

IOException

rightBrother

public BPlusNode<KeyType,KeyBufferType> rightBrother(BPlusNode<KeyType,KeyBufferType> b,
 boolean shadow)
                                              throws IOException

get the right brother of a node

Parameters:

b - , node the right sibling is looked for

shadow - , read from shadow tree

Returns:

the right sibling node

Throws:

IOException

getChild

public BPlusNode<KeyType,KeyBufferType> getChild(int offset,
 BPlusInternalNode<KeyType,KeyBufferType> node,
 int index,
 boolean shadow)
                                          throws IOException

Throws:

IOException

getNode

public BPlusNode<KeyType,KeyBufferType> getNode(int offset,
 boolean shadow)
                                         throws IOException

Throws:

IOException

searchForRecord

public boolean searchForRecord(long record,
 boolean shadow)
                        throws IOException

Throws:

IOException

checkSanity

public boolean checkSanity(String message,
 DataFile df,
 boolean shadow)
                    throws IOException

check sanity of whole tree

Returns:

Throws:

IOException

searchFor

public BPlusPosition<KeyType,KeyBufferType> searchFor(KeyBufferType key,
 BPlusNode<KeyType,KeyBufferType> sRoot,
 boolean next,
 boolean shadow)
                                               throws IOException

Search for a key inside tree

Parameters:

key - , the key to search for

next - , if next is true and then the next key after given key is searched for

shadow - , read from shadow tree

Returns:

Throws:

IOException

searchFor

public BPlusPosition<KeyType,KeyBufferType> searchFor(KeyBufferType key,
 boolean next,
 boolean shadow)
                                               throws IOException

Search for a key inside tree

Parameters:

key - , the key to search for

next - , if next is true and then the next key after given key is searched for

shadow - , read from shadow tree

Returns:

Throws:

IOException

addKey

public boolean addKey(KeyType key,
 boolean shadow)
               throws IOException,
EDBException

Add a key (without a value)

Parameters:

key -

shadow -

Returns:

Throws:

IOException

EDBException

addKey

public boolean addKey(KeyType key,
 long value,
 boolean shadow)
               throws IOException,
EDBException

Inserting a record into the tree.

Parameters:

key -

value -

shadow -

Throws:

IOException

EDBException

setRecord

public boolean setRecord(KeyType key,
 long value,
 boolean shadow)
                  throws IOException,
EDBException

Set the record for a given key.
Returns false if key is not there

Parameters:

key -

value -

shadow -

Throws:

IOException

EDBException

startBulkLoading

public void startBulkLoading()
                      throws IOException,
EDBException

Start bulk loading. Loading is sped up tremendiously
Works only if bplus tree is empty, otherwise normal (cached)
inserts are performed

Throws:

IOException

EDBException

bulkAddKey

public void bulkAddKey(KeyType key,
 long record,
 boolean shadow)
                throws IOException,
EDBException

bulk add a new record

Parameters:

key -

record -

Throws:

IOException

EDBException

finishBulkLoading

public void finishBulkLoading()
                       throws IOException,
EDBException

close bulk loading mode

Throws:

IOException

EDBException

firstKey

public KeyType firstKey(boolean shadow)
                 throws IOException

Throws:

IOException

firstKeyBuffer

public void firstKeyBuffer(KeyBufferType key,
 boolean shadow)
                    throws IOException

Throws:

IOException

nextKey

public KeyType nextKey(KeyType key,
 boolean shadow)
                throws IOException

Throws:

IOException

nextKeyAfter

public KeyType nextKeyAfter(KeyType key,
 boolean shadow)
                     throws IOException

Throws:

IOException

nextKeyAfterBuffer

public void nextKeyAfterBuffer(KeyBufferType key,
 KeyBufferType result,
 boolean shadow)
                        throws IOException

Throws:

IOException

nextKeyAfterBuffer

public void nextKeyAfterBuffer(KeyBufferType key,
 boolean next,
 KeyBufferType result,
 boolean shadow)
                        throws IOException

Throws:

IOException

iterator

public Iterator<KeyType> iterator()

transactionRollback

public void transactionRollback()
                         throws IOException

Throws:

IOException

transactionBegin

public void transactionBegin()
                      throws IOException

Throws:

IOException

transactionCommit

public void transactionCommit()
                       throws IOException,
EDBException

Throws:

IOException

EDBException

writeFlags

public void writeFlags(int flags)
                throws IOException

Throws:

IOException

writeAdditionalHeadSpace

public void writeAdditionalHeadSpace(int additional)
                              throws IOException

Throws:

IOException

getFlags

public int getFlags()