mtnode.cpp

M树源代码

/*********************************************************************
*                                                                    *
* Copyright (c) 1997,1998, 1999                                      *
* Multimedia DB Group and DEIS - CSITE-CNR,                          *
* University of Bologna, Bologna, ITALY.                             *
*                                                                    *
* All Rights Reserved.                                               *
*                                                                    *
* Permission to use, copy, and distribute this software and its      *
* documentation for NON-COMMERCIAL purposes and without fee is       *
* hereby granted provided  that this copyright notice appears in     *
* all copies.                                                        *
*                                                                    *
* THE AUTHORS MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE        *
* SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING  *
* BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY,      *
* FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHOR  *
* SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A      *
* RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS    *
* DERIVATIVES.                                                       *
*                                                                    *
*********************************************************************/

#include <string.h>
#include "MT.h"
#include "MTpredicate.h"

double MIN_UTIL;	// minimum node utilization
pp_function PROMOTE_PART_FUNCTION;	// promotion method
pv_function PROMOTE_VOTE_FUNCTION;	// confirmed promotion method (if needed)
pp_function SECONDARY_PART_FUNCTION;	// root promotion method (can't use stored distances): used only for confirmed and MAX_UB_DIST methods
r_function RADIUS_FUNCTION;	// mM_RAD promotion method (if needed)
int NUM_CANDIDATES;	// number of candidates for sampling
s_function SPLIT_FUNCTION;	// split method

extern int IOread;

// used to quick-sort the entries in a node according to their distance from the parent
int
MTentrycmp(const void *x, const void *y)
{
	double d=(*(MTentry **)x)->Key()->distance-(*(MTentry **)y)->Key()->distance;
	int i=0;

	if(d>0) i=1;
	else if(d<0) i=-1;
	return i;
}

// used in Split to find the next nearest entry
int
FindMin(double *vec, int veclen)
{
	int i, min_i=-1;
	double min=MAXDOUBLE;

	for(i=0; i<veclen; i++)
		if(vec[i]<min) {
			min_i=i;
			min=vec[i];
		}
	return min_i;
}

GiSTobject *
MTnode::NCopy()
{
	MTnode *newnode=(MTnode *)Copy();

	if((obj==NULL)&&(Path().Level()>1)) {
		MTentry *e=Entry();

		obj=newnode->obj=&(e->object());
		delete e;
	}
	newnode->InvalidateEntries();
	return newnode;
}

#ifdef PRINTING_OBJECTS
void
MTnode::Print(ostream& os) const
{
	if(obj!=NULL) os << *obj << " ";
//	else cout << "obj NULL...\n";
	os << ((MTnode *)this)->Path() << " #Entries: " << NumEntries() << ", Level " << Level();
	if(IsLeaf()) os << "(Leaf)";
	else os << "(Internal)";
	os << ", Sibling: " << Sibling() << ", Size: " << Size() << "/" << Tree()->Store()->PageSize() << endl;
	for(int i=0; i<NumEntries(); i++) (*this)[i]->Print(os);
}
#endif

int
MTnode::IsUnderFull(const GiSTstore &store) const
{
	return ((MIN_UTIL>0)&&(Size()<(int)(store.PageSize()*MIN_UTIL)));
}

void
MTnode::InvalidateEntries()
{
	for(int i=0; i<NumEntries(); i++)
		((MTentry *)((*this)[i].Ptr()))->Key()->distance=-maxDist();
}

void
MTnode::InvalidateEntry(BOOL isNew)
{
	GiSTpath path=Path();
	if(path.Level()>1) {
		MTnode *parent=((MT *)Tree())->ParentNode((MTnode *)this), *gparent=((MT *)Tree())->ParentNode(parent);
		int i;

		for(i=0; i<parent->NumEntries(); i++) {	// search the entry between the parent's children
			MTentry *e=(MTentry *)((*parent)[i].Ptr());

			if(e->Ptr()==path.Page()) {
				if(isNew) e->Key()->distance=-maxDist();
//				else e->Key()->distance=-e->Key()->distance;
				e->Key()->splitted=TRUE;
				break;
			}
		}
		path.MakeParent();
		for(i=0; i<gparent->NumEntries(); i++) {	// search the parent entry between the grandparent's children
			MTentry *e=(MTentry *)((*gparent)[i].Ptr());

			if(e->Ptr()==path.Page()) {
				e->setmaxradius(-1);
				break;
			}
		}
		((MT *)Tree())->WriteNode(parent);	// write parent node (in inconsistent state)
		((MT *)Tree())->WriteNode(gparent);	// write gparent node (to invalidate the parent's entry)
		delete parent;
		delete gparent;
	}
}

MTentry *
MTnode::Entry() const
{
	GiSTpath path=((MTnode *)this)->Path();
	MTnode *parent=((MT *)Tree())->ParentNode((MTnode *)this);
	MTentry *returnEntry=NULL;

	for(int i=0; (i<parent->NumEntries())&&(returnEntry==NULL); i++)
		if((*parent)[i].Ptr()->Ptr()==path.Page()) returnEntry=(MTentry *)(*parent)[i].Ptr()->Copy();
	delete parent;
	return returnEntry;
}

double
MTnode::distance(int i) const
{
	MTentry *e=(MTentry *)((*this)[i].Ptr());

//	if(e->Key()->distance>=0) cout << "Distance between " << obj << " & " << e->object() << " = " << e->Key()->distance << endl;
//	else cout << "Computing distance between " << obj << " & " << e->object() << "..." << endl;
	return (e->Key()->distance<0)? ((e->Key()->distance>-maxDist())? -e->Key()->distance: obj->distance(e->object())): e->Key()->distance;
}

// SearchMinPenalty returns where a new entry should be inserted.
// Overriden to insert the distance from the parent in the new entry.
GiSTpage
MTnode::SearchMinPenalty(const GiSTentry& newEntry) const
{
	MTentry *minEntry=NULL;
	MTpenalty *minPenalty=NULL;

	for(int i=0; i<NumEntries(); i++) {
		MTentry *e=(MTentry *)((*this)[i].Ptr());

		assert((MTnode *)e->Node()==this);
		MTpenalty *penalty=(MTpenalty *)e->Penalty(newEntry, minPenalty);	// use the alternate Penalty method in order to avoid some distance computations

		if((minEntry==NULL)||(*penalty)<(*minPenalty)) {
			minEntry=e;
			if(minPenalty) delete minPenalty;
			minPenalty=penalty;
		}
		else delete penalty;
	}
	((MTentry&)newEntry).Key()->distance=minPenalty->distance;
	delete minPenalty;
	return minEntry->Ptr();
}

void
MTnode::InsertBefore(const GiSTentry& entry, int index)
{
	int n=NumEntries();
	BOOL ordered=TRUE;

	if(index>0) ordered=((*this)[index-1]->Compare(entry)<=0);
	if(index<n) ordered=ordered&&((*this)[index]->Compare(entry)>=0);
	if(ordered) {	// yes, the position is right for this entry
		assert(index<=n);
		GiSTentry *e=(GiSTentry *)entry.Copy();

		e->SetLevel(Level());
		e->SetPosition(index);
		e->SetNode(this);
		// Move everything else over
		for(int i=n; i>index; i--) {
			GiSTentry *e=(*this)[i-1];

			e->SetPosition(i);
			(*this)[i]=e;
		}
		// Stick the entry in
		(*this)[index]=e;
		// Bump up the count
		SetNumEntries(n+1);
	}
	else Insert(entry);	// find the right place
}

// quick-sort the entries with respect to the distance from the parent
void
MTnode::Order()
{
	int i, obji=-1, n=NumEntries();
	MTentry **array=new MTentry *[n], *objEntry=NULL;

	for(i=0; i<n; i++) {
		array[i]=(MTentry *)((MTentry *)(*this)[i].Ptr())->Copy();
		if(obj==&((MTentry *)(*this)[i].Ptr())->object()) objEntry=array[i];
	}
	qsort(array, n, sizeof(MTentry *), MTentrycmp);
	while(NumEntries()>0) DeleteEntry(0);
	for(i=0; i<n; i++) {
		InsertBefore(*(array[i]), i);
		if(objEntry==array[i]) obji=i;
		delete array[i];
	}
	delete []array;
	if(obji>=0) obj=&((MTentry *)(*this)[obji].Ptr())->object();
}

GiSTnode *
MTnode::PickSplit()
{
	MTnode *rightnode;
	int leftdeletes, rightdeletes;	// number of entries to be deleted from each node
	int *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()];	// array of entries to be deleted from each node

	// promote the right node (possibly reassigning the left node);
	// the right node's page is copied from left node; 
	// we'll delete from the nodes as appropriate after the splitting phase
//	cout << "In PickSplit with node " << this << "\n";
	rightnode=PromotePart();
	// now perform the split
	Split(rightnode, leftvec, rightvec, &leftdeletes, &rightdeletes);	// complexity: O(n)
	// given the deletion vectors, do bulk deletes
	DeleteBulk(leftvec, leftdeletes);
	rightnode->DeleteBulk(rightvec, rightdeletes);
//	cout << "Nodes:\n" << this << rightnode;
	// order the entries in both nodes
	Order();
	rightnode->Order();
	delete []leftvec;
	delete []rightvec;
	// return the right node
	return rightnode;
}

MTnode *
MTnode::PromotePart()
{
	MTnode *newnode;

	switch(PROMOTE_PART_FUNCTION) {
		case RANDOM: {	// complexity: constant
			int i, j;

			// pick two *different* random entries
//			cout << "Random promotion: ";
			i=PickRandom(0, NumEntries());
			do j=PickRandom(0, NumEntries());
			while (j==i);
			if(((MTentry *)(*this)[j].Ptr())->Key()->distance==0) {
				int k=i; i=j; j=k;	// if we chose the parent entry, put it in the left node
			}
//			cout << "Entries " << (*this)[i].Ptr() << " & " << (*this)[j].Ptr() << " chosen.\n";
			newnode=(MTnode *)NCopy();
			// re-assign the nodes' object
			newnode->obj=&((MTentry *)((*newnode)[j].Ptr()))->object();
			obj=&((MTentry *)((*this)[i].Ptr()))->object();
			if(((MTentry *)(*this)[i].Ptr())->Key()->distance>0) {	// if the parent object wasn't confirmed, invalidate also the parent
				InvalidateEntry(TRUE);
				InvalidateEntries();
			}
			else InvalidateEntry(FALSE);	// else, invalidate only the node's radii
			break;
		}
		case CONFIRMED: {	// complexity: determined by the confirmed promotion algorithm
			int i;
			BOOL isRoot=TRUE;

//			cout << "Confirmed promotion: ";
//			for(i=0; (i<NumEntries())&&(isRoot); i++) isRoot=(((MTentry *)((*this)[i].Ptr()))->Key()->distance==-MAXDIST);
			isRoot=(((MTentry *)((*this)[0].Ptr()))->Key()->distance==-maxDist());	// we have ordered entries
			if(isRoot) {	// if we're splitting the root we have to use a policy that doesn't use stored distances
				PROMOTE_PART_FUNCTION=SECONDARY_PART_FUNCTION;	
				newnode=PromotePart();
				PROMOTE_PART_FUNCTION=CONFIRMED;
			}
			else {
				int index=-1;

				for(i=0; (i<NumEntries())&&(index<0); i++) if(((MTentry *)((*this)[i].Ptr()))->Key()->distance==0) index=i;
				obj=&((MTentry *)((*this)[index].Ptr()))->object();
				// now choose the right node parent
				newnode=PromoteVote();
			}
			InvalidateEntry(FALSE);
			break;