org.exist.storage.btree
Class BTree

java.lang.Object
  org.exist.storage.btree.Paged
      org.exist.storage.btree.BTree

Direct Known Subclasses:

BFile, BTreeStore, DOMFile

public class BTree
extends Paged

A general purpose B+-tree which stores binary keys as instances of Value. The actual value data is not stored in the B+tree itself. Instead, we use long pointers to record the storage address of the value. This class has no methods to locate or modify data records. Data handling is in the responsibilty of the proper subclasses: BFile and DOMFile. Both, branch and leaf nodes are represented by the inner class BTree.BTreeNode.

Nested Class Summary

protected class	BTree.BTreeFileHeader
protected class	BTree.BTreeNode A node in the B+-tree.
protected static class	BTree.BTreePageHeader

Nested classes/interfaces inherited from class org.exist.storage.btree.Paged

Paged.FileHeader, Paged.Page, Paged.PageHeader

Field Summary

protected static byte	BRANCH Type of BTreeNode/Page
protected int	buffers Size of BTreeNode cache
protected Cache	cache Cache of BTreeNode(s)
protected DefaultCacheManager	cacheManager
protected byte	fileId
protected double	growthThreshold
protected boolean	isTransactional
static long	KEY_NOT_FOUND Used as return value, if a value was not found
protected static byte	LEAF Type of BTreeNode/Page
static byte	LOG_CREATE_BNODE Log entry type for creation of a new btree node
static byte	LOG_INSERT_VALUE Log entry type for an insert value operation
static byte	LOG_REMOVE_VALUE Log entry type for removing a value
static byte	LOG_SET_LINK
static byte	LOG_SET_PARENT Log entry type for a parent page change resulting from a page split
static byte	LOG_UPDATE_PAGE Log entry type for a page update resulting from a page split
static byte	LOG_UPDATE_VALUE Log entry type for a value update
protected Journal	logManager The LogManager for writing the transaction log
protected static org.apache.log4j.Logger	LOGSTATS
protected static int	MIN_SPACE_PER_KEY
protected BrokerPool	pool

Fields inherited from class org.exist.storage.btree.Paged

DELETED, LENGTH_FIRST_FREE_PAGE, LENGTH_HEADER_SIZE, LENGTH_LAST_FREE_PAGE, LENGTH_MAX_KEY_SIZE, LENGTH_PAGE_COUNT, LENGTH_PAGE_HEADER_SIZE, LENGTH_PAGE_SIZE, LENGTH_RECORD_COUNT, LENGTH_TOTAL_COUNT, LENGTH_VERSION_ID, LOG, OFFSET_FIRST_FREE_PAGE, OFFSET_HEADER_SIZE, OFFSET_LAST_FREE_PAGE, OFFSET_MAX_KEY_SIZE, OFFSET_PAGE_COUNT, OFFSET_PAGE_HEADER_SIZE, OFFSET_PAGE_SIZE, OFFSET_RECORD_COUNT, OFFSET_REMAINDER, OFFSET_TOTAL_COUNT, OFFSET_VERSION_ID, OVERFLOW, PAGE_SIZE, UNUSED

Constructor Summary

protected	BTree(BrokerPool pool, byte fileId, boolean transactional, DefaultCacheManager cacheManager, double growthThreshold)
	BTree(BrokerPool pool, byte fileId, boolean transactional, DefaultCacheManager cacheManager, java.io.File file, double growthThreshold)

Method Summary

long	addValue(Txn transaction, Value value, long pointer)
long	addValue(Value value, long pointer) addValue adds a Value to the BTree and associates a pointer with it.
boolean	close() Close the underlying files.
void	closeAndRemove() Completely close down the instance and all underlying resources and caches.
boolean	create(short fixedKeyLen)
Paged.FileHeader	createFileHeader(int pageSize) createFileHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a FileHeader.
Paged.PageHeader	createPageHeader() createPageHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a PageHeader.
protected long	createRootNode(Txn transaction) Create the root node.
void	dump(java.io.Writer writer) Print a dump of the tree to the given writer.
protected void	dumpValue(java.io.Writer writer, Value value, int status)
long	findValue(Value value) findValue finds a Value in the BTree and returns the associated pointer for it.
boolean	flush()
short	getFileVersion()
BufferStats	getIndexBufferStats()
protected BTree.BTreeNode	getRootNode()
protected void	initCache()
boolean	open(short expectedVersion)
void	printStatistics()
void	query(IndexQuery query, BTreeCallback callback) query performs a query against the BTree and performs callback operations to report the search results.
void	query(IndexQuery query, Value prefix, BTreeCallback callback) Executes a query against the BTree and performs callback operations to report the search results.
void	rawScan(IndexQuery query, BTreeCallback callback)
protected void	redoCreateBTNode(CreateBTNodeLoggable loggable)
protected void	redoInsertValue(InsertValueLoggable loggable)
protected void	redoRemoveValue(RemoveValueLoggable loggable)
protected void	redoSetPageLink(SetPageLinkLoggable loggable)
protected void	redoSetParent(SetParentLoggable loggable)
protected void	redoUpdatePage(UpdatePageLoggable loggable)
protected void	redoUpdateValue(UpdateValueLoggable loggable)
void	remove(IndexQuery query, BTreeCallback callback)
void	remove(Txn transaction, IndexQuery query, BTreeCallback callback) Search for keys matching the given IndexQuery and remove them from the node.
protected void	removeSequential(Txn transaction, BTree.BTreeNode page, IndexQuery query, BTreeCallback callback)
long	removeValue(Txn transaction, Value value)
long	removeValue(Value value) removeValue removes a Value from the BTree and returns the associated pointer for it.
protected boolean	requiresRedo(Loggable loggable, Paged.Page page)
protected void	scanSequential(BTree.BTreeNode page, IndexQuery query, Value keyPrefix, BTreeCallback callback)
protected void	setRootNode(BTree.BTreeNode rootNode) Set the root node of the tree.
protected void	setSplitFactor(double factor)
TreeMetrics	treeStatistics()
protected void	undoInsertValue(InsertValueLoggable loggable)
protected void	undoRemoveValue(RemoveValueLoggable loggable)
protected void	undoUpdateValue(UpdateValueLoggable loggable)

Methods inherited from class org.exist.storage.btree.Paged

backupToStream, create, exists, getFile, getFileHeader, getFreePage, getFreePage, getPage, getPageSize, hexDump, isOpened, isReadOnly, printFreeSpaceList, reuseDeleted, setFile, setPageSize, unlinkPages, unlinkPages, writeValue, writeValue, writeValue

Methods inherited from class java.lang.Object

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

Field Detail

LOGSTATS

protected static final org.apache.log4j.Logger LOGSTATS

KEY_NOT_FOUND

public static final long KEY_NOT_FOUND

Used as return value, if a value was not found

See Also:

Constant Field Values

LEAF

protected static final byte LEAF

Type of BTreeNode/Page

See Also:

Constant Field Values

BRANCH

protected static final byte BRANCH

Type of BTreeNode/Page

See Also:

Constant Field Values

MIN_SPACE_PER_KEY

protected static final int MIN_SPACE_PER_KEY

See Also:

Constant Field Values

LOG_INSERT_VALUE

public static final byte LOG_INSERT_VALUE

Log entry type for an insert value operation

See Also:

Constant Field Values

LOG_CREATE_BNODE

public static final byte LOG_CREATE_BNODE

Log entry type for creation of a new btree node

See Also:

Constant Field Values

LOG_UPDATE_PAGE

public static final byte LOG_UPDATE_PAGE

Log entry type for a page update resulting from a page split

See Also:

Constant Field Values

LOG_SET_PARENT

public static final byte LOG_SET_PARENT

Log entry type for a parent page change resulting from a page split

See Also:

Constant Field Values

LOG_UPDATE_VALUE

public static final byte LOG_UPDATE_VALUE

Log entry type for a value update

See Also:

Constant Field Values

LOG_REMOVE_VALUE

public static final byte LOG_REMOVE_VALUE

Log entry type for removing a value

See Also:

Constant Field Values

LOG_SET_LINK

public static final byte LOG_SET_LINK

See Also:

Constant Field Values

cacheManager

protected DefaultCacheManager cacheManager

cache

protected Cache cache

Cache of BTreeNode(s)

growthThreshold

protected double growthThreshold

buffers

protected int buffers

Size of BTreeNode cache

logManager

protected Journal logManager

The LogManager for writing the transaction log

fileId

protected byte fileId

isTransactional

protected boolean isTransactional

pool

protected BrokerPool pool

Constructor Detail

BTree

protected BTree(BrokerPool pool,
                byte fileId,
                boolean transactional,
                DefaultCacheManager cacheManager,
                double growthThreshold)
         throws DBException

Throws:

DBException

BTree

public BTree(BrokerPool pool,
             byte fileId,
             boolean transactional,
             DefaultCacheManager cacheManager,
             java.io.File file,
             double growthThreshold)
      throws DBException

Throws:

DBException

Method Detail

getFileVersion

public short getFileVersion()

Specified by:

getFileVersion in class Paged

open

public boolean open(short expectedVersion)
             throws DBException

Overrides:

open in class Paged

Throws:

DBException

create

public boolean create(short fixedKeyLen)
               throws DBException

Throws:

DBException

initCache

protected void initCache()

closeAndRemove

public void closeAndRemove()

Description copied from class: Paged

Completely close down the instance and all underlying resources and caches.

Overrides:

closeAndRemove in class Paged

setSplitFactor

protected void setSplitFactor(double factor)

addValue

public long addValue(Value value,
                     long pointer)
              throws java.io.IOException,
                     BTreeException

addValue adds a Value to the BTree and associates a pointer with it. The pointer can be used for referencing any type of data, it just so happens that dbXML uses it for referencing pages of associated data in the BTree file or other files.

Parameters:

value - The Value to add

pointer - The pointer to associate with it

Returns:

The previous value for the pointer (or -1)

Throws:

java.io.IOException - Description of the Exception

BTreeException - Description of the Exception

addValue

public long addValue(Txn transaction,
                     Value value,
                     long pointer)
              throws java.io.IOException,
                     BTreeException

Throws:

java.io.IOException

BTreeException

removeValue

public long removeValue(Value value)
                 throws java.io.IOException,
                        BTreeException

removeValue removes a Value from the BTree and returns the associated pointer for it.

Parameters:

value - The Value to remove

Returns:

The pointer that was associated with it

Throws:

java.io.IOException - Description of the Exception

BTreeException - Description of the Exception

removeValue

public long removeValue(Txn transaction,
                        Value value)
                 throws java.io.IOException,
                        BTreeException

Throws:

java.io.IOException

BTreeException

findValue

public long findValue(Value value)
               throws java.io.IOException,
                      BTreeException

findValue finds a Value in the BTree and returns the associated pointer for it.

Parameters:

value - The Value to find

Returns:

The pointer that was associated with it

Throws:

java.io.IOException - Description of the Exception

BTreeException - Description of the Exception

query

public void query(IndexQuery query,
                  BTreeCallback callback)
           throws java.io.IOException,
                  BTreeException,
                  TerminatedException

query performs a query against the BTree and performs callback operations to report the search results.

Parameters:

query - The IndexQuery to use (or null for everything)

callback - The callback instance

Throws:

java.io.IOException - Description of the Exception

BTreeException - Description of the Exception

TerminatedException

query

public void query(IndexQuery query,
                  Value prefix,
                  BTreeCallback callback)
           throws java.io.IOException,
                  BTreeException,
                  TerminatedException

Executes a query against the BTree and performs callback operations to report the search results. This method takes an additional prefix value. Only BTree keys starting with the specified prefix are considered. Search through the tree is thus restricted to a given key range.

Parameters:

query - The IndexQuery to use (or null for everything)

prefix - a prefix value

callback - The callback instance

Throws:

java.io.IOException

BTreeException

TerminatedException

remove

public void remove(IndexQuery query,
                   BTreeCallback callback)
            throws java.io.IOException,
                   BTreeException,
                   TerminatedException

Throws:

java.io.IOException

BTreeException

TerminatedException

remove

public void remove(Txn transaction,
                   IndexQuery query,
                   BTreeCallback callback)
            throws java.io.IOException,
                   BTreeException,
                   TerminatedException

Search for keys matching the given IndexQuery and remove them from the node. Every match is reported to the specified BTreeCallback.

Parameters:

query -

callback -

Throws:

java.io.IOException

BTreeException

TerminatedException

removeSequential

protected void removeSequential(Txn transaction,
                                BTree.BTreeNode page,
                                IndexQuery query,
                                BTreeCallback callback)
                         throws TerminatedException

Throws:

TerminatedException

scanSequential

protected void scanSequential(BTree.BTreeNode page,
                              IndexQuery query,
                              Value keyPrefix,
                              BTreeCallback callback)
                       throws TerminatedException

Throws:

TerminatedException

setRootNode

protected void setRootNode(BTree.BTreeNode rootNode)
                    throws java.io.IOException

Set the root node of the tree.

Parameters:

rootNode -

Throws:

java.io.IOException

createRootNode

protected long createRootNode(Txn transaction)
                       throws java.io.IOException

Create the root node.

Parameters:

transaction -

Returns:

The root node

Throws:

java.io.IOException

getRootNode

protected BTree.BTreeNode getRootNode()

Returns:

the root node.

dump

public void dump(java.io.Writer writer)
          throws java.io.IOException,
                 BTreeException

Print a dump of the tree to the given writer. For debug only!

Parameters:

writer -

Throws:

java.io.IOException

BTreeException

treeStatistics

public TreeMetrics treeStatistics()
                           throws java.io.IOException

Throws:

java.io.IOException

flush

public boolean flush()
              throws DBException

Overrides:

flush in class Paged

Throws:

DBException

close

public boolean close()
              throws DBException

Description copied from class: Paged

Close the underlying files.

Overrides:

close in class Paged

Returns:

TRUE if closed.

Throws:

DBException

dumpValue

protected void dumpValue(java.io.Writer writer,
                         Value value,
                         int status)
                  throws java.io.IOException

Throws:

java.io.IOException

rawScan

public void rawScan(IndexQuery query,
                    BTreeCallback callback)
             throws java.io.IOException,
                    TerminatedException

Throws:

java.io.IOException

TerminatedException

requiresRedo

protected boolean requiresRedo(Loggable loggable,
                               Paged.Page page)

redoCreateBTNode

protected void redoCreateBTNode(CreateBTNodeLoggable loggable)
                         throws LogException

Throws:

LogException

redoInsertValue

protected void redoInsertValue(InsertValueLoggable loggable)
                        throws LogException

Throws:

LogException

undoInsertValue

protected void undoInsertValue(InsertValueLoggable loggable)
                        throws LogException

Throws:

LogException

redoUpdateValue

protected void redoUpdateValue(UpdateValueLoggable loggable)
                        throws LogException

Throws:

LogException

undoUpdateValue

protected void undoUpdateValue(UpdateValueLoggable loggable)
                        throws LogException

Throws:

LogException

redoRemoveValue

protected void redoRemoveValue(RemoveValueLoggable loggable)
                        throws LogException

Throws:

LogException

undoRemoveValue

protected void undoRemoveValue(RemoveValueLoggable loggable)
                        throws LogException

Throws:

LogException

redoUpdatePage

protected void redoUpdatePage(UpdatePageLoggable loggable)
                       throws LogException

Throws:

LogException

redoSetParent

protected void redoSetParent(SetParentLoggable loggable)
                      throws LogException

Throws:

LogException

redoSetPageLink

protected void redoSetPageLink(SetPageLinkLoggable loggable)
                        throws LogException

Throws:

LogException

createFileHeader

public Paged.FileHeader createFileHeader(int pageSize)

Description copied from class: Paged

createFileHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a FileHeader.

Specified by:

createFileHeader in class Paged

Returns:

a new FileHeader

See Also:

Paged.createFileHeader(int pageSize)

createPageHeader

public Paged.PageHeader createPageHeader()

Description copied from class: Paged

createPageHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a PageHeader.

Specified by:

createPageHeader in class Paged

Returns:

a new PageHeader

See Also:

Paged.createPageHeader()

getIndexBufferStats

public BufferStats getIndexBufferStats()

printStatistics

public void printStatistics()