B-Tree Insertion Problem

[Seag]

Hello, I am building a B-Tree with data from a txt file, extracting a numerical record (as an int) and storing that in my B-Tree. I followed the debugger and added a cout statement to see that it is actually inserting, and it seems to work fine, but upon closer inspection, the splitChild and splitParent are not occurring nearly as much as expected (with branching factor of 3), and once I return to my initial insert statement and use the Locals window, I cannot navigate past Root and it's three children (all the 'next's are NULL.


Here is my .h file:

const int PAGE_SIZE = 3;			//Branching Factor

class BTreeNode;
struct keys
{
	int value = 0;
	BTreeNode* next;
};

class BTreeNode
{
public:
	BTreeNode()
	{
		root = true;
		leaf = false;
	}
	bool root;
	bool leaf;
	int n;	// how many keys
	keys page[PAGE_SIZE];

};


class BTree
{
	BTreeNode* Root;
	bool audit;
public:
	BTree();
	BTreeNode* indexData(BTreeNode*);
	int find(BTreeNode*, int);
	int insert(BTreeNode*&, int);
	int splitRoot(BTreeNode*&);
	int splitChild(BTreeNode*&, int);
	int remove(BTreeNode*, int);
	void printTreeBOM(BTreeNode*);
	void OnOffAuditTrail();		//prompts user if they want a message for each time a node is split; 
	void setAudit(bool);
	bool getAudit();

Here is the function that reads the file and sends the key to the insert function:

BTreeNode* BTree::indexData(BTreeNode* root)
{
	int key;	// to store the extracted unique identifier from the file
	size_t eofMarker;
	string line;
	fstream inOutFile;
	long int offset = 3;
	long int begin = 0;
	long int end = 0;
	int i = 0;


	inOutFile.open("censusdata.txt", fstream::binary | fstream::ate | fstream::in | fstream::out);
	if (!inOutFile) {
		cout << "File open error" << endl;
		return root;
	}

	inOutFile.seekg(0, ios::end);		// position 0 bytes from the end of the file
	eofMarker = inOutFile.tellg();		// sets eofMarker to the end of the file returned from tellg()
	inOutFile << "0 -> ";				// so it can print 0 -> at the end of the document

	inOutFile.seekg(0, ios::beg);	// position 0 bytes from the beginning
	begin = inOutFile.tellg();

	while (begin + offset < eofMarker)
	{
		inOutFile.seekg((begin + offset), ios::beg);
		inOutFile >> key;
		inOutFile.ignore(300, '\n');
		offset = inOutFile.tellg();
		insert(root, key);
		
	}

	inOutFile.seekp(0, fstream::end);
	inOutFile << "   EOF" << endl;
	inOutFile.close();

	return root;
}

Here is the insert function:

int BTree::insert(BTreeNode*& parent, int identifier)
{
	
	if (getAudit())
		cout << endl << "AUDIT:Inserting Value" << endl;

	static int r = 0;   // see how many objects are 'inserted'
	cout << endl << "AUDIT:Inserting Value..." << r << endl;
	r++;


	int result = 0;
	if (parent == NULL)		// if the node passed is new, make a new instance
	{
		parent = new BTreeNode;
		parent->root = true;
		parent->leaf = true;
		parent->page[0].value = identifier;
		for (int i = 0; i < PAGE_SIZE - 1; i++)
			parent->page[i].next = NULL;
		parent->n = 1;
		return 1;		// 1 means OK!
	}
	else if (parent->n == PAGE_SIZE && parent->root == true)
	{
		result = splitRoot(parent);

		if (result == 1)
			return insert(parent, identifier);
	}

	else if (parent->leaf == true)
	{
		cout << "Parent's Leaf is true" << endl;

		int j = parent->n - 1;
		while (j >= 0 && identifier < parent->page[j].value)
		{
			parent->page[j + 1].value = parent->page[j].value;
			j--;
		}
		j++;
		parent->page[j].value = identifier;
		parent->n++;
		return 1;		// 1 means OK!
	}
	else
	{
		int k = parent->n - 1;
		while (k > 0 && identifier < parent->page[k].value)
			k--;

		if (parent->page[k].next != NULL && parent->page[k].next->n == PAGE_SIZE)
		{
			result = splitChild(parent, k);
			if (result == 1)		// returned result must be a 1!
				return insert(parent, identifier);
			else
			{
				result = insert(parent->page[k].next, identifier);
				if (result == 1)
					parent->page[k].value = parent->page[k].next->page[0].value;
				return result;
			}
		}
	}
}

And lastly, my splitRoot and splitParent functions:

int BTree::splitRoot(BTreeNode*& parent)
{
	if (getAudit())
		cout << endl << "AUDIT:Splitting Root" << endl;

	cout << endl << "AUDIT:Splitting Root" << endl;

	BTreeNode* temp = parent;
	parent = new BTreeNode;
	BTreeNode* temp2 = new BTreeNode;

	for (int i = 0; i < (PAGE_SIZE / 2) - 1; i++)
	{
		temp2->page[i].value = temp->page[(PAGE_SIZE + 1) / 2 + i].value;
		temp2->page[i].next = temp->page[(PAGE_SIZE + 1) / 2 + i].next;
	}
	temp->root = false;
	temp2->root = false;
	if (temp2->page[0].next == NULL)
	{
		temp->leaf = true;
		temp2->leaf = true;
	}
	else
	{
		temp->leaf = false;
		temp2->leaf = false;
	}
	temp->n = (PAGE_SIZE + 1) / 2;
	temp2->n = PAGE_SIZE / 2;
	parent->root = true;
	parent->leaf = false;
	parent->n = 2;
	parent->page[0].value = temp->page[0].value;
	parent->page[0].next = temp;
	parent->page[1].value = temp2->page[0].value;
	parent->page[1].next = temp2;
	return 1;		// 1 means OK!
}

int BTree::splitChild(BTreeNode*& parent, int key)
{
	if (getAudit())
		cout << endl << "AUDIT:Splitting Child" << endl;

	cout << endl << "AUDIT:Splitting Child" << endl;

	BTreeNode* newChild = new BTreeNode;

	for (int i = 0; i < (PAGE_SIZE / 2) - 1; i++)
	{
		newChild->page[i].value = parent->page[key].next->page[(PAGE_SIZE + 1) / 2 + i].value;
		newChild->page[i].next = parent->page[key].next->page[(PAGE_SIZE + 1) / 2 + i].next;
	}

	newChild->root = false;
	if (newChild->page[0].next == NULL)
		newChild->leaf = true;
	else
		newChild->leaf = false;

	
	newChild->n = PAGE_SIZE / 2;
	parent->page[key].next->n = (PAGE_SIZE + 1) / 2;
	int j = parent->n - 1;
	while (j > key)
	{
		parent->page[j + 1].value = parent->page[j].value;
		parent->page[j + 1].next = parent->page[j].next;
		j--;
	}
	j++;
	parent->page[j].value = newChild->page[0].value;
	parent->page[j].next = newChild;
	parent->n++;
	cout << "INCREMENTED N" << endl;
	return 1;		// 1 means OK!
}

Any help would be appreciated. Thank you for your precious time!

[Seag]

No one?

[coder777]

Well, this is too complex to skim through. You need to provide the test code as well.

What I see is that in keys you do not set next = NULL and in BTreeNode n is uninitialized. (I don't know if you at least set Root = NULL in BTree)

If you would set next = NULL you could remove

		for (int i = 0; i < PAGE_SIZE - 1; i++)
			parent->page[i].next = NULL;

Note that the last next remains uninitialized due to PAGE_SIZE - 1