btreedb.cpp

这是一个利用B+ Trees数据结构存储数据的源码,全部代码用C语言写的.

							}
							--leftSib->objCount;
						}

						// Bringing a new key in from the right sibling
						else
						{
							// Put the key from the parent into the child,
							// put the key from the sibling into the parent,
							// and move the appropriate child from the
							// sibling to the target child node.
							childNode->objects[childNode->objCount - 1] = node->objects[op.first];
							node->objects[op.first] = rightSib->objects[0];
							if (!rightSib->isLeaf)
							{
								childNode->children[childNode->objCount] = rightSib->children[0];
							}

							// Now clean up the right node, shuffling keys
							// and objects to the left and resizing.
							for (size_t ctr = 0; ctr < rightSib->objCount - 1; ctr++)
							{
								rightSib->objects[ctr] = rightSib->objects[ctr + 1];
								if (!rightSib->isLeaf)
								{
									rightSib->children[ctr] = rightSib->children[ctr + 1];
								}
							}
							if (!rightSib->isLeaf)
							{
								rightSib->children[ctr] = rightSib->children[ctr + 1];
							}
							rightSib->setCount(rightSib->objCount - 1);
						}
						ret = _delete(childNode, key);
					}

					// Case 3b: All siblings have _minDegree - 1 keys
					else
					{
						TreeNodePtr mergedChild = _merge(node, op.first);
						ret = _delete(mergedChild, key);
					}
				}
			}
		}
		return ret;
	}

	// Finds the location of the predecessor of this key, given
	// the root of the subtree to search. The predecessor is going
	// to be the right-most object in the right-most leaf node.
	NodeKeyLocn BTreeDB::_findPred(TreeNodePtr& node)
	{
		NodeKeyLocn ret(TreeNodePtr(), (size_t)-1);
		TreeNodePtr child = node;
		while (!child->isLeaf)
		{
			child = child->loadChild(child->objCount, _dataFile, _recSize);
		}
		ret.first = child;
		ret.second = child->objCount - 1;
		return ret;
	}

	// Finds the location of the successor of this key, given
	// the root of the subtree to search. The successor is the
	// left-most object in the left-most leaf node.
	NodeKeyLocn BTreeDB::_findSucc(TreeNodePtr& node)
	{
		NodeKeyLocn ret(TreeNodePtr(), (size_t)-1);
		TreeNodePtr child = node;
		while (!child->isLeaf)
		{
			child = child->loadChild(0, _dataFile, _recSize);
		}
		ret.first = child;
		ret.second = 0;
		return ret;
	}

	// Opening the database means that we check the file
	// and see if it exists. If it doesn't exist, start a database
	// from scratch. If it does exist, load the root node into
	// memory.
	bool BTreeDB::open()
	{
		// We're creating if the file doesn't exist.
		SFileHeader sfh;
		bool creating = (0 != _access(_fileName.c_str(), 06));
		_dataFile = fopen(_fileName.c_str(), creating ? "w+b" : "r+b");
		if (0 == _dataFile)
		{
			return false;
		}

		// Create a new node
		bool ret = false;
		_root = new TreeNode;
		if (creating)
		{
			// We *must* have the rec size, key size and
			// and min degree if we are creating. If not
			// supplied, we have to bug out.
			if (_recSize == -1 || _keySize == -1 || _minDegree == -1)
			{
				return false;
			}
			sfh.keySize = _keySize;
			sfh.recSize = _recSize;
			sfh.minDegree = _minDegree;
			sfh.rootPos = sizeof(sfh);
			_nodeSize = sizeof(size_t);						// object count
			_nodeSize += (_minDegree * 2 - 1) * _recSize;	// records
			_nodeSize += _minDegree * 2 * sizeof(long);		// child locations
			_nodeSize += sizeof(byte);						// is leaf?

			// when creating, write the node to the disk.
			// remember that the first four bytes contain
			// the address of the root node.
			_root->isLeaf = true;
			_root->fpos = sfh.rootPos;
			_root->loaded = true;
			if (1 != fwrite(&sfh, sizeof(sfh), 1, _dataFile))
			{
				return false;
			}
			_root->write(_dataFile);
			ret = true;
		}
		else
		{
			// when not creating, read the root node from the disk.
			memset(&sfh, 0, sizeof(sfh));
			if (1 != fread(&sfh, sizeof(sfh), 1, _dataFile))
			{
				return false;
			}
			else
			{
				_keySize = sfh.keySize;
				_recSize = sfh.recSize;
				_minDegree = sfh.minDegree;
				_root->fpos = sfh.rootPos;
				_nodeSize = sizeof(size_t);						// object count
				_nodeSize += (_minDegree * 2 - 1) * _recSize;	// records
				_nodeSize += _minDegree * 2 * sizeof(long);		// child locations
				_nodeSize += sizeof(byte);						// is leaf?
			}
			_root->read(_dataFile, _recSize);
			ret = true;
		}
		return ret;
	}

	// This is the external delete function.
	bool BTreeDB::del(const DbObjPtr& key)
	{
		// Determine if the root node is empty.
		bool ret = (_root->objCount != 0);

		// If our root is not empty, call the internal
		// delete method on it.
		ret = ret && _delete(_root, key);

		// If we successfully deleted the key, and there
		// is nothing left in the root node and the root
		// node is not a leaf, we need to shrink the tree
		// by making the root's child (there should only
		// be one) the new root. Write the location of
		// the new root to the start of the file so we
		// know where to look.
		if (ret && _root->objCount == 0 && !_root->isLeaf)
		{
			_root = _root->children[0];
			fseek(_dataFile, 0, SEEK_SET);
			fwrite(&_root->fpos, sizeof(_root->fpos), 1, _dataFile);
			ret = flush();
		}
		return ret;
	}

	// External put method. This will overwrite a key
	// (allowing no duplicates) or insert a new item.
	bool BTreeDB::put(const DbObjPtr& rec)
	{
		if (rec->getSize() != getRecSize())
		{
			return false;
		}
		NodeKeyLocn locn = _search(_root, rec);

		// If we can't find the key, then insert a new
		// record.
		if ((TreeNode*)locn.first == 0 || locn.second == (size_t)-1)
		{
			_insert(rec);
		}

		// If we found the key, update the node with
		// the record.
		else
		{
			locn.first->objects[locn.second] = rec;
			locn.first->write(_dataFile);
		}
		return true;
	}

	// This method retrieves a record from the database
	// given its location.
	bool BTreeDB::get(const NodeKeyLocn& locn, DbObjPtr& rec)
	{
		if ((TreeNode*)locn.first == 0 || locn.second == (size_t)-1)
		{
			return false;
		}
		rec = locn.first->objects[locn.second];
		return true;
	}

	// This method retrieves a record from the database
	// given its key.
	bool BTreeDB::get(const DbObjPtr& key, DbObjPtr& rec)
	{
		NodeKeyLocn locn = _search(_root, key);
		return get(locn, rec);
	}

	// Visit every record in the tree, calling the callback
	// function with the current record, the reference object,
	// and the recursion depth as parameters.
	void BTreeDB::traverse(const DbObjPtr& ref, BTreeDB::traverseCallback cbfn)
	{
		_traverse(_root, ref, cbfn);
	}

	// External method that searches for elements that match the
	// given key. The cfn parameter is a caller-provided callback
	// function used to do the comparison.
	NodeKeyLocn BTreeDB::search(const DbObjPtr& key, compareFn cfn)
	{
		return _search(_root, key, cfn);
	}

	// Structure and methods used for searching the database.
	struct SearchData
	{
		bool started;
		size_t counter;
		DbObjPtr pKey;
		DBOBJVECTOR* pVect;
	};

	// This is the callback function used for findAll traversals.
	// It builds a list of records whose keys match the object given
	// as the search pattern. It starts inserting values once we've found
	// a match, and stops once we've found a record that doesn't match.
	bool BTreeDB::_searchCallback(const DbObjPtr& obj, const DbObjPtr& ref, int /*depth*/)
	{
		SearchData* sd = (SearchData*)ref->getData();
		if (0 == memcmp(obj->getData(), sd->pKey->getData(), min(obj->getSize(), sd->pKey->getSize())))
		{
			if (sd->pVect->size() == sd->pVect->capacity() - 1)
			{
				sd->pVect->reserve(sd->pVect->capacity() * 2);
			}
			sd->pVect->push_back(obj);
			sd->started = true;
			++sd->counter;
		}
		else if (sd->started)
		{
			return false;
		}
		return true;
	}

	// This method finds all records in the database that match
	// the given key. Note that this doesn't necessarily compare
	// the entire key. This is for finding all keys that match
	// "ABC%", f'rinstance.
	void BTreeDB::findAll(const DbObjPtr& key, DBOBJVECTOR& results)
	{
		results.clear();
		SearchData sd = { false, 0, key, &results };
		DbObjPtr pRef = new DbObj(&sd, sizeof(sd));
		_traverse(_root, pRef, _searchCallback);
		memcpy(&sd, pRef->getData(), sizeof(sd));
	}

	// This method finds the record following the one at the
	// location given as locn, and copies the record into rec.
	// The direction can be either forward or backward.
	bool BTreeDB::seq(NodeKeyLocn& locn, DbObjPtr& rec, ESeqDirection sdir)
	{
		switch (sdir)
		{
		case ESD_FORWARD:
			return _seqNext(locn, rec);

		case ESD_BACKWARD:
			return _seqPrev(locn, rec);
		}

		return false;
	}

	// Find the next item in the database given a location. Return
	// the subsequent item in rec.
	bool BTreeDB::_seqNext(NodeKeyLocn& locn, DbObjPtr& rec)
	{
		// Set up a couple of convenience values
		bool ret = false;
		TreeNodePtr node = locn.first;
		size_t lastPos = locn.second;
		bool goUp = false;	// indicates whether or not we've exhausted a node.

		// If we are starting at the beginning, initialise
		// the locn reference and return with the value set.
		// This means we have to plunge into the depths of the
		// tree to find the first leaf node.
		if ((TreeNode*)node == 0)
		{
			node = _root;
			while ((TreeNode*)node != 0 && !node->isLeaf)
			{
				node = node->loadChild(0, _dataFile, _recSize);
			}
			if ((TreeNode*)node == 0)
			{
				return false;
			}
			rec = node->objects[0];
			locn.first = node;
			locn.second = 0;
			return true;
		}

		// Advance the locn object to the next item

		// If we have a leaf node, we don't need to worry about
		// traversing into children ... only need to worry about
		// going back up the tree.
		if (node->isLeaf)
		{
			// didn't visit the last node last time.
			if (lastPos < node->objCount - 1)
			{
				rec = node->objects[lastPos + 1];
				locn.second = lastPos + 1;
				return true;
			}
			goUp = (lastPos == node->objCount - 1);
		}

		// Not a leaf, therefore need to worry about traversing
		// into child nodes.
		else
		{
			node = node->loadChild(lastPos + 1, _dataFile, _recSize);
			while ((TreeNode*)node != 0 && !node->isLeaf)
			{
				node = node->loadChild(0, _dataFile, _recSize);
			}
			if ((TreeNode*)node == 0)
			{
				return false;
			}
			rec = node->objects[0];
			locn.first = node;
			locn.second = 0;
			return true;
		}

		// Finished off a leaf, therefore need to go up to
		// a parent.
		if (goUp)
		{
			size_t childNo = node->childNo;
			node = node->parent;
			while ((TreeNode*)node != 0 && childNo >= node->objCount)
			{
				childNo = node->childNo;
				node = node->parent;
			}
			if ((TreeNode*)node != 0)
			{
				locn.first = node;
				locn.second = childNo;
				ret = true;
				rec = node->objects[childNo];
			}
		}
		return ret;
	}

	// Find the previous item in the database given a location. Return
	// the item in rec.
	bool BTreeDB::_seqPrev(NodeKeyLocn& locn, DbObjPtr& rec)
	{
		// Set up a couple of convenience values
		bool ret = false;
		TreeNodePtr node = locn.first;
		size_t lastPos = locn.second;
		bool goUp = false;	// indicates whether or not we've exhausted a node.

		// If we are starting at the end, initialise
		// the locn reference and return with the value set.
		// This means we have to plunge into the depths of the
		// tree to find the first leaf node.
		if ((TreeNode*)node == 0)
		{
			node = _root;
			while ((TreeNode*)node != 0 && !node->isLeaf)
			{
				node = node->loadChild(node->objCount, _dataFile, _recSize);
			}
			if ((TreeNode*)node == 0)
			{
				return false;
			}
			locn.first = node;
			locn.second = node->objCount - 1;
			rec = node->objects[locn.second];
			return true;
		}

		// Advance the locn object to the next item

		// If we have a leaf node, we don't need to worry about
		// traversing into children ... only need to worry about
		// going back up the tree.
		if (node->isLeaf)
		{
			// didn't visit the last node last time.
			if (lastPos > 0)
			{
				locn.second = lastPos - 1;
				rec = node->objects[locn.second];
				return true;
			}
			goUp = (lastPos == 0);
		}

		// Not a leaf, therefore need to worry about traversing
		// into child nodes.
		else
		{
			node = node->loadChild(lastPos, _dataFile, _recSize);
			while ((TreeNode*)node != 0 && !node->isLeaf)
			{
				node = node->loadChild(node->objCount, _dataFile, _recSize);
			}
			if ((TreeNode*)node == 0)
			{
				return false;
			}
			locn.first = node;
			locn.second = node->objCount - 1;
			rec = node->objects[locn.second];
			return true;
		}

		// Finished off a leaf, therefore need to go up to
		// a parent.
		if (goUp)
		{
			size_t childNo = node->childNo;
			node = node->parent;
			while ((TreeNode*)node != 0 && childNo >= node->objCount)
			{
				childNo = node->childNo;
				node = node->parent;
			}
			if ((TreeNode*)node != 0)
			{
				locn.first = node;
				locn.second = childNo - 1;
				rec = node->objects[locn.second];
				ret = true;
			}
		}
		return ret;
	}

	// This method flushes all loaded nodes to the file and
	// then unloads the root node. So not only do we commit
	// everything to file, we also free up any memory previously
	// allocated.
	bool BTreeDB::flush()
	{
		bool ret = _flush(_root, _dataFile);
		if (ret)
		{
			fflush(_dataFile);
		}

		// Unload each of the root's childrent. If we
		// unload the root itself, we lose the use of
		// the tree.
		for (size_t ctr = 0; _root->isLeaf && ctr < _root->objCount; ctr++)
		{
			_root->children[ctr]->unload();
		}
		return ret;
	}
}