dbXML API

## org.dbxml.core.filer
Class BTree

    java.lang.Object
      |
      +--org.dbxml.core.filer.Paged
            |
            +--org.dbxml.core.filer.BTree

Direct Known Subclasses:
  BTreeFiler, NameIndexer, ValueIndexer

public class BTree
extends Paged

BTree represents a Variable Magnitude Simple-Prefix B+Tree File. A BTree is a bit flexible in that it can be used for set or map-based indexing. HashFiler uses the BTree as a set for producing RecordSet entries. The Indexers use BTree as a map for indexing entity and attribute values in Documents.
For those who don't know how a Simple-Prefix B+Tree works, the primary distinction is that instead of promoting actual keys to branch pages, when leaves are split, a shortest-possible separator is generated at the pivot. That separator is what is promoted to the parent branch (and continuing up the list). As a result, actual keys and pointers can only be found at the leaf level. This also affords the index the ability to ignore costly merging and redistribution of pages when deletions occur. Deletions only affect leaf pages in this implementation, and so it is entirely possible for a leaf page to be completely empty after all of its keys have been removed.
Also, the Variable Magnitude attribute means that the btree attempts to store as many values and pointers on one page as is possible.
This implementation supports the notion of nested roots. This means that you can create a btree where the pointers actually point to the root of a separate btree being managed in the same file.

Inner Class Summary
`class` `BTree.BTreeRootInfo` BTreeRootInfo

Inner classes inherited from class org.dbxml.core.filer.Paged
`Paged.FileHeader, Paged.Page, Paged.PageHeader`

Constructor Summary
`BTree()`
`BTree(java.io.File file)`

Method Summary
`long` `addValue(BTree.BTreeRootInfo root, Value value, long pointer)` addValue adds a Value to the BTree and associates a pointer with it.
`long` `addValue(Value value, long pointer)` addValue adds a Value to the BTree and associates a pointer with it.
`boolean` `create()`
`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.
`long` `findValue(BTree.BTreeRootInfo root, Value value)` findValue finds a Value in the BTree and returns the associated pointer for it.
`long` `findValue(Value value)` findValue finds a Value in the BTree and returns the associated pointer for it.
`boolean` `open()`
`void` `query(BTree.BTreeRootInfo root, IndexQuery query, BTreeCallback callback)` query performs a query against the BTree and performs callback operations to report the search results.
`void` `query(IndexQuery query, BTreeCallback callback)` query performs a query against the BTree and performs callback operations to report the search results.
`long` `removeValue(BTree.BTreeRootInfo root, Value value)` removeValue removes a Value from the BTree and returns the associated pointer for it.
`long` `removeValue(Value value)` removeValue removes a Value from the BTree and returns the associated pointer for it.

Methods inherited from class org.dbxml.core.filer.Paged
`close, deleteArrayInt, deleteArrayLong, deleteArrayShort, deleteArrayValue, drop, exists, getFileHeader, insertArrayInt, insertArrayLong, insertArrayShort, insertArrayValue, isOpened`

Methods inherited from class java.lang.Object
`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

### BTree

    public BTree()

### BTree

    public BTree(java.io.File file)

Method Detail

### open

    public boolean open()
                 throws DBException

  Overrides:
    `open` in class `Paged`

### create

    public boolean create()
                   throws DBException

  Overrides:
    `create` 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)

### addValue

    public long addValue(BTree.BTreeRootInfo root,
                         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:
    `root` - The BTree's root information (for nested trees)
    `value` - The Value to add
    `pointer` - The pointer to associate with it
  Returns:
    The previous value for the pointer (or -1)

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

### removeValue

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

  removeValue removes a Value from the BTree and returns the associated pointer for it.
  Parameters:
    `root` - The BTree's root information (for nested trees)
    `value` - The Value to remove
  Returns:
    The pointer that was associated with it

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

### findValue

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

  findValue finds a Value in the BTree and returns the associated pointer for it.
  Parameters:
    `root` - The BTree's root information (for nested trees)
    `value` - The Value to find
  Returns:
    The pointer that was associated with it

### query

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

  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

### query

    public void query(BTree.BTreeRootInfo root,
                      IndexQuery query,
                      BTreeCallback callback)
               throws java.io.IOException,
                      BTreeException

  query performs a query against the BTree and performs callback operations to report the search results.
  Parameters:
    `root` - The BTree's root information (for nested trees)
    `query` - The IndexQuery to use (or null for everything)
    `callback` - The callback instance

### 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.
  Overrides:
    `createFileHeader` in class `Paged`
  Following copied from class: `org.dbxml.core.filer.Paged`
  Returns:
    a new FileHeader

### 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.
  Overrides:
    `createFileHeader` in class `Paged`
  Following copied from class: `org.dbxml.core.filer.Paged`
  Parameters:
    `read` - If true, reads the FileHeader from disk
  Returns:
    a new FileHeader
  Throws:
    `java.io.IOException` - if an exception occurs

### 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.
  Overrides:
    `createFileHeader` in class `Paged`
  Following copied from class: `org.dbxml.core.filer.Paged`
  Parameters:
    `pageCount` - The number of pages to allocate for primary storage
  Returns:
    a new FileHeader

### 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.
  Overrides:
    `createFileHeader` in class `Paged`
  Following copied from class: `org.dbxml.core.filer.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

### 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.
  Overrides:
    `createPageHeader` in class `Paged`
  Following copied from class: `org.dbxml.core.filer.Paged`
  Returns:
    a new PageHeader

dbXML API

Copyright (c) 1999-2001 The dbXML Group, All rights reserved