Xindice API
version 1.2m1

org.apache.xindice.core.filer
Class BTree

java.lang.Object
  extended byorg.apache.xindice.core.filer.Paged
      extended byorg.apache.xindice.core.filer.BTree
All Implemented Interfaces:
Configurable, DBObject
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. BTreeFiler 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.

Version:
$Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007) $

Nested Class Summary
protected  class BTree.BTreeFileHeader
          BTreeFileHeader
protected  class BTree.BTreePageHeader
          BTreePageHeader
 class BTree.BTreeRootInfo
          BTreeRootInfo
 
Nested classes inherited from class org.apache.xindice.core.filer.Paged
Paged.FileHeader, Paged.Page, Paged.PageHeader, Paged.PageKey
 
Field Summary
protected static byte BRANCH
           
protected static byte LEAF
           
protected static byte STREAM
           
 
Fields inherited from class org.apache.xindice.core.filer.Paged
CONFIG_DESCRIPTORS_MAX, CONFIG_KEYSIZE_MAX, CONFIG_PAGECOUNT, CONFIG_PAGESIZE, DELETED, NO_PAGE, OVERFLOW, UNUSED
 
Constructor Summary
BTree()
           
BTree(File file)
           
 
Method Summary
 long addKey(Value value)
          addKey adds a Value to the BTree and associates a pointer with it.
 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 close()
          close closes the DBObject
 boolean create()
          create creates a new DBObject and any associated resources for the new DBObject, such as disk files, etc.
protected  BTree.BTreeRootInfo createBTreeRoot(BTree.BTreeRootInfo root, Value v)
          createBTreeRoot creates a new BTree root node in the BTree file based on the provided root information, and value for the tree.
protected  BTree.BTreeRootInfo createBTreeRoot(Value v)
          createBTreeRoot creates a new BTree root node in the BTree file based on the provided value for the main tree.
protected  Paged.FileHeader createFileHeader()
          createFileHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a FileHeader.
protected  Paged.PageHeader createPageHeader()
          createPageHeader must be implemented by a Paged implementation in order to create an appropriate subclass instance of a PageHeader.
protected  BTree.BTreeRootInfo findBTreeRoot(BTree.BTreeRootInfo root, Value v)
          findBTreeRoot searches for a BTreeRoot in the file and returns the BTreeRootInfo for the specified value based on the provided BTreeRootInfo value.
protected  BTree.BTreeRootInfo findBTreeRoot(Value v)
          findBTreeRoot searches for a BTreeRoot in the file and returns the BTreeRootInfo for the specified value based on the main tree.
 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.
protected  org.apache.xindice.core.filer.BTree.BTreeNode getRootNode()
          getRootNode retreives the BTree node for the file's root.
protected  org.apache.xindice.core.filer.BTree.BTreeNode getRootNode(BTree.BTreeRootInfo root)
          getRootNode retreives the BTree node for the specified root object.
 boolean open()
          open opens the DBObject
 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.
protected  void setRootNode(org.apache.xindice.core.filer.BTree.BTreeNode rootNode)
          setRootNode resets the file's root to the provided BTreeNode's page number.
protected  void setRootNode(BTree.BTreeRootInfo root, org.apache.xindice.core.filer.BTree.BTreeNode newRoot)
          setRootNode resets the root for the specified root object to the provided BTreeNode's page number.
 
Methods inherited from class org.apache.xindice.core.filer.Paged
checkOpened, closeDescriptor, deleteArrayInt, deleteArrayLong, deleteArrayShort, deleteArrayValue, drop, exists, flush, getConfig, getDescriptor, getFile, getFileHeader, getFreePage, getPage, insertArrayInt, insertArrayLong, insertArrayShort, insertArrayValue, isOpened, putDescriptor, readValue, readValue, setConfig, setFile, unlinkPages, unlinkPages, writeValue, writeValue
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

LEAF

protected static final byte LEAF
See Also:
Constant Field Values

BRANCH

protected static final byte BRANCH
See Also:
Constant Field Values

STREAM

protected static final byte STREAM
See Also:
Constant Field Values
Constructor Detail

BTree

public BTree()

BTree

public BTree(File file)
Method Detail

open

public boolean open()
             throws DBException
Description copied from interface: DBObject
open opens the DBObject

Specified by:
open in interface DBObject
Overrides:
open in class Paged
Throws:
DBException

create

public boolean create()
               throws DBException
Description copied from interface: DBObject
create creates a new DBObject and any associated resources for the new DBObject, such as disk files, etc.

Specified by:
create in interface DBObject
Overrides:
create in class Paged
Throws:
DBException

close

public boolean close()
              throws DBException
Description copied from interface: DBObject
close closes the DBObject

Specified by:
close in interface DBObject
Overrides:
close in class Paged
Throws:
DBException

addKey

public long addKey(Value value)
            throws IOException,
                   BTreeException
addKey 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 Xindice uses it for referencing pages of associated data in the BTree file or other files.

Parameters:
value - The Value to add
Returns:
Pointer to the value
Throws:
IOException
BTreeException

addValue

public long addValue(Value value,
                     long pointer)
              throws 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 Xindice 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:
IOException
BTreeException

addValue

public long addValue(BTree.BTreeRootInfo root,
                     Value value,
                     long pointer)
              throws 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 Xindice 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)
Throws:
IOException
BTreeException

removeValue

public long removeValue(Value value)
                 throws 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:
IOException
BTreeException

removeValue

public long removeValue(BTree.BTreeRootInfo root,
                        Value value)
                 throws 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
Throws:
IOException
BTreeException

findValue

public long findValue(Value value)
               throws 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:
IOException
BTreeException

findValue

public long findValue(BTree.BTreeRootInfo root,
                      Value value)
               throws 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
Throws:
IOException
BTreeException

query

public void query(IndexQuery query,
                  BTreeCallback callback)
           throws 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:
IOException
BTreeException

query

public void query(BTree.BTreeRootInfo root,
                  IndexQuery query,
                  BTreeCallback callback)
           throws 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
Throws:
IOException
BTreeException

createBTreeRoot

protected final BTree.BTreeRootInfo createBTreeRoot(Value v)
                                             throws IOException,
                                                    BTreeException
createBTreeRoot creates a new BTree root node in the BTree file based on the provided value for the main tree.

Parameters:
v - The sub-tree Value to create
Returns:
The new BTreeRootInfo instance
Throws:
IOException
BTreeException

createBTreeRoot

protected final BTree.BTreeRootInfo createBTreeRoot(BTree.BTreeRootInfo root,
                                                    Value v)
                                             throws IOException,
                                                    BTreeException
createBTreeRoot creates a new BTree root node in the BTree file based on the provided root information, and value for the tree.

Parameters:
root - The BTreeRootInfo to build off of
v - The sub-tree Value to create
Returns:
The new BTreeRootInfo instance
Throws:
IOException
BTreeException

findBTreeRoot

protected final BTree.BTreeRootInfo findBTreeRoot(Value v)
                                           throws IOException,
                                                  BTreeException
findBTreeRoot searches for a BTreeRoot in the file and returns the BTreeRootInfo for the specified value based on the main tree.

Parameters:
v - The sub-tree Value to search for
Returns:
The new BTreeRootInfo instance
Throws:
IOException
BTreeException

findBTreeRoot

protected final BTree.BTreeRootInfo findBTreeRoot(BTree.BTreeRootInfo root,
                                                  Value v)
                                           throws IOException,
                                                  BTreeException
findBTreeRoot searches for a BTreeRoot in the file and returns the BTreeRootInfo for the specified value based on the provided BTreeRootInfo value.

Parameters:
root - The BTreeRootInfo to search from
v - The sub-tree Value to search for
Returns:
The new BTreeRootInfo instance
Throws:
IOException
BTreeException

setRootNode

protected final void setRootNode(BTree.BTreeRootInfo root,
                                 org.apache.xindice.core.filer.BTree.BTreeNode newRoot)
                          throws IOException,
                                 BTreeException
setRootNode resets the root for the specified root object to the provided BTreeNode's page number. This method is not thread safe.

Parameters:
root - The root to reset
newRoot - the new root node to use
Throws:
IOException
BTreeException

setRootNode

protected final void setRootNode(org.apache.xindice.core.filer.BTree.BTreeNode rootNode)
                          throws IOException,
                                 BTreeException
setRootNode resets the file's root to the provided BTreeNode's page number. This method is not thread safe.

Parameters:
rootNode - the new root node to use
Throws:
IOException
BTreeException

getRootNode

protected final org.apache.xindice.core.filer.BTree.BTreeNode getRootNode(BTree.BTreeRootInfo root)
getRootNode retreives the BTree node for the specified root object.

Parameters:
root - The root object to retrieve with
Returns:
The root node

getRootNode

protected final org.apache.xindice.core.filer.BTree.BTreeNode getRootNode()
getRootNode retreives the BTree node for the file's root.

Returns:
The root node

createFileHeader

protected 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

createPageHeader

protected 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

Xindice API
version 1.2m1

Copyright (c) 1999-2007 The Apache Software Foundation. All Rights Reserved.