|
Xindice API version 1.1 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--org.apache.xindice.core.filer.Paged | +--org.apache.xindice.core.filer.BTree
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.
Inner Class Summary | |
protected class |
BTree.BTreeFileHeader
BTreeFileHeader |
protected class |
BTree.BTreePageHeader
BTreePageHeader |
class |
BTree.BTreeRootInfo
BTreeRootInfo |
Inner 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 |
protected static final byte LEAF
protected static final byte BRANCH
protected static final byte STREAM
Constructor Detail |
public BTree()
public BTree(File file)
Method Detail |
public boolean open() throws DBException
DBObject
open
in class Paged
org.apache.xindice.core.DBObject
public boolean create() throws DBException
DBObject
create
in class Paged
org.apache.xindice.core.DBObject
public boolean close() throws DBException
DBObject
close
in class Paged
org.apache.xindice.core.DBObject
public long addKey(Value value) throws IOException, BTreeException
value
- The Value to addpublic long addValue(Value value, long pointer) throws IOException, BTreeException
value
- The Value to addpointer
- The pointer to associate with itpublic long addValue(BTree.BTreeRootInfo root, Value value, long pointer) throws IOException, BTreeException
root
- The BTree's root information (for nested trees)value
- The Value to addpointer
- The pointer to associate with itpublic long removeValue(Value value) throws IOException, BTreeException
value
- The Value to removepublic long removeValue(BTree.BTreeRootInfo root, Value value) throws IOException, BTreeException
root
- The BTree's root information (for nested trees)value
- The Value to removepublic long findValue(Value value) throws IOException, BTreeException
value
- The Value to findpublic long findValue(BTree.BTreeRootInfo root, Value value) throws IOException, BTreeException
root
- The BTree's root information (for nested trees)value
- The Value to findpublic void query(IndexQuery query, BTreeCallback callback) throws IOException, BTreeException
query
- The IndexQuery to use (or null for everything)callback
- The callback instancepublic void query(BTree.BTreeRootInfo root, IndexQuery query, BTreeCallback callback) throws IOException, BTreeException
root
- The BTree's root information (for nested trees)query
- The IndexQuery to use (or null for everything)callback
- The callback instanceprotected final BTree.BTreeRootInfo createBTreeRoot(Value v) throws IOException, BTreeException
v
- The sub-tree Value to createprotected final BTree.BTreeRootInfo createBTreeRoot(BTree.BTreeRootInfo root, Value v) throws IOException, BTreeException
root
- The BTreeRootInfo to build off ofv
- The sub-tree Value to createprotected final BTree.BTreeRootInfo findBTreeRoot(Value v) throws IOException, BTreeException
v
- The sub-tree Value to search forprotected final BTree.BTreeRootInfo findBTreeRoot(BTree.BTreeRootInfo root, Value v) throws IOException, BTreeException
root
- The BTreeRootInfo to search fromv
- The sub-tree Value to search forprotected final void setRootNode(BTree.BTreeRootInfo root, org.apache.xindice.core.filer.BTree.BTreeNode newRoot) throws IOException, BTreeException
root
- The root to resetnewRoot
- the new root node to useprotected final void setRootNode(org.apache.xindice.core.filer.BTree.BTreeNode rootNode) throws IOException, BTreeException
rootNode
- the new root node to useprotected final org.apache.xindice.core.filer.BTree.BTreeNode getRootNode(BTree.BTreeRootInfo root)
root
- The root object to retrieve withprotected final org.apache.xindice.core.filer.BTree.BTreeNode getRootNode()
protected Paged.FileHeader createFileHeader()
Paged
createFileHeader
in class Paged
org.apache.xindice.core.filer.Paged
protected Paged.PageHeader createPageHeader()
Paged
createPageHeader
in class Paged
org.apache.xindice.core.filer.Paged
|
Xindice API version 1.1 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |