Fennel: BTreeBuilder Class Reference (original) (raw)

BTreeBuilder implements bulk load for BTrees. More...

#include <[BTreeBuilder.h](BTreeBuilder%5F8h-source.html)>

Inheritance diagram for BTreeBuilder:

Public Member Functions
	BTreeBuilder (BTreeDescriptor const &descriptor, SharedSegment pTempSegment=SharedSegment())
	Creates a new BTreeBuilder.
virtual	~BTreeBuilder ()
void	build (ByteInputStream &sortedStream, RecordNum nEntries, double fillFactor=1.0)
	Builds the tree, which must be currently empty or non-existent.
void	createEmptyRoot ()
	Creates an empty tree (just a root node with no tuples).
void	truncate (bool rootless, TupleProjection const *pLeafPageIdProj=NULL)
	Truncates or drops an existing tree.
SharedSegment	getSegment () const
	Returns:the segment storing the BTree being accessed
SharedCacheAccessor	getCacheAccessor () const
	Returns:the CacheAccessor used to access the BTree's pages
PageId	getRootPageId () const
	Returns:the BTree's root PageId
void	setRootPageId (PageId rootPageId)
	Updates the BTree's root PageId.
SegmentId	getSegmentId () const
	Returns:SegmentId of segment storing the BTree
PageOwnerId	getPageOwnerId () const
	Returns:PageOwnerId used to mark pages of the BTree
TupleDescriptor const &	getTupleDescriptor () const
	Returns:TupleDescriptor for tuples stored by this BTree
TupleDescriptor const &	getKeyDescriptor () const
	Returns:TupleDescriptor for keys indexed by this BTree
TupleProjection const &	getKeyProjection () const
	Returns:TupleProjection from getTupleDescriptor() to getKeyDescriptor()
void	validateTupleSize (TupleAccessor const &tupleAccessor)
	Validates that a particular tuple can fit in this BTree, throwing a TupleOverflowExcn if not.
Protected Member Functions
BTreeNodeAccessor &	getLeafNodeAccessor (BTreeNode const &node)
	Gets the node accessor for a leaf node, asserting that the node really is a leaf.
BTreeNodeAccessor &	getNonLeafNodeAccessor (BTreeNode const &node)
	Gets the node accessor for a non-leaf node, asserting that the node really is a non-leaf.
BTreeNodeAccessor &	getNodeAccessor (BTreeNode const &node)
	Gets the node accessor for any node, using the node height to determine whether it's a leaf or not.
PageId	getChildForCurrent ()
	Gets the child PageId corresponding to the current key in a non-leaf node.
PageId	getChild (BTreeNode const &node, uint iChild)
	Accesses a non-leaf tuple and gets its child PageId.
PageId	getRightSibling (PageId pageId)
	Gets the right sibling of a node by consulting the containing segment's successor information.
void	setRightSibling (BTreeNode &leftNode, PageId leftPageId, PageId rightPageId)
	Sets the right sibling of a node.
PageId	getFirstChild (PageId pageId)
	Gets the first child of a non-leaf node.
Protected Attributes
BTreeDescriptor	treeDescriptor
	Descriptor for tree being accessed.
TupleDescriptor	keyDescriptor
	Descriptor for pure keys (common across leaf and non-leaf tuples).
AttributeAccessor const *	pChildAccessor
	Accessor for the attribute of non-leaf tuples which stores the child PageId.
TupleProjectionAccessor	leafKeyAccessor
	Accessor for keys of tuples stored in leaves.
boost::scoped_ptr< BTreeNodeAccessor >	pNonLeafNodeAccessor
	Accessor for non-leaf nodes.
boost::scoped_ptr< BTreeNodeAccessor >	pLeafNodeAccessor
	Accessor for leaf nodes.
uint	cbTupleMax
	Maximum size for a leaf-level tuple.
Private Member Functions
uint	getRootHeight ()
void	buildBalanced (ByteInputStream &sortedStream, uint iInputLevel, RecordNum nEntriesTotal, double fillFactor)
void	buildTwoPass (ByteInputStream &sortedStream, RecordNum nEntries, double fillFactor)
void	buildUnbalanced (ByteInputStream &sortedStream, RecordNum nEntries, double fillFactor)
void	processInput (ByteInputStream &sortedStream)
BTreeBuildLevel &	getLevel (uint i)
void	growTree ()
void	swapRoot ()
void	truncateChildren (BTreeNode const &node)
void	truncateExternal (TupleProjection const &leafPageIdProj)
Static Private Member Functions
static uint	calculateChildEntriesPerNode (RecordNum parentLevelTotalEntries, RecordNum childLevelTotalEntries, RecordNum parentLevelProcessedEntries)
static uint	calculateNodesOnLevel (uint nChildEntries, uint nEntriesPerChildNode)
Private Attributes
std::vector< SharedBTreeBuildLevel >	levels
SharedSegment	pTempSegment
Friends
class	BTreeBuildLevel
class	FixedBuildLevel
class	VariableBuildLevel
class	DynamicBuildLevel

Detailed Description

BTreeBuilder implements bulk load for BTrees.

When non-leaf nodes store fixed-width entries, it builds a nicely balanced tree. In other cases, it builds an unbalanced tree. An optional fill factor is supported for all cases.

BTreeBuilder is also used for creating empty trees and truncating or dropping existing ones.

Definition at line 49 of file BTreeBuilder.h.

Constructor & Destructor Documentation

Creates a new BTreeBuilder.

In order to build a non-empty tree with variable-width tuples in the leaf nodes and fixed-width entries in the non-leaf nodes, a temporary disk buffer is required.

Parameters:

descriptor	descriptor for tree to be built
pTempSegment	segment to use for temporary buffer, or NULL if it is known that none is needed

Definition at line 34 of file BTreeBuilder.cpp.

References pTempSegment.

| BTreeBuilder::~BTreeBuilder | ( | | ) | [virtual] | | ---------------------------- | - | | - | ----------- |

Member Function Documentation

uint BTreeBuilder::calculateChildEntriesPerNode	(	RecordNum	parentLevelTotalEntries,
RecordNum	childLevelTotalEntries,
RecordNum	parentLevelProcessedEntries
)	[static, private]

Definition at line 295 of file BTreeBuilder.cpp.

Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), and buildBalanced().

00299 { 00300
00301
00302
00303 double fanout = 00304 double(childLevelTotalEntries) / double(parentLevelTotalEntries); 00305 00306 uint childLevelNewTotal; 00307 if (parentLevelProcessedEntries == (parentLevelTotalEntries - 1)) { 00308
00309 childLevelNewTotal = childLevelTotalEntries; 00310 } else { 00311 childLevelNewTotal = 00312 uint(0.5 + fanout * (parentLevelProcessedEntries + 1)); 00313 } 00314 00315
00316
00317 uint childLevelPrevTotal = uint(0.5 + fanout * parentLevelProcessedEntries); 00318 00319 uint n = childLevelNewTotal - childLevelPrevTotal; 00320 assert(n > 0); 00321 return n; 00322 }

uint BTreeBuilder::calculateNodesOnLevel	(	uint	nChildEntries,
uint	nEntriesPerChildNode
)	[static, private]

Definition at line 46 of file BTreeBuilder.cpp.

Referenced by buildBalanced().

00048 { 00049 uint nNodes = nEntries / nEntriesPerNode; 00050 if (nEntries % nEntriesPerNode) { 00051
00052 ++nNodes; 00053 } 00054 return nNodes; 00055 }

| uint BTreeBuilder::getRootHeight | ( | | ) | [inline, private] | | --------------------------------------------------------------------------------------------- | - | | - | ------------------- |

Definition at line 182 of file BTreeBuilder.cpp.

References BTreeBuildLevel::allocatePage(), calculateChildEntriesPerNode(), calculateNodesOnLevel(), BTreeNodeAccessor::clearNode(), FixedBuildLevel, getLevel(), SegNodeLock< Node >::getNodeForWrite(), getRootHeight(), BTreeAccessBase::getRootPageId(), BTreeAccessBase::getSegment(), BTreeNode::height, BTreeBuildLevel::iLevel, BTreeBuildLevel::indexLastKey(), levels, SegPageLock::lockExclusive(), BTreeNode::nEntries, BTreeBuildLevel::nEntriesPerNode, BTreeBuildLevel::nEntriesTotal, BTreeBuildLevel::nodeAccessor, NULL_PAGE_ID, BTreeBuildLevel::pageId, BTreeBuildLevel::pageLock, BTreeAccessBase::pLeafNodeAccessor, BTreeAccessBase::pNonLeafNodeAccessor, BTreeBuildLevel::processInput(), BTreeDescriptor::rootPageId, and BTreeAccessBase::treeDescriptor.

Referenced by build(), and buildTwoPass().

Definition at line 87 of file BTreeBuilder.cpp.

References BTreeBuildLevel::allocatePage(), buildBalanced(), BTreeBuildLevel::cbReserved, getLevel(), BTreeAccessBase::getSegment(), BTreeNodeAccessor::hasFixedWidthEntries(), BTreeBuildLevel::indexLastKey(), BTreeBuildLevel::iNode, levels, BTreeBuildLevel::nEntriesTotal, BTreeAccessBase::pLeafNodeAccessor, BTreeBuildLevel::processInput(), swapRoot(), and VariableBuildLevel.

Referenced by build().

void BTreeBuilder::processInput	(	ByteInputStream &	sortedStream	)	[private]

| void BTreeBuilder::growTree | ( | | ) | [private] | | --------------------------- | - | | - | ----------- |

| void BTreeBuilder::swapRoot | ( | | ) | [private] | | --------------------------- | - | | - | ----------- |

Definition at line 133 of file BTreeBuilder.cpp.

References SegPageLock::deallocateLockedPage(), getLevel(), SegNodeLock< Node >::getNodeForWrite(), getRootHeight(), BTreeAccessBase::getRootPageId(), SegPageLock::lockExclusive(), BTreeNode::nEntries, NULL_PAGE_ID, BTreeBuildLevel::pageId, BTreeBuildLevel::pageLock, BTreeDescriptor::rootPageId, BTreeDescriptor::segmentAccessor, SegPageLock::swapBuffers(), and BTreeAccessBase::treeDescriptor.

Referenced by buildTwoPass(), and buildUnbalanced().

void BTreeBuilder::truncateChildren	(	BTreeNode const &	node	)	[private]

Definition at line 389 of file BTreeBuilder.cpp.

References SegPageLock::accessSegment(), SegPageLock::deallocateUnlockedPage(), BTreeAccessBase::getChild(), SegNodeLock< Node >::getNodeForRead(), BTreeAccessBase::getRightSibling(), BTreeNode::height, SegPageLock::lockExclusive(), BTreeNode::nEntries, NULL_PAGE_ID, BTreeDescriptor::segmentAccessor, BTreeAccessBase::treeDescriptor, and SegPageLock::unlock().

Referenced by truncate().

void BTreeBuilder::truncateExternal	(	TupleProjection const &	leafPageIdProj	)	[private]

Definition at line 408 of file BTreeBuilder.cpp.

References SegPageLock::accessSegment(), TupleProjectionAccessor::bind(), SegPageLock::deallocateUnlockedPage(), BTreeReader::getTupleAccessorForRead(), TupleDescriptor::projectFrom(), BTreeReader::searchFirst(), BTreeReader::searchNext(), BTreeDescriptor::segmentAccessor, BTreeAccessBase::treeDescriptor, BTreeDescriptor::tupleDescriptor, and TupleProjectionAccessor::unmarshal().

Referenced by truncate().

Builds the tree, which must be currently empty or non-existent.

Call getRootPageId() afterwards to find the root of a newly created tree.

Parameters:

sortedStream	stream containing tuples presorted by the tree's key
nEntries	number of tuples to be read from pSortedStream
fillFactor	fraction of each node to fill, where 1.0 (the default) represents 100%

Definition at line 57 of file BTreeBuilder.cpp.

References buildBalanced(), buildTwoPass(), buildUnbalanced(), levels, BTreeAccessBase::pLeafNodeAccessor, and BTreeAccessBase::pNonLeafNodeAccessor.

Referenced by BTreeTest::testBulkLoad(), and BTreeReadersTest::testReaders().

00061 { 00062 assert(fillFactor <= 1.0); 00063 assert(fillFactor > 0); 00064 try { 00065 if (pLeafNodeAccessor->hasFixedWidthEntries() 00066 && pNonLeafNodeAccessor->hasFixedWidthEntries()) 00067 { 00068 buildBalanced(sortedInputStream,0,nEntriesTotal,fillFactor); 00069 } else if (pNonLeafNodeAccessor->hasFixedWidthEntries()) { 00070 buildTwoPass( 00071 sortedInputStream,nEntriesTotal,fillFactor); 00072 } else { 00073 assert( pLeafNodeAccessor ->hasFixedWidthEntries()); 00074 buildUnbalanced(sortedInputStream,nEntriesTotal,fillFactor); 00075 } 00076 } catch (...) { 00077 try { 00078 levels.clear(); 00079 } catch (...) { 00080
00081 } 00082 throw; 00083 } 00084 levels.clear(); 00085 }

| void BTreeBuilder::createEmptyRoot | ( | | ) | | ---------------------------------- | - | | - |

Creates an empty tree (just a root node with no tuples).

On entry, the builder should have NULL_PAGE_ID for its root. Call getRootPageId() afterwards to get the new root.

Definition at line 324 of file BTreeBuilder.cpp.

References SegPageLock::accessSegment(), SegNodeLock< Node >::allocatePage(), SegNodeLock< Node >::getNodeForWrite(), BTreeAccessBase::getPageOwnerId(), BTreeAccessBase::getRootPageId(), BTreeAccessBase::getSegment(), NULL_PAGE_ID, BTreeAccessBase::pLeafNodeAccessor, BTreeDescriptor::rootPageId, BTreeDescriptor::segmentAccessor, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeInsertExecStream::buildTree(), LbmSplicerExecStreamTest::createBTree(), LcsClusterReplaceExecStream::getTupleForLoad(), LbmSplicerExecStream::getValidatedTuple(), LcsClusterReplaceExecStreamTest::loadCluster(), LcsMultiClusterAppendTest::loadClusters(), LcsRowScanExecStreamTest::loadOneCluster(), LbmSearchTest::loadTableAndIndex(), ExecStreamTestSuite::testBTreeInsertExecStream(), BTreeTest::testBulkLoad(), BTreeTest::testInserts(), LbmLoadBitmapTest::testLoad(), LcsClusterAppendExecStreamTest::testLoadMultiCol(), LcsClusterAppendExecStreamTest::testLoadSingleCol(), BTreeTest::testMultiKeySearches(), BTreeReadersTest::testReaders(), LcsRowScanExecStreamTest::testScanOnEmptyCluster(), and CmdInterpreter::visit().

void BTreeBuilder::truncate	(	bool	rootless,
TupleProjection const *	pLeafPageIdProj = NULL
)

Truncates or drops an existing tree.

Parameters:

rootless	if true, all nodes of the existing tree are deallocated; if false, the root is cleared but remains allocated while all other nodes are deallocated
pLeafPageIdProj	if non-NULL, leaf tuples will be read and non-null projected attributes will be interpreted as additional PageId's to be dropped

Definition at line 351 of file BTreeBuilder.cpp.

References SegPageLock::accessSegment(), SegPageLock::deallocateLockedPage(), SegNodeLock< Node >::getNodeForRead(), SegNodeLock< Node >::getNodeForWrite(), BTreeAccessBase::getRootPageId(), BTreeAccessBase::getSegment(), BTreeNode::height, SegPageLock::lockExclusive(), BTreeNode::nEntries, NULL_PAGE_ID, BTreeAccessBase::pLeafNodeAccessor, BTreeDescriptor::rootPageId, BTreeDescriptor::segmentAccessor, BTreeAccessBase::treeDescriptor, truncateChildren(), and truncateExternal().

Referenced by CmdInterpreter::dropOrTruncateIndex(), BTreeTest::testBulkLoad(), BTreeReadersTest::testReaders(), and BTreeInsertExecStream::truncateTree().

FENNEL_BEGIN_NAMESPACE BTreeNodeAccessor & BTreeAccessBase::getLeafNodeAccessor	(	BTreeNode const &	node	)	[inline, protected, inherited]

Gets the node accessor for any node, using the node height to determine whether it's a leaf or not.

If you already know this from the context, call getLeafNodeAccessor or getNonLeafNodeAccessor instead.

Parameters:

Returns:

node accessor

Definition at line 46 of file BTreeAccessBaseImpl.h.

References BTreeNode::height, BTreeAccessBase::pLeafNodeAccessor, and BTreeAccessBase::pNonLeafNodeAccessor.

Referenced by BTreeReader::accessTupleInline(), BTreeWriter::attemptInsertWithoutSplit(), BTreeReader::binarySearch(), BTreeWriter::compactNode(), BTreeReader::compareFirstKey(), BTreeWriter::grow(), BTreeWriter::lockParentPage(), BTreeWriter::splitCurrentNode(), BTreeVerifier::verifyChildren(), and BTreeVerifier::verifyNode().

| PageId BTreeAccessBase::getChildForCurrent | ( | | ) | [inline, protected, inherited] | | ------------------------------------------ | - | | - | -------------------------------- |

PageId BTreeAccessBase::getChild	(	BTreeNode const &	node,
uint	iChild
)	[inline, protected, inherited]

PageId BTreeAccessBase::getRightSibling	(	PageId	pageId	)	[inline, protected, inherited]

Gets the right sibling of a node by consulting the containing segment's successor information.

Should only be used when the node is not already locked (e.g. during prefetch). When the node is already locked, its rightSibling field should be accessed instead.

Parameters:

pageId	PageId of node whose sibling is to be found

Returns:

PageId of right sibling

Definition at line 70 of file BTreeAccessBaseImpl.h.

References BTreeAccessBase::getSegment().

Referenced by truncateChildren(), and BTreeVerifier::verifyNode().

00071 { 00072 return getSegment()->getPageSuccessor(pageId); 00073 }

void BTreeAccessBase::setRightSibling	(	BTreeNode &	leftNode,
PageId	leftPageId,
PageId	rightPageId
)	[inline, protected, inherited]

PageId BTreeAccessBase::getFirstChild	(	PageId	pageId	)	[protected, inherited]

| SharedSegment BTreeAccessBase::getSegment | ( | | ) | const [inline, inherited] | | --------------------------------------------------------------------------------------------------- | - | | - | --------------------------- |

Returns:

the segment storing the BTree being accessed

Definition at line 234 of file BTreeAccessBase.h.

References SegmentAccessor::pSegment, BTreeDescriptor::segmentAccessor, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeBuildLevel::allocatePage(), BTreeAccessBase::BTreeAccessBase(), buildBalanced(), buildTwoPass(), buildUnbalanced(), BTreeWriter::compactNode(), createEmptyRoot(), BTreeAccessBase::getRightSibling(), BTreeWriter::grow(), BTreeAccessBase::setRightSibling(), BTreeWriter::splitCurrentNode(), and truncate().

| PageId BTreeAccessBase::getRootPageId | ( | | ) | const [inline, inherited] | | ------------------------------------- | - | | - | --------------------------- |

Returns:

the BTree's root PageId

Definition at line 244 of file BTreeAccessBase.h.

References BTreeDescriptor::rootPageId, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeVerifier::BTreeVerifier(), buildBalanced(), BTreeInsertExecStream::buildTree(), LbmSplicerExecStreamTest::createBTree(), createEmptyRoot(), BTreeWriter::describeParticipant(), LcsClusterReplaceExecStream::getTupleForLoad(), LbmSplicerExecStream::getValidatedTuple(), BTreeNonLeafReader::isRootOnly(), LcsClusterReplaceExecStreamTest::loadCluster(), LcsMultiClusterAppendTest::loadClusters(), LcsRowScanExecStreamTest::loadOneCluster(), LbmSearchTest::loadTableAndIndex(), BTreeWriter::lockParentPage(), BTreeWriter::optimizeRootLockMode(), BTreeWriter::positionSearchKey(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKey(), BTreeNonLeafReader::searchForKey(), swapRoot(), ExecStreamTestSuite::testBTreeInsertExecStream(), BTreeTest::testBulkLoad(), BTreeTest::testInserts(), LbmLoadBitmapTest::testLoad(), LcsClusterAppendExecStreamTest::testLoadMultiCol(), LcsClusterAppendExecStreamTest::testLoadSingleCol(), BTreeTest::testMultiKeySearches(), BTreeReadersTest::testReaders(), BTreeReadersTest::testScan(), LcsRowScanExecStreamTest::testScanOnEmptyCluster(), BTreeReadersTest::testSearch(), truncate(), BTreeVerifier::verify(), and CmdInterpreter::visit().

void BTreeAccessBase::setRootPageId	(	PageId	rootPageId	)	[inherited]

| SegmentId BTreeAccessBase::getSegmentId | ( | | ) | const [inline, inherited] | | --------------------------------------- | - | | - | --------------------------- |

| PageOwnerId BTreeAccessBase::getPageOwnerId | ( | | ) | const [inline, inherited] | | ------------------------------------------- | - | | - | --------------------------- |

| TupleDescriptor const & BTreeAccessBase::getTupleDescriptor | ( | | ) | const [inline, inherited] | | ---------------------------------------------------------------------------------------- | - | | - | --------------------------- |

| TupleDescriptor const & BTreeAccessBase::getKeyDescriptor | ( | | ) | const [inline, inherited] | | -------------------------------------------------------------------------------------- | - | | - | --------------------------- |

| TupleProjection const & BTreeAccessBase::getKeyProjection | ( | | ) | const [inline, inherited] | | -------------------------------------------------------------------------------------- | - | | - | --------------------------- |