dbXML API

com.dbxml.db.common.btree
Class BTree

java.lang.Object
  extended bycom.dbxml.db.common.btree.Paged
      extended bycom.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

dbXML API

Copyright (c) 2004 The dbXML Group