BTreeCompactNodeAccessor Class Reference

BTreeCompactNodeAccessor maintains the data on a BTreeNode as a compact array of fixed-length entries, with all free space contiguous at the end of the page. More...

#include <BTreeCompactNodeAccessor.h>

Inheritance diagram for BTreeCompactNodeAccessor:

List of all members.


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
	BTreeCompactNodeAccessor ()
PConstBuffer	getEntryForReadInline (BTreeNode const &node, uint iEntry)
virtual void	onInit ()
	Receives notification from BTreeAccessBase after tupleDescriptor has been set up.
virtual PBuffer	allocateEntry (BTreeNode &node, uint iEntry, uint cbEntry)
	Allocates space for a new tuple.
virtual void	deallocateEntry (BTreeNode &node, uint iEntry)
	Deallocates the space for an existing tuple.
virtual bool	hasFixedWidthEntries () const
	Returns: true iff this NodeAccessor always stores tuples in fixed-width slots (even if the tuples themselves are variable-length)
virtual Capacity	calculateCapacity (BTreeNode const &node, uint cbEntry)
	Determines whether a tuple can be inserted into a node.
virtual uint	getEntryByteCount (uint cbTuple)
	Determines the storage required for a tuple, including any overhead.
virtual void	compactNode (BTreeNode &node, BTreeNode &scratchNode)
	Performs compaction on a node.
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 PConstBuffer	getEntryForRead (BTreeNode const &node, uint iEntry)=0
	Gets the location of a stored tuple.
void	dumpNode (std::ostream &os, BTreeNode const &node, PageId pageId)
	Dumps the contents of a node.
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 void	unmarshalKey (TupleData &keyData)=0
	Unmarshals the key for the current tuple after a call to accessTuple.
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.
Private Attributes
uint	cbEntry
	Number of bytes per entry.

Detailed Description

BTreeCompactNodeAccessor maintains the data on a BTreeNode as a compact array of fixed-length entries, with all free space contiguous at the end of the page.

TODO: a high-performance template for builtin datatypes

Definition at line 40 of file BTreeCompactNodeAccessor.h.

Member Enumeration Documentation

enum BTreeNodeAccessor::Capacity [inherited]

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

BTreeCompactNodeAccessor::BTreeCompactNodeAccessor ( ) [explicit]

Definition at line 29 of file BTreeCompactNodeAccessor.cpp.

References cbEntry, and MAXU.

00030 {
00031     cbEntry = MAXU;
00032 }

Member Function Documentation

PConstBuffer BTreeCompactNodeAccessor::getEntryForReadInline	(	BTreeNode const &	node,
		uint	iEntry
	)			`[inline]`

Definition at line 65 of file BTreeCompactNodeAccessor.h.

References cbEntry, and BTreeNode::getDataForRead().

00067 {
00068     return node.getDataForRead() + iEntry*cbEntry;
00069 }

void BTreeCompactNodeAccessor::onInit ( ) [virtual]

Receives notification from BTreeAccessBase after tupleDescriptor has been set up.

Reimplemented from BTreeNodeAccessor.

Definition at line 34 of file BTreeCompactNodeAccessor.cpp.

References cbEntry, TupleAccessor::getMaxByteCount(), BTreeNodeAccessor::onInit(), and BTreeNodeAccessor::tupleAccessor.

00035 {
00036     BTreeNodeAccessor::onInit();
00037     cbEntry = tupleAccessor.getMaxByteCount();
00038 }

PBuffer BTreeCompactNodeAccessor::allocateEntry	(	BTreeNode &	node,
		uint	iEntry,
		uint	cbEntry
	)			`[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

Implements BTreeNodeAccessor.

Definition at line 40 of file BTreeCompactNodeAccessor.cpp.

References cbEntry, BTreeNode::cbTotalFree, BTreeNode::getDataForWrite(), and BTreeNode::nEntries.

00042 {
00043     assert(iEntry < node.nEntries + 1);
00044     assert(node.cbTotalFree >= cbEntry);
00045 
00046     // shift everything over to make room for the new entry
00047     PBuffer pBuffer = node.getDataForWrite() + iEntry*cbEntry;
00048     memmove(
00049         pBuffer + cbEntry,
00050         pBuffer,
00051         (node.nEntries - iEntry)*cbEntry);
00052 
00053     // update node control info
00054     node.nEntries++;
00055     node.cbTotalFree -= cbEntry;
00056     return pBuffer;
00057 }

void BTreeCompactNodeAccessor::deallocateEntry	(	BTreeNode &	node,
		uint	iEntry
	)			`[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

Implements BTreeNodeAccessor.

Definition at line 59 of file BTreeCompactNodeAccessor.cpp.

References cbEntry, BTreeNode::cbTotalFree, BTreeNode::getDataForWrite(), and BTreeNode::nEntries.

00061 {
00062     assert(iEntry < node.nEntries);
00063 
00064     // NOTE: this test is to avoid passing an address beyond the end of the
00065     // page to memmove.  It should be unnecessary, since in that case the
00066     // number of bytes to be moved is 0, but paranoid memmove
00067     // implementations might complain.
00068     if (iEntry != node.nEntries - 1) {
00069         // shift over everything after the entry to delete it
00070         PBuffer pBuffer = node.getDataForWrite() + iEntry*cbEntry;
00071         memmove(
00072             pBuffer,
00073             pBuffer + cbEntry,
00074             (node.nEntries - (iEntry + 1))*cbEntry);
00075     }
00076 
00077     // update node control info
00078     node.nEntries--;
00079     node.cbTotalFree += cbEntry;
00080 }

bool BTreeCompactNodeAccessor::hasFixedWidthEntries ( ) const [virtual]

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

Implements BTreeNodeAccessor.

Definition at line 82 of file BTreeCompactNodeAccessor.cpp.

00083 {
00084     return true;
00085 }

BTreeNodeAccessor::Capacity BTreeCompactNodeAccessor::calculateCapacity	(	BTreeNode const &	node,
		uint	cbEntry
	)			`[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

Implements BTreeNodeAccessor.

Definition at line 88 of file BTreeCompactNodeAccessor.cpp.

References BTreeNodeAccessor::CAN_FIT, BTreeNodeAccessor::CAN_NOT_FIT, and BTreeNode::cbTotalFree.

00089 {
00090     if (node.cbTotalFree >= cbEntry) {
00091         return CAN_FIT;
00092     } else {
00093         return CAN_NOT_FIT;
00094     }
00095 }

uint BTreeCompactNodeAccessor::getEntryByteCount ( uint cbTuple ) [virtual]

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

Parameters:

cbTuple

number of bytes without overhead

Returns:: number of bytes with overhead

Implements BTreeNodeAccessor.

Definition at line 97 of file BTreeCompactNodeAccessor.cpp.

00098 {
00099     return cb;
00100 }

void BTreeCompactNodeAccessor::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 from BTreeNodeAccessor.

Definition at line 102 of file BTreeCompactNodeAccessor.cpp.

00103 {
00104     // Since we never return CAN_FIT_WITH_COMPACTION, no one should ever ask us
00105     // to do this.
00106     permAssert(false);
00107 }

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

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, inherited]`

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 PConstBuffer BTreeNodeAccessor::getEntryForRead	(	BTreeNode const &	node,
		uint	iEntry
	)			`[pure virtual, inherited]`

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 BTreeNodeAccessor::dumpNode(), BTreeWriter::splitCurrentNode(), and BTreeWriter::updateCurrent().

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

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, BTreeNodeAccessor::getEntryForRead(), BTreeNode::height, isMAXU(), BTreeNode::nEntries, NULL_PAGE_ID, TuplePrinter::print(), BTreeNode::rightSibling, TupleAccessor::setCurrentTupleBuf(), BTreeNodeAccessor::tupleAccessor, BTreeNodeAccessor::tupleData, BTreeNodeAccessor::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 void BTreeNodeAccessor::accessTuple	(	BTreeNode const &	node,
		uint	iEntry
	)			`[pure virtual, inherited]`

Binds tupleAccessor to a stored tuple.

Parameters:

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

Referenced by BTreeReader::accessLeafTuple(), BTreeNodeAccessor::compactNode(), BTreeAccessBase::getChild(), BTreeWriter::grow(), BTreeWriter::lockParentPage(), BTreeWriter::splitCurrentNode(), BTreeNodeAccessor::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, inherited]`

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, inherited]`

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, inherited]`

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 void BTreeNodeAccessor::unmarshalKey ( TupleData & keyData ) [pure virtual, inherited]

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::splitNode	(	BTreeNode &	node,
		BTreeNode &	newNode,
		uint	cbNewTuple,
		bool	monotonic
	)			`[virtual, inherited]`

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 BTreeNodeAccessor::accessTuple(), BTreeNodeAccessor::allocateEntry(), BTreeNode::cbTotalFree, TupleAccessor::getCurrentByteCount(), TupleAccessor::getCurrentTupleBuf(), BTreeNodeAccessor::getEntryByteCount(), BTreeNode::height, max(), BTreeNode::nEntries, and BTreeNodeAccessor::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 }