| Package | Description |
|---|---|
| org.apache.directory.mavibot.btree |
| Modifier and Type | Class and Description |
|---|---|
(package private) class |
AbstractBTree<K,V>
A BTree abstract class containing the methods shared by the PersistedBTree or the InMemoryBTree
implementations.
|
(package private) class |
InMemoryBTree<K,V>
The B+Tree MVCC data structure.
|
class |
PersistedBTree<K,V>
The B+Tree MVCC data structure.
|
| Modifier and Type | Field and Description |
|---|---|
protected BTree<K,V> |
PageHolder.btree
The BTree
|
protected BTree<K,V> |
AbstractPage.btree
Parent B+Tree.
|
private BTree<K,V> |
BTreeHeader.btree
The B-tree this header is associated with
|
(package private) BTree<NameRevision,java.lang.Long> |
RecordManager.btreeOfBtrees
The B-tree of B-trees
|
(package private) BTree<RevisionName,long[]> |
RecordManager.copiedPageBtree
A B-tree used to manage the page that has been copied in a new version.
|
private BTree<?,V> |
PersistedBTreeConfiguration.parentBTree
The inherited B-tree if we create a sub B-tree
|
protected BTree<V,V> |
AbstractValueHolder.valueBtree
The BTree storing multiple value, if we have more than one value
|
private BTree<V,V> |
ValueBTreeCursor.valueBtree
The Value sub-btree
|
| Modifier and Type | Field and Description |
|---|---|
private java.util.Map<java.lang.String,BTree<java.lang.Object,java.lang.Object>> |
RecordManager.managedBtrees
The set of managed B-trees
|
| Modifier and Type | Method and Description |
|---|---|
<K,V> BTree<K,V> |
RecordManager.addBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
boolean allowDuplicates)
Creates a B-tree and automatically adds it to the list of managed btrees
|
BTree<K,V> |
InMemoryBTreeBuilder.build(java.util.Iterator<Tuple<K,V>> sortedTupleItr) |
BTree<K,V> |
PersistedBTreeBuilder.build(java.util.Iterator<Tuple<K,V>> sortedTupleItr) |
private BTree<V,V> |
PersistedValueHolder.build(PersistedBTree<V,V> btree,
V[] dupKeyValues)
Constructs the sub-BTree using bulkload instead of performing sequential inserts.
|
private static <K,V> BTree<K,V> |
BulkLoader.bulkLoad(BTree<K,V> btree,
java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator,
int nbElems)
Construct the target BTree from the sorted data.
|
private static <K,V> BTree<K,V> |
BulkLoader.bulkLoadSinglePage(BTree<K,V> btree,
java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator,
int nbElems) |
static BTree<?,?> |
BulkLoader.compact(BTree<?,?> btree)
Compact a given in-memory BTree, making it dense.
|
static <K,V> BTree<K,V> |
BTreeFactory.createInMemoryBTree()
Creates a new in-memory B-tree, with no initialization.
|
static <K,V> BTree<K,V> |
BTreeFactory.createInMemoryBTree(InMemoryBTreeConfiguration<K,V> configuration)
Creates a new in-memory B-tree using the BTreeConfiguration to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createInMemoryBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer)
Creates a new in-memory B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createInMemoryBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
boolean allowDuplicates)
Creates a new in-memory B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createInMemoryBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
int pageSize)
Creates a new in-memory B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createInMemoryBTree(java.lang.String name,
java.lang.String filePath,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer)
Creates a new in-memory B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createInMemoryBTree(java.lang.String name,
java.lang.String filePath,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
int pageSize)
Creates a new in-memory B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createInMemoryBTree(java.lang.String name,
java.lang.String filePath,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
int pageSize,
boolean allowDuplicates)
Creates a new in-memory B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree()
Creates a new persisted B-tree, with no initialization.
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree(BTreeTypeEnum type)
Creates a new persisted B-tree, with no initialization.
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree(PersistedBTreeConfiguration<K,V> configuration)
Creates a new persisted B-tree using the BTreeConfiguration to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer)
Creates a new persisted B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
boolean allowDuplicates)
Creates a new persisted B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
boolean allowDuplicates,
int cacheSize)
Creates a new persisted B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
int pageSize)
Creates a new persisted B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
int pageSize,
boolean allowDuplicates)
Creates a new persisted B-tree using the parameters to initialize the
B-tree
|
static <K,V> BTree<K,V> |
BTreeFactory.createPersistedBTree(java.lang.String name,
ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer,
int pageSize,
boolean allowDuplicates,
int cacheSize)
Creates a new persisted B-tree using the parameters to initialize the
B-tree
|
BTree<K,V> |
AbstractPage.getBtree() |
(package private) BTree<K,V> |
BTreeHeader.getBtree() |
<K,V> BTree<K,V> |
RecordManager.getManagedTree(java.lang.String name)
Get one managed trees, knowing its name.
|
BTree<?,V> |
PersistedBTreeConfiguration.getParentBTree() |
static <K,V> BTree<K,V> |
BulkLoader.load(BTree<K,V> btree,
java.util.Iterator<Tuple<K,V>> iterator,
int chunkSize)
Bulk Load data into a persisted BTree
|
(package private) <K,V> BTree<V,V> |
RecordManager.loadDupsBtree(long btreeHeaderOffset,
BTree<K,V> parentBtree)
Loads a B-tree holding the values of a duplicate key
This tree is also called as dups tree or sub tree
|
| Modifier and Type | Method and Description |
|---|---|
private int |
InMemoryBTreeBuilder.add(BTree<K,V> btree,
Page<K,V>[] pageStack,
int level,
Page<K,V> page,
Tuple<K,V> tuple) |
private Page<K,V> |
InMemoryBTreeBuilder.addLeaves(BTree<K,V> btree,
java.util.List<Tuple<K,V>> tuples,
int maxElements)
Creates all the leaves using the provided tuples, and update the upper layer if needed
|
private Page<K,V> |
InMemoryBTreeBuilder.attachNodes(java.util.List<Page<K,V>> children,
BTree<K,V> btree) |
private Page<K,V> |
PersistedBTreeBuilder.attachNodes(java.util.List<Page<K,V>> children,
BTree<K,V> btree) |
private static <K,V> BTree<K,V> |
BulkLoader.bulkLoad(BTree<K,V> btree,
java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator,
int nbElems)
Construct the target BTree from the sorted data.
|
private static <K,V> BTree<K,V> |
BulkLoader.bulkLoadSinglePage(BTree<K,V> btree,
java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator,
int nbElems) |
static BTree<?,?> |
BulkLoader.compact(BTree<?,?> btree)
Compact a given in-memory BTree, making it dense.
|
static void |
BulkLoader.compact(RecordManager recordManager,
BTree<?,?> btree)
Compact a given persisted BTree, making it dense.
|
(package private) static <K,V> LevelInfo<K,V> |
BulkLoader.computeLevel(BTree<K,V> btree,
int nbElems,
BulkLoader.LevelEnum levelType)
Creates a node leaf LevelInfo based on the number of elements in the lower level.
|
(package private) static <K,V> java.util.List<LevelInfo<K,V>> |
BulkLoader.computeLevels(BTree<K,V> btree,
int nbElems)
Compute the number of pages necessary to store all the elements per level.
|
private static <K,V> int |
BulkLoader.computeNbElemsLeaf(BTree<K,V> btree,
LevelInfo<K,V> levelInfo) |
(package private) int |
BulkLoader.computeNbElemsNode(BTree<K,V> btree,
LevelInfo<K,V> levelInfo)
Compute the number of nodes necessary to store all the elements.
|
private static <K,V> java.util.Iterator<Tuple<K,java.util.Set<V>>> |
BulkLoader.createIterator(BTree<K,V> btree,
java.io.FileInputStream[] streams)
Build an iterator over an array of sorted tuples, from files on the disk
|
(package private) static <K,V> Page<K,V> |
BTreeFactory.createLeaf(BTree<K,V> btree,
long revision,
int nbElems)
Create a new Leaf for the given B-tree.
|
(package private) static <K,V> Page<K,V> |
BTreeFactory.createNode(BTree<K,V> btree,
long revision,
int nbElems)
Create a new Node for the given B-tree.
|
private InMemoryNode<K,V> |
InMemoryBTreeBuilder.createParentNode(BTree<K,V> btree,
java.util.List<InMemoryNode<K,V>> nodes,
int maxElements)
Creates all the nodes using the provided node pages, and update the upper laye
|
private static <K,V> java.util.Iterator<Tuple<K,java.util.Set<V>>> |
BulkLoader.createTupleIterator(BTree<K,V> btree,
java.util.List<Tuple<K,V>> tuples)
Build an iterator over an array of sorted tuples, in memory
|
private static <K,V> java.util.Iterator<Tuple<K,java.util.Set<V>>> |
BulkLoader.createUniqueFileIterator(BTree<K,V> btree,
java.io.FileInputStream stream)
Build an iterator over an array of sorted tuples, from files on the disk
|
<K,V> Page<K,V> |
RecordManager.deserialize(BTree<K,V> btree,
long offset)
Deserialize a Page from a B-tree at a give position
|
private static <K,V> Tuple<K,java.util.Set<V>> |
BulkLoader.fetchTuple(BTree<K,V> btree,
java.io.FileInputStream fis) |
private static <K,V> java.io.File |
BulkLoader.flushToDisk(int fileNb,
java.util.List<Tuple<K,V>> tuples,
BTree<K,V> btree)
Flush a list of tuples to disk after having sorted them.
|
(package private) <K,V> void |
RecordManager.freePages(BTree<K,V> btree,
long revision,
java.util.List<Page<K,V>> pages)
Move a list of pages to the free page list.
|
(package private) static <K,V> java.util.LinkedList<ParentPos<K,V>> |
BTreeFactory.getPathToLeftMostLeaf(BTree<K,V> btree)
Includes the intermediate nodes in the path up to and including the left most leaf of the tree
|
(package private) static <K,V> java.util.LinkedList<ParentPos<K,V>> |
BTreeFactory.getPathToRightMostLeaf(BTree<K,V> btree)
Includes the intermediate nodes in the path up to and including the right most leaf of the tree
|
(package private) static <K,V> Page<K,V> |
BTreeFactory.getRootPage(BTree<K,V> btree)
Return the B-tree root page
|
(package private) <K,V> Page<K,V> |
RecordManager.getRootPage(BTree<K,V> btree,
long revision)
Fetch the rootPage of a given B-tree for a given revision.
|
void |
PersistedBTree.init(BTree<K,V> parentBTree)
Initialize the BTree.
|
private static <K,V> void |
BulkLoader.injectInLeaf(BTree<K,V> btree,
Tuple<K,java.util.Set<V>> tuple,
LevelInfo<K,V> leafLevel)
Inject a tuple into a leaf
|
private static <K,V> void |
BulkLoader.injectInNode(BTree<K,V> btree,
Page<K,V> page,
java.util.List<LevelInfo<K,V>> levels,
int levelIndex)
Inject a page reference into a Node.
|
private static <K,V> void |
BulkLoader.injectInRoot(BTree<K,V> btree,
Page<K,V> page,
PageHolder<K,V> pageHolder,
LevelInfo<K,V> level)
Inject a page reference into the root page.
|
private void |
InMemoryBTreeBuilder.injectTuple(BTree<K,V> btree,
InMemoryLeaf<K,V> leaf,
int leafPos,
Tuple<K,V> tuple) |
static <K,V> BTree<K,V> |
BulkLoader.load(BTree<K,V> btree,
java.util.Iterator<Tuple<K,V>> iterator,
int chunkSize)
Bulk Load data into a persisted BTree
|
private <K,V> void |
RecordManager.loadBtree(PageIO[] pageIos,
BTree<K,V> btree)
Read a B-tree from the disk.
|
(package private) <K,V> void |
RecordManager.loadBtree(PageIO[] pageIos,
BTree btree,
BTree<K,V> parentBTree)
Read a B-tree from the disk.
|
(package private) <K,V> void |
RecordManager.loadBtree(PageIO[] pageIos,
BTree btree,
BTree<K,V> parentBTree)
Read a B-tree from the disk.
|
(package private) <K,V> BTree<V,V> |
RecordManager.loadDupsBtree(long btreeHeaderOffset,
BTree<K,V> parentBtree)
Loads a B-tree holding the values of a duplicate key
This tree is also called as dups tree or sub tree
|
<K,V> void |
RecordManager.manage(BTree<K,V> btree)
Manage a B-tree.
|
<K,V> void |
RecordManager.manageSubBtree(BTree<K,V> btree)
Managing a btree is a matter of storing an reference to the managed B-tree in the B-tree Of B-trees.
|
private static <K,V> Tuple<java.util.Iterator<Tuple<K,java.util.Set<V>>>,BulkLoader.SortedFile> |
BulkLoader.processFiles(BTree<K,V> btree,
java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator)
Read all the sorted files, and inject them into one single big file containing all the
sorted and merged elements.
|
private static <K,V> int |
BulkLoader.readElements(BTree<K,V> btree,
java.util.Iterator<Tuple<K,V>> iterator,
java.util.List<java.io.File> sortedFiles,
java.util.List<Tuple<K,V>> tuples,
int chunkSize)
Process the data, and creates files to store them sorted if necessary, or store them
TODO readElements.
|
private <K,V> PersistedLeaf<K,V> |
RecordManager.readLeafKeysAndValues(BTree<K,V> btree,
int nbElems,
long revision,
java.nio.ByteBuffer byteBuffer,
PageIO[] pageIos)
Deserialize a Leaf from some PageIOs
|
private <K,V> PersistedNode<K,V> |
RecordManager.readNodeKeysAndValues(BTree<K,V> btree,
int nbElems,
long revision,
java.nio.ByteBuffer byteBuffer,
PageIO[] pageIos)
Deserialize a Node from some PageIos
|
private <K,V> Page<K,V> |
RecordManager.readPage(BTree<K,V> btree,
PageIO[] pageIos)
Read a page from some PageIO for a given B-tree
|
private <K,V> Page<K,V> |
RecordManager.readRootPage(BTree<K,V> btree,
long btreeHeaderOffset)
Read a root page from the B-tree header offset
|
private <K,V> PageIO[] |
RecordManager.serializePage(BTree<K,V> btree,
long revision,
Page<K,V> page)
Serialize a new Page.
|
(package private) void |
BTreeHeader.setBtree(BTree<K,V> btree)
Associate a B-tree with this BTreeHeader instance
|
(package private) static <K,V> void |
BTreeFactory.setKey(BTree<K,V> btree,
Page<K,V> page,
int pos,
byte[] buffer)
Set the key at a give position
|
(package private) static <K,V> void |
BTreeFactory.setKey(BTree<K,V> btree,
Page<K,V> page,
int pos,
K key)
Set the key at a give position
|
(package private) static <K,V> void |
BTreeFactory.setKeySerializer(BTree<K,V> btree,
java.lang.String keySerializerFqcn)
Sets the KeySerializer into the B-tree
|
(package private) static <K,V> void |
BTreeFactory.setName(BTree<K,V> btree,
java.lang.String name)
Set the B-tree name
|
(package private) static <K,V> void |
BTreeFactory.setNbElems(BTree<K,V> btree,
long nbElems)
Update the B-tree number of elements
|
(package private) static <K,V> void |
BTreeFactory.setPage(BTree<K,V> btree,
Page<K,V> page,
int pos,
Page<K,V> child)
Set the page at a give position
|
(package private) static <K,V> void |
BTreeFactory.setPageSize(BTree<K,V> btree,
int pageSize)
Set the maximum number of elements we can store in a page.
|
void |
PersistedBTreeConfiguration.setParentBTree(BTree<?,V> parentBTree) |
(package private) static <K,V> void |
BTreeFactory.setRecordManager(BTree<K,V> btree,
RecordManager recordManager)
Set the RecordManager
|
(package private) static <K,V> void |
BTreeFactory.setRevision(BTree<K,V> btree,
long revision)
Update the B-tree revision
|
(package private) static <K,V> void |
BTreeFactory.setRootPage(BTree<K,V> btree,
Page<K,V> root)
Set the new root page for this tree.
|
(package private) static <K,V> void |
BTreeFactory.setRootPageOffset(BTree<K,V> btree,
long rootPageOffset)
Set the rootPage offset of the B-tree
|
(package private) void |
InMemoryValueHolder.setSubBtree(BTree<V,V> subBtree)
Set the subBtree in the ValueHolder
|
(package private) void |
PersistedValueHolder.setSubBtree(BTree<V,V> subBtree)
Set the subBtree in the ValueHolder
|
(package private) static <K,V> void |
BTreeFactory.setValue(BTree<K,V> btree,
Page<K,V> page,
int pos,
ValueHolder<V> value)
Set the value at a give position
|
(package private) static <K,V> void |
BTreeFactory.setValueSerializer(BTree<K,V> btree,
java.lang.String valueSerializerFqcn)
Sets the ValueSerializer into the B-tree
|
private static <K,V> Tuple<K,java.util.Set<V>>[] |
BulkLoader.sort(BTree<K,V> btree,
java.util.List<Tuple<K,V>> tuples)
Sort a list of tuples, eliminating the duplicate keys and storing the values in a set when we
have a duplicate key
|
(package private) <K,V> void |
RecordManager.storeRootPage(BTree<K,V> btree,
Page<K,V> rootPage)
Store a reference to an old rootPage into the Revision B-tree
|
(package private) <K,V> long |
RecordManager.updateBtreeHeader(BTree<K,V> btree,
long btreeHeaderOffset)
Update the B-tree header after a B-tree modification.
|
private <K,V> long |
RecordManager.updateBtreeHeader(BTree<K,V> btree,
long btreeHeaderOffset,
boolean onPlace)
Update the B-tree header after a B-tree modification.
|
(package private) <K,V> void |
RecordManager.updateBtreeHeaderOnPlace(BTree<K,V> btree,
long btreeHeaderOffset)
Update the B-tree header after a B-tree modification.
|
(package private) <K,V> long |
RecordManager.writeBtreeHeader(BTree<K,V> btree,
BTreeHeader<K,V> btreeHeader)
Write the B-tree header on disk.
|
private <K,V> long |
RecordManager.writeBtreeInfo(BTree<K,V> btree)
Write the B-tree informations on disk.
|
(package private) <K,V> PageHolder<K,V> |
RecordManager.writePage(BTree<K,V> btree,
Page<K,V> newPage,
long newRevision)
Write the page in a serialized form.
|
| Constructor and Description |
|---|
AbstractPage(BTree<K,V> btree)
Creates a default empty AbstractPage
|
AbstractPage(BTree<K,V> btree,
long revision,
int nbElems)
Internal constructor used to create Page instance used when a page is being copied or overflow
|
InMemoryLeaf(BTree<K,V> btree)
Constructor used to create a new Leaf when we read it from a file.
|
InMemoryLeaf(BTree<K,V> btree,
long revision,
int nbElems)
Internal constructor used to create Page instance used when a page is being copied or overflow
|
InMemoryNode(BTree<K,V> btree,
long revision,
int nbElems)
Creates a new Node which will contain only one key, with references to
a left and right page.
|
InMemoryNode(BTree<K,V> btree,
long revision,
K key,
Page<K,V> leftPage,
Page<K,V> rightPage)
Creates a new Node which will contain only one key, with references to
a left and right page.
|
InMemoryValueHolder(BTree<?,V> parentBtree,
int nbValues)
Creates a new instance of a ValueHolder, containing the serialized values.
|
InMemoryValueHolder(BTree<?,V> parentBtree,
V... values)
Creates a new instance of a ValueHolder, containing Values.
|
PageHolder(BTree<K,V> btree,
Page<K,V> page)
Create a new holder storing an offset and a SoftReference containing the element.
|
PersistedLeaf(BTree<K,V> btree)
Constructor used to create a new Leaf when we read it from a file.
|
PersistedLeaf(BTree<K,V> btree,
long revision,
int nbElems)
Internal constructor used to create Page instance used when a page is being copied or overflow
|
PersistedNode(BTree<K,V> btree,
long revision,
int nbElems)
Creates a new Node which will contain only one key, with references to
a left and right page.
|
PersistedNode(BTree<K,V> btree,
long revision,
K key,
Page<K,V> leftPage,
Page<K,V> rightPage)
Creates a new Node which will contain only one key, with references to
a left and right page.
|
PersistedNode(BTree<K,V> btree,
long revision,
K key,
PageHolder<K,V> leftPage,
PageHolder<K,V> rightPage)
Creates a new Node which will contain only one key, with references to
a left and right page.
|
PersistedPageHolder(BTree<K,V> btree,
Page<K,V> page)
Create a new holder storing an offset and a SoftReference containing the element.
|
PersistedPageHolder(BTree<K,V> btree,
Page<K,V> page,
long offset,
long lastOffset)
Create a new holder storing an offset and a SoftReference containing the element.
|
PersistedValueHolder(BTree<?,V> parentBtree,
int nbValues,
byte[] raw)
Creates a new instance of a ValueHolder, containing the serialized values.
|
PersistedValueHolder(BTree<?,V> parentBtree,
V... values)
Creates a new instance of a ValueHolder, containing Values.
|
ValueBTreeCursor(BTree<V,V> valueBtree)
Create an instance
|