BTreeNodeAccessor Class Reference

BTreeNodeAccessor is an abstract base class for accessing the sorted tuple data stored on a BTreeNode. More...

#include <BTreeNodeAccessor.h>

Inheritance diagram for BTreeNodeAccessor:


Public Types
enum	Capacity { CAN_FIT, CAN_FIT_WITH_COMPACTION, CAN_NOT_FIT }
	Enumeration used to classify the storage state of a node which is targeted for insertion. More...
Public Member Functions
virtual	~BTreeNodeAccessor ()
uint	getKeyCount (BTreeNode const &node) const
	Gets the number of keys stored on a node.
virtual void	clearNode (BTreeNode &node, uint cbPage)
	Clears the contents of a node, converting it to an empty root.
virtual PBuffer	allocateEntry (BTreeNode &node, uint iEntry, uint cbEntry)=0
	Allocates space for a new tuple.
virtual void	deallocateEntry (BTreeNode &node, uint iEntry)=0
	Deallocates the space for an existing tuple.
virtual PConstBuffer	getEntryForRead (BTreeNode const &node, uint iEntry)=0
	Gets the location of a stored tuple.
virtual void	onInit ()
	Receives notification from BTreeAccessBase after tupleDescriptor has been set up.
void	dumpNode (std::ostream &os, BTreeNode const &node, PageId pageId)
	Dumps the contents of a node.
virtual bool	hasFixedWidthEntries () const=0
	Returns: true iff this NodeAccessor always stores tuples in fixed-width slots (even if the tuples themselves are variable-length)
virtual void	accessTuple (BTreeNode const &node, uint iEntry)=0
	Binds tupleAccessor to a stored tuple.
virtual uint	binarySearch (BTreeNode const &node, TupleDescriptor const &keyDescriptor, TupleData const &searchKey, DuplicateSeek dupSeek, bool leastUpper, TupleData &scratchKey, bool &found)=0
	Searches for a tuple based on a key.
virtual int	compareFirstKey (BTreeNode const &node, TupleDescriptor const &keyDescriptor, TupleData const &searchKey, TupleData &scratchKey)=0
	Compare first key on a node to provided search key.
virtual void	accessTupleInline (BTreeNode const &node, uint iEntry)=0
	Sets tuple accessor to provided node entry.
virtual Capacity	calculateCapacity (BTreeNode const &node, uint cbEntry)=0
	Determines whether a tuple can be inserted into a node.
virtual uint	getEntryByteCount (uint cbTuple)=0
	Determines the storage required for a tuple, including any overhead.
virtual void	unmarshalKey (TupleData &keyData)=0
	Unmarshals the key for the current tuple after a call to accessTuple.
virtual void	compactNode (BTreeNode &node, BTreeNode &scratchNode)
	Performs compaction on a node.
virtual void	splitNode (BTreeNode &node, BTreeNode &newNode, uint cbNewTuple, bool monotonic)
	Splits a node.
Public Attributes
TupleDescriptor	tupleDescriptor
	Descriptor for tuples stored on nodes accessed by this.
TupleAccessor	tupleAccessor
	Accessor for tuples stored on nodes accessed by this.
TupleData	tupleData
	TupleData for tuples stored on nodes accessed by this.

Detailed Description

BTreeNodeAccessor is an abstract base class for accessing the sorted tuple data stored on a BTreeNode.

Derived classes fill in the implementation details.

The general idea is that low-level management of node data is orthogonal to high-level BTree algorithms, so it should be easy to plug in new node representations (fixed-width, variable-width, compressed, etc.). An alternate way of expressing this would be to define all of the high-level BTree classes as templates, with BTreeNodeAccessor as a template parameter. This would give the ultimate efficiency, but at the price of code bloat (number of high-level classes times number of BTreeNodeAccessor implementations) and higher complexity. A virtual interface was chosen instead, but still with performance in mind (e.g. the binarySearch method is delegated to BTreeNodeAccessor so that all tuple access within one node search can be computed inline).

Definition at line 54 of file BTreeNodeAccessor.h.

Member Enumeration Documentation

enum BTreeNodeAccessor::Capacity

Enumeration used to classify the storage state of a node which is targeted for insertion.

Enumerator:

CAN_FIT	The tuple can fit without compaction.
CAN_FIT_WITH_COMPACTION	The tuple can fit, but only after compaction.
CAN_NOT_FIT	The tuple can't fit. Compaction wouldn't help.

Definition at line 238 of file BTreeNodeAccessor.h.

00238                   {
00242         CAN_FIT,
00246         CAN_FIT_WITH_COMPACTION,
00247 
00251         CAN_NOT_FIT
00252     };

Constructor & Destructor Documentation

BTreeNodeAccessor::~BTreeNodeAccessor ( ) [virtual]

Definition at line 30 of file BTreeNodeAccessor.cpp.

00031 {
00032 }

Member Function Documentation

uint BTreeNodeAccessor::getKeyCount ( BTreeNode const & node ) const [inline]

Gets the number of keys stored on a node.

This may be one less than the number of tuples, since in the rightmost node on a non-leaf level, we pretend the last key is +infinity, so the actual stored key is ignored. But the last tuple is still stored, and its child PageId is used.

Parameters:

node

the node to access

Returns:: number of keys stored on node

Definition at line 308 of file BTreeNodeAccessor.h.

References BTreeNode::height, BTreeNode::nEntries, NULL_PAGE_ID, and BTreeNode::rightSibling.

Referenced by BTreeWriter::lockParentPage(), BTreeWriter::splitCurrentNode(), and BTreeVerifier::verifyNode().

00309 {
00310     if (node.height && (node.rightSibling == NULL_PAGE_ID)) {
00311         // For non-leaf nodes on the rightmost fringe, we pretend the last
00312         // key is +infinity, and ignore whatever's actually stored
00313         // there (except for its child PageId).
00314         assert(node.nEntries);
00315         return node.nEntries - 1;
00316     }
00317     return node.nEntries;
00318 }

void BTreeNodeAccessor::clearNode	(	BTreeNode &	node,
		uint	cbPage
	)			`[virtual]`

Clears the contents of a node, converting it to an empty root.

Parameters:

	node	the node to clear
	cbPage	number of usable bytes per page in segment storing BTree

Reimplemented in BTreeHeapNodeAccessor.

Definition at line 34 of file BTreeNodeAccessor.cpp.

References BTreeNode::cbCompactFree, BTreeNode::cbTotalFree, BTreeNode::height, MAXU, BTreeNode::nEntries, NULL_PAGE_ID, and BTreeNode::rightSibling.

Referenced by BTreeBuildLevel::allocatePage(), BTreeBuilder::buildBalanced(), BTreeHeapNodeAccessor::clearNode(), BTreeWriter::compactNode(), BTreeWriter::grow(), and BTreeWriter::splitCurrentNode().

00035 {
00036     node.rightSibling = NULL_PAGE_ID;
00037     node.nEntries = 0;
00038     node.height = 0;
00039     node.cbTotalFree = cbPage - sizeof(BTreeNode);
00040     node.cbCompactFree = MAXU;
00041 }

virtual PBuffer BTreeNodeAccessor::allocateEntry	(	BTreeNode &	node,
		uint	iEntry,
		uint	cbEntry
	)			`[pure virtual]`

Allocates space for a new tuple.

Parameters:

	node	the node in which the tuple will be stored
	iEntry	0-based index at which tuple will be stored
	cbEntry	number of bytes in stored tuple

Returns:: location at which tuple should be stored

Implemented in BTreeCompactNodeAccessor, and BTreeHeapNodeAccessor.

Referenced by BTreeWriter::attemptInsertWithoutSplit(), compactNode(), BTreeWriter::grow(), BTreeBuildLevel::indexLastChild(), BTreeBuildLevel::processInput(), splitNode(), and BTreeWriter::updateCurrent().

virtual void BTreeNodeAccessor::deallocateEntry	(	BTreeNode &	node,
		uint	iEntry
	)			`[pure virtual]`

Deallocates the space for an existing tuple.

Parameters:

	node	the node from which to deallocate the tuple
	iEntry	0-based index of tuple to be deallocated

Implemented in BTreeCompactNodeAccessor, and BTreeHeapNodeAccessor.

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

virtual PConstBuffer BTreeNodeAccessor::getEntryForRead	(	BTreeNode const &	node,
		uint	iEntry
	)			`[pure virtual]`

Gets the location of a stored tuple.

Parameters:

	node	the node to access
	iEntry	0-based index of tuple to access

Returns:: location of stored tuple

Referenced by dumpNode(), BTreeWriter::splitCurrentNode(), and BTreeWriter::updateCurrent().

void BTreeNodeAccessor::onInit ( ) [virtual]

Receives notification from BTreeAccessBase after tupleDescriptor has been set up.

Reimplemented in BTreeCompactNodeAccessor.

Definition at line 43 of file BTreeNodeAccessor.cpp.

References TupleData::compute(), TupleAccessor::compute(), tupleAccessor, tupleData, and tupleDescriptor.

Referenced by BTreeCompactNodeAccessor::onInit().

00044 {
00045     tupleAccessor.compute(tupleDescriptor);
00046     tupleData.compute(tupleDescriptor);
00047 }

void BTreeNodeAccessor::dumpNode	(	std::ostream &	os,
		BTreeNode const &	node,
		PageId	pageId
	)

Dumps the contents of a node.

Parameters:

	os	output stream receiving the dump
	node	the node to dump
	pageId	PageId of the node being dumped

Definition at line 49 of file BTreeNodeAccessor.cpp.

References BTreeNode::cbCompactFree, BTreeNode::cbTotalFree, getEntryForRead(), BTreeNode::height, isMAXU(), BTreeNode::nEntries, NULL_PAGE_ID, TuplePrinter::print(), BTreeNode::rightSibling, TupleAccessor::setCurrentTupleBuf(), tupleAccessor, tupleData, tupleDescriptor, and TupleAccessor::unmarshal().

Referenced by BTreeWriter::attemptInsertWithoutSplit(), BTreeWriter::grow(), BTreeWriter::splitCurrentNode(), and BTreeVerifier::verifyNode().

00051 {
00052     os << "PageId:  " << pageId << std::endl;
00053     if (node.rightSibling == NULL_PAGE_ID) {
00054         os << "rightSibling:  <null>" << std::endl;
00055     } else {
00056         os << "rightSibling:  " << node.rightSibling << std::endl;
00057     }
00058     os << "nEntries:  " << node.nEntries << std::endl;
00059     os << "height:  " << node.height << std::endl;
00060     os << "cbTotalFree:  " << node.cbTotalFree << std::endl;
00061     if (!isMAXU(node.cbCompactFree)) {
00062         os << "cbCompactFree:  " << node.cbCompactFree << std::endl;
00063     }
00064     os << std::endl;
00065     TuplePrinter tuplePrinter;
00066     // TODO:  print "+infinity" for last key on right fringe
00067     for (uint i = 0; i < node.nEntries; ++i) {
00068         PConstBuffer pEntry = getEntryForRead(node,i);
00069         os << "offset = "
00070            << pEntry - reinterpret_cast<PConstBuffer>(&node) << std::endl;
00071         tupleAccessor.setCurrentTupleBuf(pEntry);
00072         tupleAccessor.unmarshal(tupleData);
00073         tuplePrinter.print(os,tupleDescriptor,tupleData);
00074         os << std::endl;
00075     }
00076     os << std::endl;
00077 }

virtual bool BTreeNodeAccessor::hasFixedWidthEntries ( ) const [pure virtual]

Returns:: true iff this NodeAccessor always stores tuples in fixed-width slots (even if the tuples themselves are variable-length)

Implemented in BTreeCompactNodeAccessor, and BTreeHeapNodeAccessor.

Referenced by BTreeBuilder::buildTwoPass(), and BTreeWriter::updateCurrent().

virtual void BTreeNodeAccessor::accessTuple	(	BTreeNode const &	node,
		uint	iEntry
	)			`[pure virtual]`

Binds tupleAccessor to a stored tuple.

Parameters:

	node	the node to access
	iEntry	0-based index of tuple to access

Referenced by BTreeReader::accessLeafTuple(), compactNode(), BTreeAccessBase::getChild(), BTreeWriter::grow(), BTreeWriter::lockParentPage(), BTreeWriter::splitCurrentNode(), splitNode(), BTreeBuildLevel::unmarshalLastKey(), BTreeVerifier::verifyChildren(), and BTreeVerifier::verifyNode().

virtual uint BTreeNodeAccessor::binarySearch	(	BTreeNode const &	node,
		TupleDescriptor const &	keyDescriptor,
		TupleData const &	searchKey,
		DuplicateSeek	dupSeek,
		bool	leastUpper,
		TupleData &	scratchKey,
		bool &	found
	)			`[pure virtual]`

Searches for a tuple based on a key.

Parameters:

	node	the node to search
	keyDescriptor	key descriptor to be used for comparisons
	searchKey	key to search for
	dupSeek	what to do if duplicates are found
	leastUpper	whether to position on least upper bound or greatest lower bound
	scratchKey	key to be used as a temp variable in comparisons
	found	same semantics as BTreeReader::binarySearch

Returns:: result of search as 0-based index of tuple on node

Referenced by BTreeReader::binarySearch(), and BTreeWriter::lockParentPage().

virtual int BTreeNodeAccessor::compareFirstKey	(	BTreeNode const &	node,
		TupleDescriptor const &	keyDescriptor,
		TupleData const &	searchKey,
		TupleData &	scratchKey
	)			`[pure virtual]`

Compare first key on a node to provided search key.

Parameters:

	node	the node to search
	keyDescriptor	key descriptor to be used for comparisons
	searchKey	key to search for
	scratchKey	key to be used as a temp variable in comparison

Returns:: result of comparing searchKey with the first key (0, -1, or 1)

Referenced by BTreeReader::compareFirstKey().

virtual void BTreeNodeAccessor::accessTupleInline	(	BTreeNode const &	node,
		uint	iEntry
	)			`[pure virtual]`

Sets tuple accessor to provided node entry.

Parameters:

	node	the current node positioned on
	iEntry	the entry within the node to set the tuple accessor to

Referenced by BTreeReader::accessTupleInline().

virtual Capacity BTreeNodeAccessor::calculateCapacity	(	BTreeNode const &	node,
		uint	cbEntry
	)			`[pure virtual]`

Determines whether a tuple can be inserted into a node.

Parameters:

	node	the target node
	cbEntry	the number of bytes in the tuple to be inserted

Returns:: see Capacity

Implemented in BTreeCompactNodeAccessor, and BTreeHeapNodeAccessor.

Referenced by BTreeWriter::attemptInsertWithoutSplit(), BTreeBuildLevel::isNodeFull(), BTreeWriter::splitCurrentNode(), and BTreeWriter::updateCurrent().

virtual uint BTreeNodeAccessor::getEntryByteCount ( uint cbTuple ) [pure virtual]

Determines the storage required for a tuple, including any overhead.

Parameters:

cbTuple

number of bytes without overhead

Returns:: number of bytes with overhead

Implemented in BTreeCompactNodeAccessor, and BTreeHeapNodeAccessor.

Referenced by splitNode().

virtual void BTreeNodeAccessor::unmarshalKey ( TupleData & keyData ) [pure virtual]

Unmarshals the key for the current tuple after a call to accessTuple.

Parameters:

keyData

receives the unmarshalled key

Referenced by BTreeWriter::checkMonotonicity(), BTreeWriter::grow(), BTreeWriter::lockParentPage(), BTreeWriter::positionSearchKey(), BTreeWriter::splitCurrentNode(), BTreePrefetchSearchExecStream::testNonLeafInterval(), BTreeBuildLevel::unmarshalLastKey(), BTreeVerifier::verifyChildren(), and BTreeVerifier::verifyNode().

void BTreeNodeAccessor::compactNode	(	BTreeNode &	node,
		BTreeNode &	scratchNode
	)			`[virtual]`

Performs compaction on a node.

Parameters:

	node	the fragmented node to be compacted
	scratchNode	receives a compacted copy of node

Reimplemented in BTreeCompactNodeAccessor.

Definition at line 82 of file BTreeNodeAccessor.cpp.

References accessTuple(), allocateEntry(), BTreeNode::cbCompactFree, BTreeNode::cbTotalFree, TupleAccessor::getCurrentByteCount(), TupleAccessor::getCurrentTupleBuf(), isMAXU(), BTreeNode::nEntries, and tupleAccessor.

Referenced by BTreeWriter::compactNode().

00083 {
00084     assert(!scratchNode.nEntries);
00085     for (uint i = 0; i < node.nEntries; ++i) {
00086         accessTuple(node,i);
00087         uint cbTuple = tupleAccessor.getCurrentByteCount();
00088         PBuffer pBuffer = allocateEntry(scratchNode,i,cbTuple);
00089         memcpy(pBuffer,tupleAccessor.getCurrentTupleBuf(),cbTuple);
00090     }
00091 
00092     if (!isMAXU(node.cbCompactFree)) {
00093         node.cbCompactFree = node.cbTotalFree;
00094     }
00095     memcpy(&scratchNode,&node,sizeof(BTreeNode));
00096 }

void BTreeNodeAccessor::splitNode	(	BTreeNode &	node,
		BTreeNode &	newNode,
		uint	cbNewTuple,
		bool	monotonic
	)			`[virtual]`

Splits a node.

Parameters:

	node	the node to be split
	newNode	an empty node which receives half of the tuple data.
	cbNewTuple	number of bytes which will be required to store the tuple which caused this split
	monotonic	if true, inserts are always increasing so optimize the split accordingly

Definition at line 104 of file BTreeNodeAccessor.cpp.

References accessTuple(), allocateEntry(), BTreeNode::cbTotalFree, TupleAccessor::getCurrentByteCount(), TupleAccessor::getCurrentTupleBuf(), getEntryByteCount(), BTreeNode::height, max(), BTreeNode::nEntries, and tupleAccessor.

Referenced by BTreeWriter::splitCurrentNode().

00108 {
00109     assert(!newNode.nEntries);
00110     assert(node.nEntries > 1);
00111     newNode.height = node.height; // split should be of the same height
00112 
00113     // if monotonic, for leaf page,
00114     // don't actually split the page; leave the left
00115     // page as is and force all inserts to go into the new page
00116     // on the right
00117     // for internal node,
00118     // put the last entry to the right page.
00119     if (monotonic && node.height == 0) {
00120         return;
00121     }
00122 
00123     // Calculate the balance point in bytes
00124     uint cbNeeded = getEntryByteCount(cbNewTuple);
00125     uint cbBalance = cbNeeded;
00126     if (!monotonic) {
00127         cbBalance = (node.cbTotalFree + newNode.cbTotalFree - cbNeeded) / 2;
00128         cbBalance = std::max(cbNeeded,cbBalance);
00129     }
00130 
00131     // Calculate the corresponding split point in terms of tuples
00132     uint cbFreeAfterSplit = node.cbTotalFree;
00133     uint iSplitTuple = node.nEntries;
00134     while (cbFreeAfterSplit < cbBalance) {
00135         --iSplitTuple;
00136         accessTuple(node,iSplitTuple);
00137         uint cbTuple = tupleAccessor.getCurrentByteCount();
00138         cbFreeAfterSplit += getEntryByteCount(cbTuple);
00139     }
00140 
00141     // Copy tuples accordingly.
00142     for (uint i = iSplitTuple; i < node.nEntries; ++i) {
00143         accessTuple(node,i);
00144         uint cbTuple = tupleAccessor.getCurrentByteCount();
00145         PBuffer pNewEntry = allocateEntry(newNode,newNode.nEntries,cbTuple);
00146         memcpy(pNewEntry,tupleAccessor.getCurrentTupleBuf(),cbTuple);
00147     }
00148 
00149     // Truncate old node.  NOTE: This isn't kosher, since it assumes too much
00150     // about data layout, but this whole method is going to go away soon
00151     // anyway.
00152     node.nEntries = iSplitTuple;
00153     node.cbTotalFree = cbFreeAfterSplit;
00154 }