## 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

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.