BTreeBuilder Class Reference

BTreeBuilder implements bulk load for BTrees. More...

#include <BTreeBuilder.h>

Inheritance diagram for BTreeBuilder:

List of all members.

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

BTreeBuilder::BTreeBuilder	(	BTreeDescriptor const &	descriptor,
		SharedSegment	pTempSegment = SharedSegment()
	)			[explicit]

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.

    : BTreeAccessBase(descriptor)
{
    pTempSegment = pTempSegmentInit;
}

BTreeBuilder::~BTreeBuilder

(

)

[virtual]

Definition at line 42 of file BTreeBuilder.cpp.

{
}

---

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().

{
    // Determine the desired fanout.  This is non-integral, so our job is to
    // distribute it as evenly as possible.
    // TODO:  we could remember this instead of recalculating it.
    double fanout =
        double(childLevelTotalEntries) / double(parentLevelTotalEntries);

    uint childLevelNewTotal;
    if (parentLevelProcessedEntries == (parentLevelTotalEntries - 1)) {
        // Last child node needs to make everything come out exact.
        childLevelNewTotal = childLevelTotalEntries;
    } else {
        childLevelNewTotal =
            uint(0.5 + fanout * (parentLevelProcessedEntries + 1));
    }

    // Use what we returned from the previous call as a baseline.
    // TODO:  we could remember this instead of recalculating it.
    uint childLevelPrevTotal = uint(0.5 + fanout * parentLevelProcessedEntries);

    uint n = childLevelNewTotal - childLevelPrevTotal;
    assert(n > 0);
    return n;
}

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

Definition at line 46 of file BTreeBuilder.cpp.

Referenced by buildBalanced().

{
    uint nNodes = nEntries / nEntriesPerNode;
    if (nEntries % nEntriesPerNode) {
        // need an extra node for the remainder
        ++nNodes;
    }
    return nNodes;
}

uint BTreeBuilder::getRootHeight

(

)

[inline, private]

Definition at line 74 of file BTreeBuilder.h.

Referenced by buildBalanced(), growTree(), DynamicBuildLevel::indexLastKey(), FixedBuildLevel::indexLastKey(), and swapRoot().

    {
        return levels.size() - 1;
    }

void BTreeBuilder::buildBalanced	(	ByteInputStream &	sortedStream,
		uint	iInputLevel,
		RecordNum	nEntriesTotal,
		double	fillFactor
	)			[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().

{
    // First, determine node capacities based on fixed-width entry sizes.  This
    // gives us the maximum fanout.

    uint nEntriesPerNonLeaf =
        getSegment()->getUsablePageSize() - sizeof(BTreeNode);
    nEntriesPerNonLeaf /=
        pNonLeafNodeAccessor->getEntryByteCount(
            pNonLeafNodeAccessor->tupleAccessor.getMaxByteCount());

    uint nEntriesPerLeaf =
        getSegment()->getUsablePageSize() - sizeof(BTreeNode);
    nEntriesPerLeaf /=
        pLeafNodeAccessor->getEntryByteCount(
            pLeafNodeAccessor->tupleAccessor.getMaxByteCount());

    nEntriesPerNonLeaf = uint(nEntriesPerNonLeaf*fillFactor);
    nEntriesPerLeaf = uint(nEntriesPerLeaf*fillFactor);

    if (!nEntriesPerNonLeaf) {
        nEntriesPerNonLeaf = 1;
    }
    if (!nEntriesPerLeaf) {
        nEntriesPerLeaf = 1;
    }

    // Next, calculate how high a "full" tree with this fanout would have to be
    // in order to accommodate the expected number of entries.  In most cases
    // the tree won't actually be full, but the height can't be any lower than
    // this.

    RecordNum nEntriesFull = iInputLevel ? nEntriesPerNonLeaf : nEntriesPerLeaf;
    uint nLevels = iInputLevel + 1;
    while (nEntriesFull < nEntriesTotal) {
        ++nLevels;
        nEntriesFull *= nEntriesPerNonLeaf;
    }
    levels.resize(nLevels);

    // Now, calculate how many entries to expect on each level.  We could do
    // the per-level balancing here as well, but then we'd have to keep around
    // an in-memory structure proportional to the number of nodes in the tree.
    // Instead, we calculate the balancing on the fly later.
    RecordNum nEntriesInLevel = nEntriesTotal;
    for (uint i = iInputLevel; i < levels.size(); i++) {
        BTreeNodeAccessor &nodeAccessor =
            i ? *pNonLeafNodeAccessor : *pLeafNodeAccessor;

        assert(nodeAccessor.hasFixedWidthEntries());
        levels[i].reset(new FixedBuildLevel(*this,nodeAccessor));

        BTreeBuildLevel &level = getLevel(i);
        level.iLevel = i;
        level.nEntriesTotal = nEntriesInLevel;

        // number of parent entries is same as number of child nodes
        nEntriesInLevel = calculateNodesOnLevel(
            nEntriesInLevel,
            i ? nEntriesPerNonLeaf : nEntriesPerLeaf);

        if (i == getRootHeight()) {
            // Set up the root info, which can be fully determined ahead of
            // time.
            level.nEntriesPerNode = level.nEntriesTotal;
            if (getRootPageId() == NULL_PAGE_ID) {
                level.allocatePage();
                treeDescriptor.rootPageId = level.pageId;
            } else {
                // We're from Berkeley, so we reuse the existing root rather
                // than allocating a new one.
                level.pageId = getRootPageId();
                level.pageLock.lockExclusive(level.pageId);
                BTreeNode &node = level.pageLock.getNodeForWrite();
                assert(!node.nEntries);
                level.nodeAccessor.clearNode(
                    node,getSegment()->getUsablePageSize());
                node.height = i;
            }
        } else {
            // Allocate the first empty page of a non-root level.
            level.allocatePage();
        }
        if (i) {
            // Prepare the first page of a non-leaf level.
            // Calculate balancing for first child node.
            BTreeBuildLevel &childLevel = getLevel(i - 1);
            childLevel.nEntriesPerNode = calculateChildEntriesPerNode(
                level.nEntriesTotal,
                childLevel.nEntriesTotal,
                0);
        }
    }

    // should end up with exactly one node at the root level, which corresponds
    // to one entry in an imaginary parent of the root
    assert(nEntriesInLevel == 1);

    // feed data into the correct level
    getLevel(iInputLevel).processInput(sortedInputStream);

    // finalize rightist fringe
    for (uint i = iInputLevel; i < levels.size(); ++i) {
        BTreeBuildLevel &level = getLevel(i);
        level.indexLastKey(true);
        assert(level.isFinished());
    }
}

void BTreeBuilder::buildTwoPass	(	ByteInputStream &	sortedStream,
		RecordNum	nEntries,
		double	fillFactor
	)			[private]

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().

{
    // calculate amount of space to reserve on each leaf from fillfactor
    uint cbReserved = getSegment()->getUsablePageSize() - sizeof(BTreeNode);
    cbReserved = uint(cbReserved*(1-fillFactor));

    levels.resize(1);
    BTreeNodeAccessor &nodeAccessor = *pLeafNodeAccessor;
    assert(!nodeAccessor.hasFixedWidthEntries());
    VariableBuildLevel *pLeafLevel = new VariableBuildLevel(*this,nodeAccessor);
    levels[0].reset(pLeafLevel);

    BTreeBuildLevel &level = getLevel(0);
    level.nEntriesTotal = nEntriesTotal;
    level.cbReserved = cbReserved;

    level.allocatePage();

    // feed data into the leaf level; this will collect the entries for
    // level 1 (the parent of the leaf level) in a temp stream
    level.processInput(sortedInputStream);

    level.indexLastKey(true);

    // now we know how many entries to expect for level 1:  the number of
    // leaf nodes just filled
    RecordNum nEntriesParent = level.iNode + 1;

    if (nEntriesParent == 1) {
        // The leaf we just filled turns out to be the root.
        swapRoot();
        return;
    }

    // REVIEW:  distinguish leaf fillFactor from non-leaf fillFactor?

    SharedSegInputStream pParentInputStream =
        pLeafLevel->getParentKeyStream();
    assert(pParentInputStream);
    // feed buffered entries into level 1, and build up balanced from there
    buildBalanced(*pParentInputStream,1,nEntriesParent,fillFactor);
}

void BTreeBuilder::buildUnbalanced	(	ByteInputStream &	sortedStream,
		RecordNum	nEntries,
		double	fillFactor
	)			[private]

Definition at line 154 of file BTreeBuilder.cpp.

References BTreeBuildLevel::cbReserved, getLevel(), BTreeAccessBase::getSegment(), growTree(), BTreeBuildLevel::indexLastKey(), levels, BTreeBuildLevel::nEntriesTotal, BTreeBuildLevel::processInput(), and swapRoot().

Referenced by build().

{
    // TODO:  common fcn
    // calculate amount of space to reserve on each leaf from fillfactor
    uint cbReserved = getSegment()->getUsablePageSize() - sizeof(BTreeNode);
    cbReserved = uint(cbReserved*(1-fillFactor));

    // start with just a leaf level
    growTree();
    BTreeBuildLevel &level = getLevel(0);
    level.cbReserved = cbReserved;
    level.nEntriesTotal = nEntriesTotal;
    level.processInput(sortedInputStream);

    // NOTE:  It's important to realize that growTree() could be called inside
    // this loop, so it's necessary to recompute levels.size() after each
    // iteration.
    for (uint i = 0; i < levels.size(); ++i) {
        BTreeBuildLevel &level = getLevel(i);
        level.indexLastKey(true);
    }

    swapRoot();
}

void BTreeBuilder::processInput

(

ByteInputStream &

sortedStream

)

[private]

BTreeBuildLevel & BTreeBuilder::getLevel

(

uint

i

)

[inline, private]

Definition at line 164 of file BTreeBuilder.h.

References levels.

Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), buildBalanced(), buildTwoPass(), buildUnbalanced(), growTree(), BTreeBuildLevel::indexLastChild(), DynamicBuildLevel::indexLastKey(), FixedBuildLevel::indexLastKey(), and swapRoot().

{
    return *(levels[i]);
}

void BTreeBuilder::growTree

(

)

[private]

Definition at line 335 of file BTreeBuilder.cpp.

References BTreeBuildLevel::allocatePage(), BTreeBuildLevel::cbReserved, DynamicBuildLevel, getLevel(), getRootHeight(), BTreeBuildLevel::iLevel, levels, BTreeAccessBase::pLeafNodeAccessor, and BTreeAccessBase::pNonLeafNodeAccessor.

Referenced by buildUnbalanced(), and DynamicBuildLevel::indexLastKey().

{
    BTreeNodeAccessor &nodeAccessor =
        levels.size() ? *pNonLeafNodeAccessor : *pLeafNodeAccessor;
    levels.resize(levels.size() + 1);
    levels[getRootHeight()].reset(new DynamicBuildLevel(*this,nodeAccessor));
    BTreeBuildLevel &level = *levels.back();
    level.iLevel = getRootHeight();
    if (level.iLevel) {
        // inherit cbReserved
        level.cbReserved = getLevel(level.iLevel - 1).cbReserved;
    }
    level.allocatePage();
}

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().

{
    BTreeBuildLevel &rootLevel = getLevel(getRootHeight());
    if (getRootPageId() == NULL_PAGE_ID) {
        // No rootPageId has been assigned yet, so no need to copy.
        treeDescriptor.rootPageId = rootLevel.pageId;
        return;
    }

    // We're supposed to preserve the PageId of the existing root, so
    // swap buffers with the original root.
    BTreePageLock reusedRootPageLock(treeDescriptor.segmentAccessor);
    reusedRootPageLock.lockExclusive(getRootPageId());
    BTreeNode &reusedRoot = reusedRootPageLock.getNodeForWrite();
    assert(!reusedRoot.nEntries);
    reusedRootPageLock.swapBuffers(rootLevel.pageLock);

    // deallocate the abandonded tempRoot
    rootLevel.pageLock.deallocateLockedPage();
}

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().

{
    assert(node.height);
    assert(node.nEntries);
    PageId pageId = getChild(node,0);
    BTreePageLock pageLock;
    pageLock.accessSegment(treeDescriptor.segmentAccessor);
    if (node.height > 1) {
        pageLock.lockExclusive(pageId);
        truncateChildren(pageLock.getNodeForRead());
        pageLock.unlock();
    }
    while (pageId != NULL_PAGE_ID) {
        PageId nextPageId = getRightSibling(pageId);
        pageLock.deallocateUnlockedPage(pageId);
        pageId = nextPageId;
    }
}

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().

{
    // REVIEW jvs 24-Dec-2005:  Here we pre-scan the tree, dropping
    // the external pages.  This scan could be combined with
    // the main truncate traversal for better efficiency.
    BTreeReader reader(treeDescriptor);
    TupleProjectionAccessor projAccessor;
    projAccessor.bind(
        reader.getTupleAccessorForRead(),
        leafPageIdProj);
    TupleDescriptor projDesc;
    projDesc.projectFrom(treeDescriptor.tupleDescriptor, leafPageIdProj);
    TupleData projData(projDesc);
    BTreePageLock pageLock;
    pageLock.accessSegment(treeDescriptor.segmentAccessor);
    if (reader.searchFirst()) {
        do {
            projAccessor.unmarshal(projData);
            for (uint i = 0; i < projData.size(); ++i) {
                if (!projData[i].pData) {
                    continue;
                }
                PageId pageId = *reinterpret_cast<PageId const *>(
                    projData[i].pData);
                pageLock.deallocateUnlockedPage(pageId);
            }
        } while (reader.searchNext());
    }
}

void BTreeBuilder::build	(	ByteInputStream &	sortedStream,
		RecordNum	nEntries,
		double	fillFactor = 1.0
	)

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().

{
    assert(fillFactor <= 1.0);
    assert(fillFactor > 0);
    try {
        if (pLeafNodeAccessor->hasFixedWidthEntries()
            && pNonLeafNodeAccessor->hasFixedWidthEntries())
        {
            buildBalanced(sortedInputStream,0,nEntriesTotal,fillFactor);
        } else if (pNonLeafNodeAccessor->hasFixedWidthEntries()) {
            buildTwoPass(
                sortedInputStream,nEntriesTotal,fillFactor);
        } else {
            assert(!pLeafNodeAccessor->hasFixedWidthEntries());
            buildUnbalanced(sortedInputStream,nEntriesTotal,fillFactor);
        }
    } catch (...) {
        try {
            levels.clear();
        } catch (...) {
            // TODO:  trace suppressed excn
        }
        throw;
    }
    levels.clear();
}

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().

{
    assert(getRootPageId() == NULL_PAGE_ID);
    BTreePageLock pageLock;
    pageLock.accessSegment(treeDescriptor.segmentAccessor);
    treeDescriptor.rootPageId = pageLock.allocatePage(getPageOwnerId());
    BTreeNode &node = pageLock.getNodeForWrite();
    pLeafNodeAccessor->clearNode(
        node,getSegment()->getUsablePageSize());
}

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().

{
    if (pLeafPageIdProj) {
        truncateExternal(*pLeafPageIdProj);
    }
    BTreePageLock pageLock;
    pageLock.accessSegment(treeDescriptor.segmentAccessor);

    pageLock.lockExclusive(getRootPageId());

    // Try a read-only access to see if we can skip dirtying a page.
    BTreeNode const &rootReadOnly = pageLock.getNodeForRead();
    if (!rootReadOnly.height) {
        if (rootless) {
            pageLock.deallocateLockedPage();
            treeDescriptor.rootPageId = NULL_PAGE_ID;
            return;
        }
        if (!rootReadOnly.nEntries) {
            // root is already empty
            return;
        }
    }

    BTreeNode &root = pageLock.getNodeForWrite();
    if (root.height) {
        truncateChildren(root);
    }
    if (rootless) {
        pageLock.deallocateLockedPage();
        treeDescriptor.rootPageId = NULL_PAGE_ID;
    } else {
        pLeafNodeAccessor->clearNode(
            root,getSegment()->getUsablePageSize());
    }
}

FENNEL_BEGIN_NAMESPACE BTreeNodeAccessor & BTreeAccessBase::getLeafNodeAccessor

(

BTreeNode const &

node

)

[inline, protected, inherited]

Gets the node accessor for a leaf node, asserting that the node really is a leaf.

Parameters:

node

leaf node to access

Returns:

node accessor

Definition at line 32 of file BTreeAccessBaseImpl.h.

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

Referenced by BTreeReader::accessLeafTuple(), BTreeWriter::deleteCurrent(), and BTreeWriter::updateCurrent().

{
    assert(!node.height);
    return *pLeafNodeAccessor;
}

BTreeNodeAccessor & BTreeAccessBase::getNonLeafNodeAccessor

(

BTreeNode const &

node

)

[inline, protected, inherited]

Gets the node accessor for a non-leaf node, asserting that the node really is a non-leaf.

Parameters:

node

non-leaf node to access

Returns:

node accessor

Definition at line 39 of file BTreeAccessBaseImpl.h.

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

Referenced by BTreeAccessBase::getChild(), and BTreeWriter::grow().

{
    assert(node.height);
    return *pNonLeafNodeAccessor;
}

BTreeNodeAccessor & BTreeAccessBase::getNodeAccessor

(

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:

node

node to access

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().

{
    if (node.height) {
        return *pNonLeafNodeAccessor;
    } else {
        return *pLeafNodeAccessor;
    }
}

PageId BTreeAccessBase::getChildForCurrent

(

)

[inline, protected, inherited]

Gets the child PageId corresponding to the current key in a non-leaf node.

Assumes that accessTuple has already been called on pNonLeafNodeAccessor (but can't assert this), so use with caution.

Returns:

child PageId

Reimplemented in BTreeNonLeafReader.

Definition at line 56 of file BTreeAccessBaseImpl.h.

References BTreeAccessBase::pChildAccessor, TupleDatum::pData, BTreeAccessBase::pNonLeafNodeAccessor, and AttributeAccessor::unmarshalValue().

Referenced by BTreeAccessBase::getChild(), BTreeNonLeafReader::getChildForCurrent(), and BTreeReader::searchForKeyTemplate().

{
    TupleDatum &childDatum = pNonLeafNodeAccessor->tupleData.back();
    pChildAccessor->unmarshalValue(
        pNonLeafNodeAccessor->tupleAccessor,childDatum);
    return *reinterpret_cast<PageId const *>(childDatum.pData);
}

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

Accesses a non-leaf tuple and gets its child PageId.

Parameters:

	node	non-leaf node to access
	iChild	0-based index of tuple to access

Returns:

child PageId of accessed tuple

Definition at line 64 of file BTreeAccessBaseImpl.h.

References BTreeNodeAccessor::accessTuple(), BTreeAccessBase::getChildForCurrent(), and BTreeAccessBase::getNonLeafNodeAccessor().

Referenced by BTreeAccessBase::getFirstChild(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKeyTemplate(), truncateChildren(), and BTreeVerifier::verifyChildren().

{
    getNonLeafNodeAccessor(node).accessTuple(node,iChild);
    return getChildForCurrent();
}

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().

{
    return getSegment()->getPageSuccessor(pageId);
}

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

Sets the right sibling of a node.

Parameters:

	leftNode	node whose right sibling is to be set
	leftPageId	PageId corresponding to leftNode
	rightPageId	PageId of new right sibling

Definition at line 75 of file BTreeAccessBaseImpl.h.

References BTreeAccessBase::getSegment(), and BTreeNode::rightSibling.

Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), and BTreeWriter::splitCurrentNode().

{
    getSegment()->setPageSuccessor(leftPageId,rightPageId);
    leftNode.rightSibling = rightPageId;
}

PageId BTreeAccessBase::getFirstChild

(

PageId

pageId

)

[protected, inherited]

Gets the first child of a non-leaf node.

Parameters:

pageId

PageId of non-leaf node

Returns:

PageId of node's first child

Definition at line 126 of file BTreeAccessBase.cpp.

References BTreeAccessBase::getChild(), SegNodeLock< Node >::getNodeForRead(), BTreeNode::height, SegPageLock::lockShared(), BTreeNode::nEntries, NULL_PAGE_ID, BTreeNode::rightSibling, BTreeDescriptor::segmentAccessor, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeReader::searchForKeyTemplate(), and BTreeVerifier::verifyChildren().

{
    BTreePageLock pageLock(treeDescriptor.segmentAccessor);
    while (parentPageId != NULL_PAGE_ID) {
        pageLock.lockShared(parentPageId);
        BTreeNode const &node = pageLock.getNodeForRead();
        assert(node.height);
        if (node.nEntries) {
            return getChild(node,0);
        }
        parentPageId = node.rightSibling;
    }
    return NULL_PAGE_ID;
}

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().

{
    return treeDescriptor.segmentAccessor.pSegment;
}

SharedCacheAccessor BTreeAccessBase::getCacheAccessor

(

)

const [inline, inherited]

Returns:

the CacheAccessor used to access the BTree's pages

Definition at line 239 of file BTreeAccessBase.h.

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

Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), VariableBuildLevel::getParentKeyStream(), and VariableBuildLevel::VariableBuildLevel().

{
    return treeDescriptor.segmentAccessor.pCacheAccessor;
}

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().

{
    return treeDescriptor.rootPageId;
}

void BTreeAccessBase::setRootPageId

(

PageId

rootPageId

)

[inherited]

Updates the BTree's root PageId.

Definition at line 141 of file BTreeAccessBase.cpp.

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

{
    treeDescriptor.rootPageId = rootPageId;
}

SegmentId BTreeAccessBase::getSegmentId

(

)

const [inline, inherited]

Returns:

SegmentId of segment storing the BTree

Definition at line 249 of file BTreeAccessBase.h.

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

{
    return treeDescriptor.segmentId;
}

PageOwnerId BTreeAccessBase::getPageOwnerId

(

)

const [inline, inherited]

Returns:

PageOwnerId used to mark pages of the BTree

Definition at line 254 of file BTreeAccessBase.h.

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

Referenced by BTreeBuildLevel::allocatePage(), createEmptyRoot(), BTreeWriter::grow(), and BTreeWriter::splitCurrentNode().

{
    return treeDescriptor.pageOwnerId;
}

TupleDescriptor const & BTreeAccessBase::getTupleDescriptor

(

)

const [inline, inherited]

Returns:

TupleDescriptor for tuples stored by this BTree

Definition at line 259 of file BTreeAccessBase.h.

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

Referenced by BTreeWriter::describeParticipant(), and BTreeAccessBase::validateTupleSize().

{
    return treeDescriptor.tupleDescriptor;
}

TupleDescriptor const & BTreeAccessBase::getKeyDescriptor

(

)

const [inline, inherited]

Returns:

TupleDescriptor for keys indexed by this BTree

Definition at line 264 of file BTreeAccessBase.h.

References BTreeAccessBase::keyDescriptor.

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

{
    return keyDescriptor;
}

TupleProjection const & BTreeAccessBase::getKeyProjection

(

)

const [inline, inherited]

Returns:

TupleProjection from getTupleDescriptor() to getKeyDescriptor()

Definition at line 269 of file BTreeAccessBase.h.

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

Referenced by BTreeAccessBase::BTreeAccessBase(), and BTreeWriter::describeParticipant().

{
    return treeDescriptor.keyProjection;
}

void BTreeAccessBase::validateTupleSize

(

TupleAccessor const &

tupleAccessor

)

[inherited]

Validates that a particular tuple can fit in this BTree, throwing a TupleOverflowExcn if not.

Parameters:

tupleAccessor

TupleAccessor referencing tuple to be inserted

Definition at line 146 of file BTreeAccessBase.cpp.

References BTreeAccessBase::cbTupleMax, TupleAccessor::getCurrentByteCount(), BTreeAccessBase::getTupleDescriptor(), and TupleAccessor::unmarshal().

Referenced by BTreeWriter::insertTupleFromBuffer(), and BTreeBuildLevel::processInput().

{
    uint cbTuple = tupleAccessor.getCurrentByteCount();
    if (cbTuple > cbTupleMax) {
        TupleData tupleData(getTupleDescriptor());
        tupleAccessor.unmarshal(tupleData);
        throw TupleOverflowExcn(
            getTupleDescriptor(),
            tupleData,
            cbTuple,
            cbTupleMax);
    }
}

---

Friends And Related Function Documentation

friend class BTreeBuildLevel [friend]

Definition at line 53 of file BTreeBuilder.h.

friend class FixedBuildLevel [friend]

Definition at line 54 of file BTreeBuilder.h.

Referenced by buildBalanced().

friend class VariableBuildLevel [friend]

Definition at line 55 of file BTreeBuilder.h.

Referenced by buildTwoPass().

friend class DynamicBuildLevel [friend]

Definition at line 56 of file BTreeBuilder.h.

Referenced by growTree().

---

Member Data Documentation

std::vector<SharedBTreeBuildLevel> BTreeBuilder::levels [private]

Definition at line 58 of file BTreeBuilder.h.

Referenced by build(), buildBalanced(), buildTwoPass(), buildUnbalanced(), getLevel(), and growTree().

SharedSegment BTreeBuilder::pTempSegment [private]

Definition at line 60 of file BTreeBuilder.h.

Referenced by BTreeBuilder(), VariableBuildLevel::getParentKeyStream(), and VariableBuildLevel::VariableBuildLevel().

BTreeDescriptor BTreeAccessBase::treeDescriptor [protected, inherited]

Descriptor for tree being accessed.

Definition at line 51 of file BTreeAccessBase.h.

Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeAccessBase::BTreeAccessBase(), BTreeBuildLevel::BTreeBuildLevel(), BTreeReader::BTreeReader(), buildBalanced(), createEmptyRoot(), BTreeAccessBase::getCacheAccessor(), BTreeAccessBase::getFirstChild(), BTreeAccessBase::getKeyProjection(), BTreeAccessBase::getPageOwnerId(), BTreeAccessBase::getRootPageId(), BTreeAccessBase::getSegment(), BTreeAccessBase::getSegmentId(), BTreeAccessBase::getTupleDescriptor(), BTreeWriter::grow(), BTreeWriter::lockParentPage(), BTreeAccessBase::setRootPageId(), BTreeWriter::splitCurrentNode(), swapRoot(), truncate(), truncateChildren(), truncateExternal(), and BTreeVerifier::verifyNode().

TupleDescriptor BTreeAccessBase::keyDescriptor [protected, inherited]

Descriptor for pure keys (common across leaf and non-leaf tuples).

Definition at line 56 of file BTreeAccessBase.h.

Referenced by BTreeReader::binarySearch(), BTreeAccessBase::BTreeAccessBase(), BTreeReader::BTreeReader(), BTreeVerifier::BTreeVerifier(), BTreeWriter::checkMonotonicity(), BTreeReader::compareFirstKey(), BTreeAccessBase::getKeyDescriptor(), BTreeWriter::insertTupleFromBuffer(), BTreeWriter::lockParentPage(), BTreeReader::searchForKeyTemplate(), and BTreeVerifier::verifyNode().

AttributeAccessor const* BTreeAccessBase::pChildAccessor [protected, inherited]

Accessor for the attribute of non-leaf tuples which stores the child PageId.

Definition at line 62 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase(), BTreeAccessBase::getChildForCurrent(), and BTreeWriter::splitCurrentNode().

TupleProjectionAccessor BTreeAccessBase::leafKeyAccessor [protected, inherited]

Accessor for keys of tuples stored in leaves.

Definition at line 67 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase().

boost::scoped_ptr<BTreeNodeAccessor> BTreeAccessBase::pNonLeafNodeAccessor [protected, inherited]

Accessor for non-leaf nodes.

Definition at line 72 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase(), BTreeWriter::BTreeWriter(), build(), buildBalanced(), BTreeAccessBase::getChildForCurrent(), BTreeAccessBase::getNodeAccessor(), BTreeNonLeafReader::getNonLeafNodeAccessor(), BTreeAccessBase::getNonLeafNodeAccessor(), BTreeNonLeafReader::getTupleAccessorForRead(), growTree(), VariableBuildLevel::indexLastKey(), BTreeWriter::splitCurrentNode(), and BTreeBuildLevel::unmarshalLastKey().

boost::scoped_ptr<BTreeNodeAccessor> BTreeAccessBase::pLeafNodeAccessor [protected, inherited]

Accessor for leaf nodes.

Definition at line 77 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase(), BTreeWriter::BTreeWriter(), build(), buildBalanced(), buildTwoPass(), createEmptyRoot(), BTreeWriter::deleteLogged(), BTreeReader::endSearch(), BTreeAccessBase::getLeafNodeAccessor(), BTreeAccessBase::getNodeAccessor(), BTreeReader::getTupleAccessorForRead(), growTree(), BTreeWriter::insertTupleData(), BTreeWriter::insertTupleFromBuffer(), and truncate().

uint BTreeAccessBase::cbTupleMax [protected, inherited]

Maximum size for a leaf-level tuple.

Definition at line 82 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase(), and BTreeAccessBase::validateTupleSize().

---

The documentation for this class was generated from the following files:

• /home/pub/open/dev/fennel/btree/BTreeBuilder.h
• /home/pub/open/dev/fennel/btree/BTreeBuilder.cpp

---