Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| dbXML API
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## com.dbxml.db.common.btree
Class BTree

    java.lang.Object
      com.dbxml.db.common.btree.Paged
          com.dbxml.db.common.btree.BTree

All Implemented Interfaces:
  Configurable

Direct Known Subclasses:
  BTreeFiler, FullTextIndexer, 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. 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 possible. When storing values, the largest common prefix between the values is stored only once at the beginning of the page, with the remaining value content being stored in the individual entries. This method is highly efficient for tight sequences and highly redundant values.

Nested Class Summary

Nested classes inherited from class com.dbxml.db.common.btree.Paged
`Paged.FileHeader, Paged.Page, Paged.PageHeader`

Constructor Summary
`BTree(boolean compoundKeys)`
`BTree(java.io.File file, boolean compoundKeys)`

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

Methods inherited from class com.dbxml.db.common.btree.Paged
`addPageFilter, close, deleteArrayValue, drop, exists, flush, getConfig, getFileHeader, getTransactionLog, insertArrayValue, isOpened, listPageFilters, removePageFilter, setConfig`

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

Constructor Detail

### BTree

    public BTree(boolean compoundKeys)

### BTree

    public BTree(java.io.File file,
                 boolean compoundKeys)

Method Detail

### open

    public boolean open()
                 throws DBException

  Overrides:
    `open` in class `Paged`
  Throws:
    `DBException`

### create

    public boolean create()
                   throws DBException

  Overrides:
    `create` in class `Paged`
  Throws:
    `DBException`

### addValue

    public final long addValue(Transaction tx,
                               Value value,
                               long pointer)
                        throws DBException,
                               java.io.IOException

  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:
    `DBException`
    `java.io.IOException`

### removeValue

    public final long removeValue(Transaction tx,
                                  Value value)
                           throws DBException,
                                  java.io.IOException

  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:
    `DBException`
    `java.io.IOException`

### findValue

    public final long findValue(Transaction tx,
                                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`
    `BTreeException`

### query

    public final void query(Transaction tx,
                            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
  Throws:
    `java.io.IOException`
    `BTreeException`

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

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

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

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

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

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| dbXML API
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright (c) 2004 The dbXML Group