org.exist.storage.btree
Class BTree

java.lang.Object
  extended by org.exist.storage.btree.Paged
      extended by 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
 
Nested classes/interfaces inherited from class org.exist.storage.btree.Paged
Paged.FileHeader, Paged.Page, Paged.PageHeader
 
Field Summary
static long KEY_NOT_FOUND
          Used as return value, if a value was not found
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
 
Fields inherited from class org.exist.storage.btree.Paged
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, 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
 
Constructor Summary
BTree(BrokerPool pool, byte fileId, boolean transactional, DefaultCacheManager cacheManager, 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.
 void dump(Writer writer)
          Print a dump of the tree to the given writer.
 long findValue(Value value)
          findValue finds a Value in the BTree and returns the associated pointer for it.
 boolean flush()
           
 short getFileVersion()
           
 BufferStats getIndexBufferStats()
           
 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 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.
 TreeMetrics treeStatistics()
           
 
Methods inherited from class org.exist.storage.btree.Paged
backupToStream, create, exists, getFile, getFileHeader, getPageSize, hexDump, isOpened, isReadOnly, printFreeSpaceList, setPageSize
 
Methods inherited from class java.lang.Object
equals, 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

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
Constructor Detail

BTree

public BTree(BrokerPool pool,
             byte fileId,
             boolean transactional,
             DefaultCacheManager cacheManager,
             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

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 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:
IOException - Description of the Exception
BTreeException - Description of the Exception

addValue

public long addValue(Txn transaction,
                     Value value,
                     long pointer)
              throws IOException,
                     BTreeException
Throws:
IOException
BTreeException

removeValue

public long removeValue(Value value)
                 throws 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:
IOException - Description of the Exception
BTreeException - Description of the Exception

removeValue

public long removeValue(Txn transaction,
                        Value value)
                 throws IOException,
                        BTreeException
Throws:
IOException
BTreeException

findValue

public long findValue(Value value)
               throws 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:
IOException - Description of the Exception
BTreeException - Description of the Exception

query

public void query(IndexQuery query,
                  BTreeCallback callback)
           throws 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:
IOException - Description of the Exception
BTreeException - Description of the Exception
TerminatedException

query

public void query(IndexQuery query,
                  Value prefix,
                  BTreeCallback callback)
           throws 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:
IOException
BTreeException
TerminatedException

remove

public void remove(IndexQuery query,
                   BTreeCallback callback)
            throws IOException,
                   BTreeException,
                   TerminatedException
Throws:
IOException
BTreeException
TerminatedException

remove

public void remove(Txn transaction,
                   IndexQuery query,
                   BTreeCallback callback)
            throws 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:
IOException
BTreeException
TerminatedException

dump

public void dump(Writer writer)
          throws IOException,
                 BTreeException
Print a dump of the tree to the given writer. For debug only!

Parameters:
writer -
Throws:
IOException
BTreeException

treeStatistics

public TreeMetrics treeStatistics()
                           throws IOException
Throws:
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

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


Copyright (C) Wolfgang Meier. All rights reserved.