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();