BTree< T, M, BlockSize >::BNode Struct Reference

B-tree node. More...

Public Member Functions
void	initialize (bool isLeaf=true, int size=0)
	Initializes the node. More...
bool	isFull () const
	Checks if the node has reached its maximum capacity. More...
template<typename U >
std::unique_ptr< T >	seek (const U &key, BTree &tree) const
	Seeks a value that's equivalent to the one provided. More...

Public Attributes
long	offset
	Disk address. More...
bool	isLeaf
	True if the node is a leaf, false if it's an internal node. More...
std::size_t	size
	Quantity of values currently stored in the node. More...
T	values [2 *M+1]
	Node values. More...
long	children [2 *M+2]
	Node pointers. More...

Detailed Description

template<typename T, std::size_t M, unsigned int BlockSize = BLOCK_SIZE>
struct BTree< T, M, BlockSize >::BNode

B-tree node.

Member Function Documentation

template<typename T , std::size_t M, unsigned int BlockSize>

void BTree< T, M, BlockSize >::BNode::initialize	(	bool	isLeaf = true,
		int	size = 0
	)

Initializes the node.

The value of BNode::offset is initialized as -1 so that we can know whether the node has already been written to the file or not.

This method must always be called upon declaring a BNode if it won't be read through BTree::readFromDisk.

BNode's initialization was implemented as a method rather than a constructor because BNode must be a POD in order to be serialized in the binary file, and POD's can't have constructors.

Parameters

isLeaf	True if the node will be a leaf, false if it will be an internal node
size	Initial node size

template<typename T , std::size_t M, unsigned int BlockSize>

bool BTree< T, M, BlockSize >::BNode::isFull

(

)

const

Checks if the node has reached its maximum capacity.

Returns

True if BNode::size >= 2M, false otherwise

template<typename T , std::size_t M, unsigned int BlockSize>

template<typename U >

std::unique_ptr< T > BTree< T, M, BlockSize >::BNode::seek	(	const U &	key,
		BTree &	tree
	)		const

Seeks a value that's equivalent to the one provided.

Template Parameters

U	See BTree::seek

Parameters

key	Value to seek
tree	BTree to access the file and statistics

Returns

Pointer with the value if found, null pointer otherwise

Member Data Documentation

template<typename T, std::size_t M, unsigned int BlockSize = BLOCK_SIZE>

long BTree< T, M, BlockSize >::BNode::children[2 *M+2]

Node pointers.

Most of the time, the node will only use the first 2M+1 positions of this array. The additional space for 1 value is used temporarily to deal with overflows during BTree::insert.

template<typename T, std::size_t M, unsigned int BlockSize = BLOCK_SIZE>

bool BTree< T, M, BlockSize >::BNode::isLeaf

True if the node is a leaf, false if it's an internal node.

template<typename T, std::size_t M, unsigned int BlockSize = BLOCK_SIZE>

long BTree< T, M, BlockSize >::BNode::offset

Disk address.

Ideally, the node before written should have its offset set to -1. Only after its first writing should BNode::offset be set to its disk location.

template<typename T, std::size_t M, unsigned int BlockSize = BLOCK_SIZE>

std::size_t BTree< T, M, BlockSize >::BNode::size

Quantity of values currently stored in the node.

template<typename T, std::size_t M, unsigned int BlockSize = BLOCK_SIZE>

T BTree< T, M, BlockSize >::BNode::values[2 *M+1]

Node values.

Most of the time, the node will only be using the first 2M positions of this array. The additional space for 1 value is used temporarily to deal with overflows during BTree::insert.

---

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

• include/BTree.hpp
• include/BTree.inl