org.exist.storage.btree
Class BTree

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

Direct Known Subclasses:

BFile, 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 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 CacheManager	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_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

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

DELETED, LOG, OVERFLOW, PAGE_SIZE, UNUSED

Constructor Summary

protected	BTree(BrokerPool pool, byte fileId, boolean transactional, CacheManager cacheManager, double growthThreshold)
	BTree(BrokerPool pool, byte fileId, boolean transactional, CacheManager 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.
protected boolean	create(short fixedKeyLen)
Paged.FileHeader	createFileHeader() createFileHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a FileHeader.
Paged.FileHeader	createFileHeader(boolean read) createFileHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a FileHeader.
Paged.FileHeader	createFileHeader(long pageCount) createFileHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a FileHeader.
Paged.FileHeader	createFileHeader(long pageCount, 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)
long	findValue(Value value) findValue finds a Value in the BTree and returns the associated pointer for it.
boolean	flush()
BufferStats	getIndexBufferStats()
protected BTree.BTreeNode	getRootNode()
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.
protected void	redoCreateBTNode(CreateBTNodeLoggable loggable)
protected void	redoInsertValue(InsertValueLoggable loggable)
protected void	redoRemoveValue(RemoveValueLoggable 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.
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	setRootNode(BTree.BTreeNode rootNode) Set the root node of the tree.
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, getFileVersion, 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

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

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

cacheManager

protected CacheManager 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

Constructor Detail

BTree

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

BTree

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

Method Detail

open

public boolean open(short expectedVersion)
             throws DBException

Overrides:

open in class Paged

Throws:

DBException

create

protected boolean create(short fixedKeyLen)
                  throws DBException

Throws:

DBException

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

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

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:

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

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:

Throws:

DBException

dumpValue

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

Throws:

java.io.IOException

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

createFileHeader

public Paged.FileHeader createFileHeader()

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()

createFileHeader

public Paged.FileHeader createFileHeader(boolean read)
                                  throws java.io.IOException

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

Parameters:

read - If true, reads the FileHeader from disk

Returns:

a new FileHeader

Throws:

java.io.IOException - if an exception occurs

See Also:

Paged.createFileHeader(boolean)

createFileHeader

public Paged.FileHeader createFileHeader(long pageCount)

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

Parameters:

pageCount - The number of pages to allocate for primary storage

Returns:

a new FileHeader

See Also:

Paged.createFileHeader(long)

createFileHeader

public Paged.FileHeader createFileHeader(long pageCount,
                                         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

Parameters:

pageCount - The number of pages to allocate for primary storage

pageSize - The size of a Page (should be a multiple of a FS block)

Returns:

a new FileHeader

See Also:

Paged.createFileHeader(long, int)

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()