|
||||||||||
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.
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)
|
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 IOException
Index
load
in interface Index<Key,Value>
IOException
public void unload(Transaction tx)
Index
unload
in interface Index<Key,Value>
public boolean containsKey(Transaction tx, Key key) throws IOException
containsKey
in interface Index<Key,Value>
IOException
public Value get(Transaction tx, Key key) throws IOException
get
in interface Index<Key,Value>
IOException
public Value put(Transaction tx, Key key, Value value) throws IOException
Index
put
in interface Index<Key,Value>
IOException
public Value remove(Transaction tx, Key key) throws IOException
Index
remove
in interface Index<Key,Value>
IOException
public boolean isTransient()
isTransient
in interface Index<Key,Value>
public void clear(Transaction tx) throws IOException
Index
clear
in interface Index<Key,Value>
IOException
public int getMinLeafDepth(Transaction tx) throws IOException
IOException
public int getMaxLeafDepth(Transaction tx) throws IOException
IOException
public void printStructure(Transaction tx, PrintWriter out) throws IOException
IOException
public void printStructure(Transaction tx, OutputStream out) throws IOException
IOException
public boolean isEmpty(Transaction tx) throws IOException
IOException
public Iterator<Map.Entry<Key,Value>> iterator(Transaction tx) throws IOException
iterator
in interface Index<Key,Value>
IOException
public Iterator<Map.Entry<Key,Value>> iterator(Transaction tx, Key initialKey) throws IOException
IOException
public void visit(Transaction tx, BTreeVisitor<Key,Value> visitor) throws IOException
IOException
public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException
IOException
public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException
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 |