com.bigdata.btree

Class IndexSegmentPlan

java.lang.Object

com.bigdata.btree.IndexSegmentPlan

public class IndexSegmentPlan
extends Object

A plan for building a B+-Tree based on an input branching factor and #of entries.

Version:

$Id$

Author:

Bryan Thompson

Field Summary

Fields

Modifier and Type	Field and Description
int	height The height of the output tree (#of levels in the output tree).
protected static org.apache.log4j.Logger	log
int	m The branching factor of the output tree (input).
int	m2 The minimum #of values that may be placed into non-root leaf (and also the minimum #of children that may be placed into a non-root node).
long	nentries The #of entries in the btree (input).
long	nleaves The #of leaves that will exist in the output tree.
long	nnodes The #of non-leaf nodes in the output tree.
int[]	numInLeaf The #of entries to place into each leaf.
long[]	numInLevel The #of nodes at each level of the tree, including the level containing the leaves.
int[][]	numInNode The #of children / values to place into each node in each level of the output tree.

Constructor Summary

Constructors

Constructor and Description
IndexSegmentPlan(int m, long nentries) Create a plan for building a B+-Tree.

Method Summary

Methods

Modifier and Type	Method and Description
static int[]	distributeChildren(int m, int m2, long nnodes, long nchildren) Distributes the children among the nodes of a given level.
static int[]	distributeKeys(int m, int m2, long nleaves, long nentries) Distributes the keys among the leaves.
static int	getMinimumHeight(int m, long nleaves) Chooses the minimum height for a tree having a specified branching factor and a specified #of leaves.
String	toString() A summary representation of the index build plan.

Methods inherited from class java.lang.Object

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

Field Detail

log

protected static final transient org.apache.log4j.Logger log

m

public final int m

The branching factor of the output tree (input).

m2

public final int m2

The minimum #of values that may be placed into non-root leaf (and also the minimum #of children that may be placed into a non-root node). (the minimum capacity).

nentries

public final long nentries

The #of entries in the btree (input).

nleaves

public final long nleaves

The #of leaves that will exist in the output tree. When nleaves == 1 the output tree will consist of a root leaf. In this case we do not open a temporary file for the nodes since there will not be any.

nnodes

public final long nnodes

The #of non-leaf nodes in the output tree.

height

public final int height

The height of the output tree (#of levels in the output tree).

numInLeaf

public final int[] numInLeaf

The #of entries to place into each leaf. The array is dimensioned to nleaves. This is a convenience reference to the last array in numInNode.

numInLevel

public final long[] numInLevel

The #of nodes at each level of the tree, including the level containing the leaves.

See Also:

#nleaves, which is the #of leaves in the output tree.

numInNode

public final int[][] numInNode

The #of children / values to place into each node in each level of the output tree. The first index is the level in the tree, starting from level zero which is the root and increasing through level [height+1], which is the level containing the leaves of the output tree.

See Also:

numInLeaf, which is a reference to the last element of this array.

Constructor Detail

IndexSegmentPlan

public IndexSegmentPlan(int m,
                long nentries)

Create a plan for building a B+-Tree. The plan has only these two inputs. Everything else about the plan is deterministic based on those values.

Parameters:

m - The branching factor of the output tree (#of keys/values for a leaf or the #of children for a node).

nentries - The #of entries in the tree.

Throws:

IllegalArgumentException - if the branching factor is less than .

IllegalArgumentException - if the #of index entries is negative (zero is allowed as a special case).

Method Detail

toString

public String toString()

A summary representation of the index build plan. The branching factor and the #of entries are the inputs. The outputs include the height of the B+Tree that should be generated and the #of nodes and leaves that will exist in that B+Tree.

Overrides:

toString in class Object

getMinimumHeight

public static int getMinimumHeight(int m,
                   long nleaves)

Chooses the minimum height for a tree having a specified branching factor and a specified #of leaves.

Parameters:

m - The branching factor.

nleaves - The #of leaves that must be addressable by the tree.

Throws:

UnsupportedOperationException - if it is not possible to build a B+Tree with that branching factor and that many leaves without exceeding maxHeight (statically configured to 10).

distributeKeys

public static int[] distributeKeys(int m,
                   int m2,
                   long nleaves,
                   long nentries)

Distributes the keys among the leaves.

We want to fill up every leaf, but we have to make sure that the last leaf is not under capacity. To that end, we calculate the #of entries that would remain if we filled up n-1 leaves completely. If the #of remaining entries is less than or equal to the minimum capacity of a leaf, then we have to adjust the allocation of entries such that the last leaf is at its minimum capacity. This is done by computing the shortage and then distributing that shortage among the leaves. Once we have deferred enough entries we are guaranteed that the final leaf will not be under capacity.

Parameters:

m - The branching factor in the output tree.

m2 - The minimum capacity for a leaf in the output tree, which is computed as (m+1)/2.

nleaves - The #of leaves in the output tree.

nentries - The #of entries to be inserted into the output tree.

Returns:

An array indicating how many entries should be inserted into each leaf of the output tree. The array index is the leaf order (origin zero). The value is the capacity to which that leaf should be filled.

Throws:

IllegalArgumentException - if there is a problem with the arguments.

See Also:

TestIndexSegmentPlan, TestIndexSegmentBuilderWithSmallTree.test_problem3_buildOrder3()

distributeChildren

public static int[] distributeChildren(int m,
                       int m2,
                       long nnodes,
                       long nchildren)

Distributes the children among the nodes of a given level.

Note: This is just an alias for distributeKeys(int, int, long, long). The only difference when distributing children among nodes is that the result returned to the caller must be interpreted as the #of children to assigned to each node NOT the #of keys (for leaves the #of values and the #of keys is always the same).

Parameters:

m - The branching factor in the output tree.

m2 - The minimum capacity, which should be computed as (m+1)/2.

nnodes - The #of nodes in the output tree for some given level of the output tree.

nchildren - The #of children to be distributed among those nodes.

Returns:

An array indicating how many children should be inserted into each node of the output tree at the given level. The array index is the node order (origin zero). The value is the #of children which must be assigned to that leaf.

See Also:

TestIndexSegmentPlan, TestIndexSegmentBuilderWithSmallTree.test_problem3_buildOrder3()