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

java.lang.Object
  extended by 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: 2013-10-21 18:53:28 +0000 (Mon, 21 Oct 2013) $


Nested Class Summary
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
BTreeIndex()
           
BTreeIndex(long rootPageId)
           
BTreeIndex(Page page)
           
BTreeIndex(PageFile pageFile, long rootPageId)
           
BTreeIndex(PageFile pageFile, Page page)
           
 
Method Summary
 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)
           
 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

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)


Copyright © 2005–2013 The Apache Software Foundation. All rights reserved.