org.apache.activemq.store.kahadb.disk.index

Class BTreeIndex<Key,Value>

java.lang.Object

org.apache.activemq.store.kahadb.disk.index.BTreeIndex<Key,Value>

All Implemented Interfaces:

Index<Key,Value>

public class BTreeIndex<Key,Value>
extends Object
implements Index<Key,Value>

BTreeIndex represents a Variable Magnitude B+Tree in a Page File. A BTree is a bit flexible in that it can be used for set or map-based indexing. Leaf nodes are linked together for faster iteration of the values.
The Variable Magnitude attribute means that the BTree attempts to store as many values and pointers on one page as is possible.
The implementation can optionally a be Simple-Prefix B+Tree.
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. , $Date$

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	BTreeIndex.Prefixer<Key> Interface used to determine the simple prefix of two keys.
static class	BTreeIndex.StringPrefixer StringPrefixer is a Prefixer implementation that works on strings.

Constructor Summary

Constructors

Constructor and Description
BTreeIndex()
BTreeIndex(long rootPageId)
BTreeIndex(Page page)
BTreeIndex(PageFile pageFile, long rootPageId)
BTreeIndex(PageFile pageFile, Page page)

Method Summary

Modifier and Type	Method and Description
void	clear(Transaction tx) clear the index
boolean	containsKey(Transaction tx, Key key)
Value	get(Transaction tx, Key key)
Map.Entry<Key,Value>	getFirst(Transaction tx)
Marshaller<Key>	getKeyMarshaller()
Map.Entry<Key,Value>	getLast(Transaction tx)
int	getMaxLeafDepth(Transaction tx)
int	getMinLeafDepth(Transaction tx)
PageFile	getPageFile()
long	getPageId()
BTreeIndex.Prefixer<Key>	getPrefixer()
Marshaller<Value>	getValueMarshaller()
boolean	isEmpty(Transaction tx)
boolean	isTransient()
Iterator<Map.Entry<Key,Value>>	iterator(Transaction tx)
Iterator<Map.Entry<Key,Value>>	iterator(Transaction tx, Key initialKey)
Iterator<Map.Entry<Key,Value>>	iterator(Transaction tx, Key initialKey, Key maxKey)
void	load(Transaction tx) load indexes
void	printStructure(Transaction tx, OutputStream out)
void	printStructure(Transaction tx, PrintWriter out)
Value	put(Transaction tx, Key key, Value value) store the key, item
Value	remove(Transaction tx, Key key) remove the index key
void	setKeyMarshaller(Marshaller<Key> keyMarshaller) Set the marshaller for key objects
void	setPageFile(PageFile pageFile)
void	setPageId(long pageId)
void	setPrefixer(BTreeIndex.Prefixer<Key> prefixer)
void	setValueMarshaller(Marshaller<Value> valueMarshaller) Set the marshaller for key objects
void	unload(Transaction tx) unload indexes
void	visit(Transaction tx, BTreeVisitor<Key,Value> visitor)

Methods inherited from class java.lang.Object

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

Constructor Detail

BTreeIndex

public BTreeIndex()

BTreeIndex

public BTreeIndex(long rootPageId)

BTreeIndex

public BTreeIndex(Page page)

BTreeIndex

public BTreeIndex(PageFile pageFile,
                  long rootPageId)

BTreeIndex

public BTreeIndex(PageFile pageFile,
                  Page page)

Method Detail

load

public void load(Transaction tx)
          throws IOException

Description copied from interface: Index

load indexes

Specified by:

load in interface Index<Key,Value>

Throws:

IOException

unload

public void unload(Transaction tx)

Description copied from interface: Index

unload indexes

Specified by:

unload in interface Index<Key,Value>

containsKey

public boolean containsKey(Transaction tx,
                           Key key)
                    throws IOException

Specified by:

containsKey in interface Index<Key,Value>

Returns:

true if it contains the key

Throws:

IOException

get

public Value get(Transaction tx,
                 Key key)
          throws IOException

Specified by:

get in interface Index<Key,Value>

Returns:

the entry

Throws:

IOException

put

public Value put(Transaction tx,
                 Key key,
                 Value value)
          throws IOException

Description copied from interface: Index

store the key, item

Specified by:

put in interface Index<Key,Value>

Throws:

IOException

remove

public Value remove(Transaction tx,
                    Key key)
             throws IOException

Description copied from interface: Index

remove the index key

Specified by:

remove in interface Index<Key,Value>

Returns:

StoreEntry removed

Throws:

IOException

isTransient

public boolean isTransient()

Specified by:

isTransient in interface Index<Key,Value>

Returns:

true if the index is transient

clear

public void clear(Transaction tx)
           throws IOException

Description copied from interface: Index

clear the index

Specified by:

clear in interface Index<Key,Value>

Throws:

IOException

getMinLeafDepth

public int getMinLeafDepth(Transaction tx)
                    throws IOException

Throws:

IOException

getMaxLeafDepth

public int getMaxLeafDepth(Transaction tx)
                    throws IOException

Throws:

IOException

printStructure

public void printStructure(Transaction tx,
                           PrintWriter out)
                    throws IOException

Throws:

IOException

printStructure

public void printStructure(Transaction tx,
                           OutputStream out)
                    throws IOException

Throws:

IOException

isEmpty

public boolean isEmpty(Transaction tx)
                throws IOException

Throws:

IOException

iterator

public Iterator<Map.Entry<Key,Value>> iterator(Transaction tx)
                                        throws IOException

Specified by:

iterator in interface Index<Key,Value>

Returns:

Throws:

IOException

iterator

public Iterator<Map.Entry<Key,Value>> iterator(Transaction tx,
                                               Key initialKey)
                                        throws IOException

Throws:

IOException

iterator

public Iterator<Map.Entry<Key,Value>> iterator(Transaction tx,
                                               Key initialKey,
                                               Key maxKey)
                                        throws IOException

Throws:

IOException

visit

public void visit(Transaction tx,
                  BTreeVisitor<Key,Value> visitor)
           throws IOException

Throws:

IOException

getFirst

public Map.Entry<Key,Value> getFirst(Transaction tx)
                              throws IOException

Throws:

IOException

getLast

public Map.Entry<Key,Value> getLast(Transaction tx)
                             throws IOException

Throws:

IOException

getPageFile

public PageFile getPageFile()

getPageId

public long getPageId()

getKeyMarshaller

public Marshaller<Key> getKeyMarshaller()

setKeyMarshaller

public void setKeyMarshaller(Marshaller<Key> keyMarshaller)

Description copied from interface: Index

Set the marshaller for key objects

Specified by:

setKeyMarshaller in interface Index<Key,Value>

getValueMarshaller

public Marshaller<Value> getValueMarshaller()

setValueMarshaller

public void setValueMarshaller(Marshaller<Value> valueMarshaller)

Description copied from interface: Index

Set the marshaller for key objects

Specified by:

setValueMarshaller in interface Index<Key,Value>

getPrefixer

public BTreeIndex.Prefixer<Key> getPrefixer()

setPrefixer

public void setPrefixer(BTreeIndex.Prefixer<Key> prefixer)

setPageFile

public void setPageFile(PageFile pageFile)

setPageId

public void setPageId(long pageId)