org.apache.directory.mavibot.btree

Class BulkLoader<K,V>

java.lang.Object

org.apache.directory.mavibot.btree.BulkLoader<K,V>

public class BulkLoader<K,V>
extends java.lang.Object

A class used to bulk load a BTree. It will allow the load of N elements in a given BTree without to have to inject one by one, saving a lot of time. The second advantage is that the btree will be dense (the leaves will be complete, except the last one). This class can also be used to compact a BTree.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) static class	BulkLoader.LevelEnum
private static class	BulkLoader.SortedFile A private class used to store the temporary sorted file.

Constructor Summary

Constructors

Modifier	Constructor and Description
private	BulkLoader()

Method Summary

Modifier and Type	Method and Description
private static <K,V> BTree<K,V>	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>	bulkLoadSinglePage(BTree<K,V> btree, java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator, int nbElems)
static BTree<?,?>	compact(BTree<?,?> btree) Compact a given in-memory BTree, making it dense.
static void	compact(RecordManager recordManager, BTree<?,?> btree) Compact a given persisted BTree, making it dense.
(package private) static <K,V> LevelInfo<K,V>	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>>	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	computeNbElemsLeaf(BTree<K,V> btree, LevelInfo<K,V> levelInfo)
(package private) int	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>>>	createIterator(BTree<K,V> btree, java.io.FileInputStream[] streams) Build an iterator over an array of sorted tuples, from files on the disk
private static <K,V> java.util.Iterator<Tuple<K,java.util.Set<V>>>	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>>>	createUniqueFileIterator(BTree<K,V> btree, java.io.FileInputStream stream) Build an iterator over an array of sorted tuples, from files on the disk
private static <K,V> Tuple<K,java.util.Set<V>>	fetchTuple(BTree<K,V> btree, java.io.FileInputStream fis)
private static <K,V> java.io.File	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.
private static <K,V> void	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	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	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.
static <K,V> BTree<K,V>	load(BTree<K,V> btree, java.util.Iterator<Tuple<K,V>> iterator, int chunkSize) Bulk Load data into a persisted BTree
private static <K,V> Tuple<java.util.Iterator<Tuple<K,java.util.Set<V>>>,BulkLoader.SortedFile>	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	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 static <K,V> Tuple<K,java.util.Set<V>>[]	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

Methods inherited from class java.lang.Object

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

Constructor Detail

BulkLoader

private BulkLoader()

Method Detail

readElements

private static <K,V> int 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)
                               throws java.io.IOException

Process the data, and creates files to store them sorted if necessary, or store them TODO readElements.

Parameters:

btree -

iterator -

sortedFiles -

tuples -

chunkSize -

Returns:

Throws:

java.io.IOException

processFiles

private static <K,V> Tuple<java.util.Iterator<Tuple<K,java.util.Set<V>>>,BulkLoader.SortedFile> processFiles(BTree<K,V> btree,
                                                                                                             java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator)
                                                                                                      throws java.io.IOException

Read all the sorted files, and inject them into one single big file containing all the sorted and merged elements.

Throws:

java.io.IOException

load

public static <K,V> BTree<K,V> load(BTree<K,V> btree,
                                    java.util.Iterator<Tuple<K,V>> iterator,
                                    int chunkSize)
                             throws java.io.IOException

Bulk Load data into a persisted BTree

Parameters:

btree - The persisted BTree in which we want to load the data

iterator - The iterator over the data to bulkload

chunkSize - The number of elements we may store in memory at each iteration

Throws:

java.io.IOException - If there is a problem while processing the data

computeLevel

static <K,V> LevelInfo<K,V> 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. We can store up to PageSize + 1 references to pages in a node.

computeLevels

static <K,V> java.util.List<LevelInfo<K,V>> computeLevels(BTree<K,V> btree,
                                                          int nbElems)

Compute the number of pages necessary to store all the elements per level. The resulting list is reversed ( ie the leaves are on the left, the root page on the right.

injectInLeaf

private static <K,V> void injectInLeaf(BTree<K,V> btree,
                                       Tuple<K,java.util.Set<V>> tuple,
                                       LevelInfo<K,V> leafLevel)

Inject a tuple into a leaf

computeNbElemsLeaf

private static <K,V> int computeNbElemsLeaf(BTree<K,V> btree,
                                            LevelInfo<K,V> levelInfo)

computeNbElemsNode

int computeNbElemsNode(BTree<K,V> btree,
                       LevelInfo<K,V> levelInfo)

Compute the number of nodes necessary to store all the elements.

injectInRoot

private static <K,V> void injectInRoot(BTree<K,V> btree,
                                       Page<K,V> page,
                                       PageHolder<K,V> pageHolder,
                                       LevelInfo<K,V> level)
                                throws java.io.IOException

Inject a page reference into the root page.

Throws:

java.io.IOException

injectInNode

private static <K,V> void injectInNode(BTree<K,V> btree,
                                       Page<K,V> page,
                                       java.util.List<LevelInfo<K,V>> levels,
                                       int levelIndex)
                                throws java.io.IOException

Inject a page reference into a Node. This method will recurse if needed.

Throws:

java.io.IOException

bulkLoadSinglePage

private static <K,V> BTree<K,V> bulkLoadSinglePage(BTree<K,V> btree,
                                                   java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator,
                                                   int nbElems)
                                            throws java.io.IOException

Throws:

java.io.IOException

bulkLoad

private static <K,V> BTree<K,V> bulkLoad(BTree<K,V> btree,
                                         java.util.Iterator<Tuple<K,java.util.Set<V>>> dataIterator,
                                         int nbElems)
                                  throws java.io.IOException

Construct the target BTree from the sorted data. We will use the nb of elements to determinate the structure of the BTree, as it must be balanced

Throws:

java.io.IOException

flushToDisk

private static <K,V> java.io.File flushToDisk(int fileNb,
                                              java.util.List<Tuple<K,V>> tuples,
                                              BTree<K,V> btree)
                                       throws java.io.IOException

Flush a list of tuples to disk after having sorted them. In the process, we may have to gather the values for the tuples having the same keys.

Throws:

java.io.IOException

sort

private static <K,V> Tuple<K,java.util.Set<V>>[] 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

createTupleIterator

private static <K,V> java.util.Iterator<Tuple<K,java.util.Set<V>>> createTupleIterator(BTree<K,V> btree,
                                                                                       java.util.List<Tuple<K,V>> tuples)

Build an iterator over an array of sorted tuples, in memory

fetchTuple

private static <K,V> Tuple<K,java.util.Set<V>> fetchTuple(BTree<K,V> btree,
                                                          java.io.FileInputStream fis)

createIterator

private static <K,V> java.util.Iterator<Tuple<K,java.util.Set<V>>> createIterator(BTree<K,V> btree,
                                                                                  java.io.FileInputStream[] streams)
                                                                           throws java.io.FileNotFoundException

Build an iterator over an array of sorted tuples, from files on the disk

Throws:

java.io.FileNotFoundException

createUniqueFileIterator

private static <K,V> java.util.Iterator<Tuple<K,java.util.Set<V>>> createUniqueFileIterator(BTree<K,V> btree,
                                                                                            java.io.FileInputStream stream)
                                                                                     throws java.io.FileNotFoundException

Build an iterator over an array of sorted tuples, from files on the disk

Throws:

java.io.FileNotFoundException

compact

public static void compact(RecordManager recordManager,
                           BTree<?,?> btree)

Compact a given persisted BTree, making it dense. All the values will be stored in newly created pages, each one of them containing as much elements as it's size.
The RecordManager will be stopped and restarted, do not use this method on a running BTree.

Parameters:

recordManager - The associated recordManager

btree - The BTree to compact

compact

public static BTree<?,?> compact(BTree<?,?> btree)
                          throws java.io.IOException,
                                 KeyNotFoundException

Compact a given in-memory BTree, making it dense. All the values will be stored in newly created pages, each one of them containing as much elements as it's size.

Parameters:

btree - The BTree to compact

Throws:

KeyNotFoundException

java.io.IOException