org.exist.storage.btree
Class BTree

java.lang.Object
  extended byorg.exist.storage.btree.Paged
      extended byorg.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 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_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
 
Constructor Summary
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.
 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.
 void dump(java.io.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()
           
 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.
 
Methods inherited from class org.exist.storage.btree.Paged
backupToStream, create, exists, getFile, getFileHeader, getFileVersion, 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
Constructor Detail

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

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

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:
TRUE if closed.
Throws:
DBException

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


Copyright (C) Wolfgang Meier. All rights reserved.