Fennel: BTreeHeapNodeAccessor Class Reference

typedef uint16_t BTreeHeapNodeAccessor::EntryOffset [private]

Definition at line 41 of file BTreeHeapNodeAccessor.h.

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     };

BTreeHeapNodeAccessor::BTreeHeapNodeAccessor ( ) [explicit]

Definition at line 29 of file BTreeHeapNodeAccessor.cpp.

00030 {
00031 }

BTreeHeapNodeAccessor::EntryOffset const * BTreeHeapNodeAccessor::getEntryOffsetPointer	(	BTreeNode const &	node,
		uint	iEntry
	)			`[inline, private]`

Definition at line 71 of file BTreeHeapNodeAccessor.h.

References BTreeNode::getDataForRead().

Referenced by allocateEntry(), deallocateEntry(), and getEntryOffset().

00073 {
00074     return reinterpret_cast<EntryOffset const *>(node.getDataForRead())
00075         + iEntry;
00076 }

BTreeHeapNodeAccessor::EntryOffset * BTreeHeapNodeAccessor::getEntryOffsetPointer	(	BTreeNode &	node,
		uint	iEntry
	)			`[inline, private]`

Definition at line 79 of file BTreeHeapNodeAccessor.h.

References BTreeNode::getDataForWrite().

00081 {
00082     return reinterpret_cast<EntryOffset *>(node.getDataForWrite())
00083         + iEntry;
00084 }

uint BTreeHeapNodeAccessor::getEntryOffset	(	BTreeNode const &	node,
		uint	iEntry
	)			`[inline, private]`

Definition at line 86 of file BTreeHeapNodeAccessor.h.

References getEntryOffsetPointer(), and BTreeNode::nEntries.

Referenced by getEntryForReadInline().

00088 {
00089     assert(iEntry < node.nEntries);
00090     return *getEntryOffsetPointer(node,iEntry);
00091 }

uint BTreeHeapNodeAccessor::getEntrySizeWithOverhead ( uint cbEntry ) [inline, private]

Definition at line 93 of file BTreeHeapNodeAccessor.h.

Referenced by allocateEntry(), calculateCapacity(), deallocateEntry(), and getEntryByteCount().

00094 {
00095     return cbEntry + sizeof(EntryOffset);
00096 }

uint BTreeHeapNodeAccessor::getEntryOffsetArrayByteSize ( uint nEntries ) [inline, private]

Definition at line 98 of file BTreeHeapNodeAccessor.h.

Referenced by allocateEntry(), and deallocateEntry().

00099 {
00100     assert(sizeof(EntryOffset) == 2);
00101     return nEntries << 1;
00102 }

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

Definition at line 104 of file BTreeHeapNodeAccessor.h.

References getEntryOffset().

Referenced by deallocateEntry().

00106 {
00107     uint offset = getEntryOffset(node,iEntry);
00108     return reinterpret_cast<PConstBuffer>(&node) + offset;
00109 }

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

Definition at line 33 of file BTreeHeapNodeAccessor.cpp.

References BTreeNode::cbCompactFree, BTreeNode::cbTotalFree, and BTreeNodeAccessor::clearNode().

00034 {
00035     BTreeNodeAccessor::clearNode(node,cbPage);
00036     node.cbCompactFree = node.cbTotalFree;
00037 }

PBuffer BTreeHeapNodeAccessor::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 39 of file BTreeHeapNodeAccessor.cpp.

References BTreeNode::cbCompactFree, BTreeNode::cbTotalFree, getEntryOffsetArrayByteSize(), getEntryOffsetPointer(), getEntrySizeWithOverhead(), and BTreeNode::nEntries.

00041 {
00042     uint cbEntryWithOverhead = getEntrySizeWithOverhead(cbEntry);
00043     assert(iEntry < node.nEntries + 1);
00044     assert(node.cbCompactFree >= cbEntryWithOverhead);
00045 
00046     EntryOffset *pFirstEntryOffset = getEntryOffsetPointer(node,0);
00047 
00048     // calculate the end of the compact free space, and subtract off
00049     // the entry size to determine where the entry should be stored
00050     PBuffer pAllocation =
00051         reinterpret_cast<PBuffer>(pFirstEntryOffset + node.nEntries)
00052         + node.cbCompactFree - cbEntry;
00053 
00054     // make room in the offset array
00055     EntryOffset *pEntryOffset = pFirstEntryOffset + iEntry;
00056     memmove(
00057         pEntryOffset + 1,
00058         pEntryOffset,
00059         getEntryOffsetArrayByteSize(node.nEntries - iEntry));
00060     // and write the new offset into the slot just vacated
00061     *pEntryOffset = pAllocation - reinterpret_cast<PBuffer>(&node);
00062 
00063     // update node control info
00064     node.nEntries++;
00065     node.cbTotalFree -= cbEntryWithOverhead;
00066     node.cbCompactFree -= cbEntryWithOverhead;
00067 
00068     return pAllocation;
00069 }

void BTreeHeapNodeAccessor::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 71 of file BTreeHeapNodeAccessor.cpp.

References BTreeNode::cbTotalFree, TupleAccessor::getCurrentByteCount(), getEntryForReadInline(), getEntryOffsetArrayByteSize(), getEntryOffsetPointer(), getEntrySizeWithOverhead(), BTreeNode::nEntries, TupleAccessor::setCurrentTupleBuf(), and BTreeNodeAccessor::tupleAccessor.

00073 {
00074     tupleAccessor.setCurrentTupleBuf(getEntryForReadInline(node,iEntry));
00075     uint cbEntry = tupleAccessor.getCurrentByteCount();
00076 
00077     // see comments in BTreeCompactNodeAccessor::deallocateEntry
00078     if (iEntry != node.nEntries - 1) {
00079         // delete the entry from the offset array
00080         EntryOffset *pEntryOffset = getEntryOffsetPointer(node,iEntry);
00081         memmove(
00082             pEntryOffset,
00083             pEntryOffset + 1,
00084             getEntryOffsetArrayByteSize(node.nEntries - (iEntry + 1)));
00085     }
00086 
00087     // update node control info
00088     node.nEntries--;
00089     node.cbTotalFree += getEntrySizeWithOverhead(cbEntry);
00090 }

bool BTreeHeapNodeAccessor::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 92 of file BTreeHeapNodeAccessor.cpp.

References TupleAccessor::isFixedWidth(), and BTreeNodeAccessor::tupleAccessor.

00093 {
00094     return false;
00095 
00096     // REVIEW:  we might choose to store fixed-width entries in a heap just to
00097     // save on memmmove cost
00098 #if 0
00099     return tupleAccessor.isFixedWidth();
00100 #endif
00101 }

BTreeNodeAccessor::Capacity BTreeHeapNodeAccessor::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 104 of file BTreeHeapNodeAccessor.cpp.

References BTreeNodeAccessor::CAN_FIT, BTreeNodeAccessor::CAN_FIT_WITH_COMPACTION, BTreeNodeAccessor::CAN_NOT_FIT, BTreeNode::cbCompactFree, BTreeNode::cbTotalFree, and getEntrySizeWithOverhead().

00105 {
00106     uint cbEntryWithOverhead = getEntrySizeWithOverhead(cbEntry);
00107     if (cbEntryWithOverhead <= node.cbCompactFree) {
00108         return CAN_FIT;
00109     }
00110     if (cbEntryWithOverhead <= node.cbTotalFree) {
00111         return CAN_FIT_WITH_COMPACTION;
00112     }
00113     return CAN_NOT_FIT;
00114 }

uint BTreeHeapNodeAccessor::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 116 of file BTreeHeapNodeAccessor.cpp.

References getEntrySizeWithOverhead().

00117 {
00118     return getEntrySizeWithOverhead(cb);
00119 }

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 }

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::onInit ( ) [virtual, inherited]

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(), BTreeNodeAccessor::tupleAccessor, BTreeNodeAccessor::tupleData, and BTreeNodeAccessor::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
	)			`[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::compactNode	(	BTreeNode &	node,
		BTreeNode &	scratchNode
	)			`[virtual, inherited]`

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

TupleDescriptor BTreeNodeAccessor::tupleDescriptor [inherited]

Descriptor for tuples stored on nodes accessed by this.

Definition at line 60 of file BTreeNodeAccessor.h.

Referenced by BTreeNodeAccessor::dumpNode(), and BTreeNodeAccessor::onInit().

TupleAccessor BTreeNodeAccessor::tupleAccessor [inherited]

Accessor for tuples stored on nodes accessed by this.

This is used as a scratch variable in a variety of contexts, so reference with caution.

Definition at line 66 of file BTreeNodeAccessor.h.

Referenced by BTreeWriter::checkMonotonicity(), BTreeNodeAccessor::compactNode(), deallocateEntry(), BTreeWriter::deleteCurrent(), BTreeNodeAccessor::dumpNode(), BTreeWriter::grow(), hasFixedWidthEntries(), BTreeBuildLevel::indexLastChild(), VariableBuildLevel::indexLastKey(), BTreeWriter::insertTupleFromBuffer(), BTreeNodeAccessor::onInit(), BTreeCompactNodeAccessor::onInit(), BTreeBuildLevel::processInput(), BTreeWriter::splitCurrentNode(), BTreeNodeAccessor::splitNode(), and BTreeWriter::updateCurrent().

TupleData BTreeNodeAccessor::tupleData [inherited]

TupleData for tuples stored on nodes accessed by this.

This is used as a scratch variable in a variety of contexts, so reference with caution.

Definition at line 72 of file BTreeNodeAccessor.h.

Referenced by BTreeNodeAccessor::dumpNode(), BTreeWriter::grow(), BTreeBuildLevel::indexLastChild(), VariableBuildLevel::indexLastKey(), BTreeWriter::lockParentPage(), BTreeNodeAccessor::onInit(), and BTreeWriter::splitCurrentNode().

BTreeHeapNodeAccessor Class Reference

Public Types

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation


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
	BTreeHeapNodeAccessor ()
PConstBuffer	getEntryForReadInline (BTreeNode const &node, uint iEntry)
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)
	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.
uint	getKeyCount (BTreeNode const &node) const
	Gets the number of keys stored on a node.
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 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	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.
Private Types
typedef uint16_t	EntryOffset
Private Member Functions
EntryOffset const *	getEntryOffsetPointer (BTreeNode const &node, uint iEntry)
EntryOffset *	getEntryOffsetPointer (BTreeNode &node, uint iEntry)
uint	getEntryOffset (BTreeNode const &node, uint iEntry)
uint	getEntrySizeWithOverhead (uint cbEntry)
uint	getEntryOffsetArrayByteSize (uint nEntries)