public class IndexSegmentPlan extends Object
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 nonroot leaf (and
also the minimum #of children that may be placed into a nonroot
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 nonleaf 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 and Description 

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

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.

protected static final transient org.apache.log4j.Logger log
public final int m
public final int m2
public final long nentries
public final long nleaves
public final long nnodes
public final int height
public final int[] numInLeaf
public final long[] numInLevel
#nleaves, which is the #of leaves in the output tree.
public final int[][] numInNode
public IndexSegmentPlan(int m, long nentries)
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.IllegalArgumentException
 if the branching factor is less than
.IllegalArgumentException
 if the #of index entries is negative (zero is allowed as a
special case).public String toString()
public static int getMinimumHeight(int m, long nleaves)
m
 The branching factor.nleaves
 The #of leaves that must be addressable by the tree.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
).public static int[] distributeKeys(int m, int m2, long nleaves, long nentries)
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 n1 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.
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.IllegalArgumentException
 if there is a problem with the arguments.TestIndexSegmentPlan
,
TestIndexSegmentBuilderWithSmallTree.test_problem3_buildOrder3()
public static int[] distributeChildren(int m, int m2, long nnodes, long nchildren)
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).
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.TestIndexSegmentPlan
,
TestIndexSegmentBuilderWithSmallTree.test_problem3_buildOrder3()
Copyright © 2006–2019 SYSTAP, LLC DBA Blazegraph. All rights reserved.