JXTA

net.jxta.impl.xindice.core.filer
Class BTree

java.lang.Object
  extended by net.jxta.impl.xindice.core.filer.Paged
      extended by net.jxta.impl.xindice.core.filer.BTree
Direct Known Subclasses:
BTreeFiler, NameIndexer

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.


Nested Class Summary
protected  class BTree.BTreeFileHeader
          BTreeFileHeader
protected  class BTree.BTreePageHeader
          BTreePageHeader
 class BTree.BTreeRootInfo
          BTreeRootInfo
 
Nested classes/interfaces inherited from class net.jxta.impl.xindice.core.filer.Paged
Paged.FileHeader, Paged.Page, Paged.PageHeader
 
Field Summary
protected static byte BRANCH
           
protected static byte LEAF
           
protected static byte STREAM
           
 
Fields inherited from class net.jxta.impl.xindice.core.filer.Paged
DELETED, NO_PAGE, OVERFLOW, sync, UNUSED
 
Constructor Summary
BTree()
           
BTree(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()
           
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.
 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.
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  net.jxta.impl.xindice.core.filer.BTree.BTreeNode getRootNode()
          getRootNode retreives the BTree node for the file's root.
protected  net.jxta.impl.xindice.core.filer.BTree.BTreeNode getRootNode(BTree.BTreeRootInfo root)
          getRootNode retreives the BTree node for the specified root object.
 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.
protected  void setRootNode(net.jxta.impl.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, net.jxta.impl.xindice.core.filer.BTree.BTreeNode newRoot)
          setRootNode resets the root for the specified root object to the provided BTreeNode's page number.
 void setSync(boolean sync)
          Setting this option forces all system buffers with the underlying device if sync is set writes return after all modified data and attributes of the DB have been written to the device.
 
Methods inherited from class net.jxta.impl.xindice.core.filer.Paged
addDirty, checkOpened, close, closeDescriptor, deleteArrayInt, deleteArrayLong, deleteArrayShort, deleteArrayValue, drop, exists, flush, getDescriptor, getFile, getFileHeader, getFreePage, getPage, insertArrayInt, insertArrayLong, insertArrayShort, insertArrayValue, isOpened, putDescriptor, readValue, readValue, 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

setSync

public void setSync(boolean sync)
Setting this option forces all system buffers with the underlying device if sync is set writes return after all modified data and attributes of the DB have been written to the device. by default sync is true. FileDescriptor

Parameters:
sync - if true, invokes FD.sync(), an expensive operation, required to ensure high consistency, especially with system failures.

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 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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

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 - if an io error occurs
BTreeException - if a DB exception occurs

setRootNode

protected final void setRootNode(BTree.BTreeRootInfo root,
                                 net.jxta.impl.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 - if an io error occurs
BTreeException - if a DB exception occurs

setRootNode

protected final void setRootNode(net.jxta.impl.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 - if an io error occurs
BTreeException - if a DB exception occurs

getRootNode

protected final net.jxta.impl.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 net.jxta.impl.xindice.core.filer.BTree.BTreeNode getRootNode()
getRootNode retreives the BTree node for the file's root.

Returns:
The root node

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

JXSE