Click here to Skip to main content
Click here to Skip to main content
Articles » Database » Database » General » Downloads
 
Add your own
alternative version

Implementation of a B-Tree Database Class

, 29 Jun 2006
An article and source code regarding the implmentation of B-Trees in C++.
/***************************************************************************
 TreeNode.h  -  Header file containing the definition of the TreeNode class.
                The database tree structure is really a collection of nodes
                that contain records.

 begin     : April 2004
 copyright : (C) 2004 by Phil Cairns
 email     : philcairns@hotmail.com

 This code may be used in compiled form in any way you desire (including
 commercial use). The code may be redistributed unmodified by any means
 providing it is not sold for profit without the authors written consent,
 and providing that this notice and the authors name and all copyright
 notices remains intact.

 This software is provided "as is" without express or implied warranty. Use
 it at your own risk!
 ***************************************************************************/

#if !defined(__treenode_h)
#define __treenode_h

#include "DbObj.h"

namespace Database
{
	// Function type used for object comparison callbacks.
	typedef int (*compareFn)(const DbObjPtr&, const DbObjPtr&);

	// Where (from a given child) does the key lay?
	enum EChildPos
	{
		ECP_INTHIS,
		ECP_INLEFT,
		ECP_INRIGHT,
		ECP_NONE
	};
	typedef std::pair<size_t, EChildPos> OBJECTPOS;

	// A BTreeDB is made up of a collection of nodes. A node
	// contains information about which of its parent's children
	// is, how many objects it has, whether or not it's a leaf,
	// where it lives on the disk, whether or not it's actually
	// been loaded from the disk, a collection of records,
	// and (if it's not a leaf) a collection of children.
	// It also contains a ptr to its parent.
	class TreeNode : public Database::RefCount
	{
	public:
		TreeNode();
		~TreeNode();
		Database::Ptr<TreeNode> loadChild(size_t childNo, FILE* f, size_t recSize);
		void unload();
		void unloadChildren();
		bool read(FILE* f, size_t recSize);
		bool write(FILE* f);
		bool delFromLeaf(size_t objNo);
		OBJECTPOS findPos(const DbObjPtr& key, compareFn cfn);

		// This count is the number of objects in the node, rather than the
		// number of children in the node. It should only be used when splitting
		// or joining nodes.
		void setCount(size_t newSize)
		{
			objCount = newSize;
			objects.resize(newSize);
			children.resize(newSize + 1);
		}

	public:
		size_t childNo;
		size_t objCount;
		bool isLeaf;
		bool loaded;
		long fpos;
		DBOBJVECTOR objects;
		std::vector<Database::Ptr<TreeNode> > children;
		Database::Ptr<TreeNode> parent;
	};

	typedef Database::Ptr<TreeNode> TreeNodePtr;
	typedef std::vector<TreeNodePtr> TREENODEVECTOR;
	typedef std::pair<TreeNodePtr, size_t> NodeKeyLocn;
}

#endif

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

_oti
Other
Australia Australia
No Biography provided

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 29 Jun 2006
Article Copyright 2004 by _oti
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid