|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.kahadb.index.BTreeIndex<Key,Value>
public class BTreeIndex<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: 2011-02-16 14:58:54 +0100 (mer. 16 févr. 2011) $
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)
|
java.util.Map.Entry<Key,Value> |
getFirst(Transaction tx)
|
Marshaller<Key> |
getKeyMarshaller()
|
java.util.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()
|
java.util.Iterator<java.util.Map.Entry<Key,Value>> |
iterator(Transaction tx)
|
java.util.Iterator<java.util.Map.Entry<Key,Value>> |
iterator(Transaction tx,
Key initialKey)
|
void |
load(Transaction tx)
load indexes |
void |
printStructure(Transaction tx,
java.io.OutputStream out)
|
void |
printStructure(Transaction tx,
java.io.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 |
---|
public BTreeIndex()
public BTreeIndex(long rootPageId)
public BTreeIndex(Page page)
public BTreeIndex(PageFile pageFile, long rootPageId)
public BTreeIndex(PageFile pageFile, Page page)
Method Detail |
---|
public void load(Transaction tx) throws java.io.IOException
Index
load
in interface Index<Key,Value>
java.io.IOException
public void unload(Transaction tx)
Index
unload
in interface Index<Key,Value>
public boolean containsKey(Transaction tx, Key key) throws java.io.IOException
containsKey
in interface Index<Key,Value>
java.io.IOException
public Value get(Transaction tx, Key key) throws java.io.IOException
get
in interface Index<Key,Value>
java.io.IOException
public Value put(Transaction tx, Key key, Value value) throws java.io.IOException
Index
put
in interface Index<Key,Value>
java.io.IOException
public Value remove(Transaction tx, Key key) throws java.io.IOException
Index
remove
in interface Index<Key,Value>
java.io.IOException
public boolean isTransient()
isTransient
in interface Index<Key,Value>
public void clear(Transaction tx) throws java.io.IOException
Index
clear
in interface Index<Key,Value>
java.io.IOException
public int getMinLeafDepth(Transaction tx) throws java.io.IOException
java.io.IOException
public int getMaxLeafDepth(Transaction tx) throws java.io.IOException
java.io.IOException
public void printStructure(Transaction tx, java.io.PrintWriter out) throws java.io.IOException
java.io.IOException
public void printStructure(Transaction tx, java.io.OutputStream out) throws java.io.IOException
java.io.IOException
public boolean isEmpty(Transaction tx) throws java.io.IOException
java.io.IOException
public java.util.Iterator<java.util.Map.Entry<Key,Value>> iterator(Transaction tx) throws java.io.IOException
iterator
in interface Index<Key,Value>
java.io.IOException
public java.util.Iterator<java.util.Map.Entry<Key,Value>> iterator(Transaction tx, Key initialKey) throws java.io.IOException
java.io.IOException
public void visit(Transaction tx, BTreeVisitor<Key,Value> visitor) throws java.io.IOException
java.io.IOException
public java.util.Map.Entry<Key,Value> getFirst(Transaction tx) throws java.io.IOException
java.io.IOException
public java.util.Map.Entry<Key,Value> getLast(Transaction tx) throws java.io.IOException
java.io.IOException
public PageFile getPageFile()
public long getPageId()
public Marshaller<Key> getKeyMarshaller()
public void setKeyMarshaller(Marshaller<Key> keyMarshaller)
Index
setKeyMarshaller
in interface Index<Key,Value>
public Marshaller<Value> getValueMarshaller()
public void setValueMarshaller(Marshaller<Value> valueMarshaller)
Index
setValueMarshaller
in interface Index<Key,Value>
public BTreeIndex.Prefixer<Key> getPrefixer()
public void setPrefixer(BTreeIndex.Prefixer<Key> prefixer)
public void setPageFile(PageFile pageFile)
public void setPageId(long pageId)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |