org.apache.xindice.core.filer
Class BTree

java.lang.Object
  |
  +--org.apache.xindice.core.filer.Paged
        |
        +--org.apache.xindice.core.filer.BTree

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

Inner Class Summary

class

BTree.BTreeRootInfo BTreeRootInfo

Inner classes inherited from class org.apache.xindice.core.filer.Paged

Paged.FileHeader, Paged.Page, Paged.PageHeader

Constructor Summary

BTree()

BTree(java.io.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()
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(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.
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.

Methods inherited from class org.apache.xindice.core.filer.Paged

close, deleteArrayInt, deleteArrayLong, deleteArrayShort, deleteArrayValue, drop, exists, flush, getFileHeader, insertArrayInt, insertArrayLong, insertArrayShort, insertArrayValue, isOpened

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BTree

public BTree()

BTree

public BTree(java.io.File file)

Method Detail

open

public boolean open()
             throws DBException

Overrides:

open in class Paged

create

public boolean create()
               throws DBException

Overrides:

create in class Paged

addValue

public long addValue(Value value,
                     long pointer)
              throws java.io.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)

addValue

public long addValue(BTree.BTreeRootInfo root,
                     Value value,
                     long pointer)
              throws java.io.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)

removeValue

public long removeValue(Value value)
                 throws java.io.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

removeValue

public long removeValue(BTree.BTreeRootInfo root,
                        Value value)
                 throws java.io.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

findValue

public long findValue(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

findValue

public long findValue(BTree.BTreeRootInfo root,
                      Value value)
               throws java.io.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

query

public void query(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

query

public void query(BTree.BTreeRootInfo root,
                  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:

root - The BTree's root information (for nested trees)

query - The IndexQuery to use (or null for everything)

callback - The callback instance

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.

Overrides:

createFileHeader in class Paged

Following copied from class: org.apache.xindice.core.filer.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.

Overrides:

createFileHeader in class Paged

Following copied from class: org.apache.xindice.core.filer.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.

Overrides:

createFileHeader in class Paged

Following copied from class: org.apache.xindice.core.filer.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.

Overrides:

createFileHeader in class Paged

Following copied from class: org.apache.xindice.core.filer.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.

Overrides:

createPageHeader in class Paged

Following copied from class: org.apache.xindice.core.filer.Paged

Returns:

a new PageHeader