bulkload.cpp

M树源代码

			tree->Create(newname);	// create the new sub-tree
//			cout << "Now building sub-tree " << newname << " on " << ns[i] << " data (exp. size=" << sizes[i] << ")...\n";
			tree->BulkLoad(arrays[i], ns[i], padFactor, newname);	// insert the data into the sub-tree
//			cout << "Tree level=" << tree->MaxLevel() << endl;
			// if the root node is underfilled, we have to split the tree
			path.MakeRoot();
			root=(MTnode *)tree->ReadNode(path);
			if(root->IsUnderFull(*Store())) {
				GiSTlist<MTentry *> *roots=new GiSTlist<MTentry *>;
				GiSTlist<char *> *list=tree->SplitTree(&ncreated, tree->MaxLevel()-1, roots, name);	// split the tree

				nsamples--;
				while(!list->IsEmpty()) {	// insert all the new trees in the sub-trees list
					MTentry *e=roots->RemoveFront();

					othernameslist.Append(list->RemoveFront());
					for(j=0; j<n; j++) if(data[j]->object()==e->object()) {	// append also the root entry to the parents list
//						cout << "parent=" << data[j];
						plist.Append(data[j]);
						j=n;
					}
					delete e;
					nsamples++;
				}
				delete list;
				delete roots;
				minLevel=MIN(minLevel, tree->MaxLevel()-1);
			}
			else {
				char *tmp=new char[50];

				strcpy(tmp, newname);
				othernameslist.Append(tmp);
				plist.Append(data[samples[i]]);
				minLevel=MIN(minLevel, tree->MaxLevel());
			}
			delete root;
			tree->Close();
			delete tree->Store();	// it was created in tree->Create()
		}
		for(i=0; i<nInit; i++)  {
			for(j=0; j<ns[i]; j++) delete arrays[i][j];
			delete []arrays[i];
		}
		delete []arrays;
		while(!plist.IsEmpty()) {	// insert the trees in the list (splitting if necessary)
			MTentry *parent=plist.RemoveFront();
			char *tmp=othernameslist.RemoveFront();

			strcpy(newname, tmp);
			delete []tmp;
			tree->Open(newname);
//			cout << ": Tree level=" << tree->MaxLevel() << " (" << minLevel << ")\n";
			if(tree->MaxLevel()>minLevel) {	// we have to split the tree to reduce its height
//			cout << "level too high!!! (min=" << minLevel << ") Splitting the tree...\n";
				GiSTlist<MTentry *> *roots=new GiSTlist<MTentry *>;
				GiSTlist<char *> *list=tree->SplitTree(&ncreated, minLevel, roots, name);	// split the tree

				nsamples--;
				while(!list->IsEmpty()) {	// insert all the new trees in the sub-trees list
					MTentry *e=roots->RemoveFront();

					nameslist.Append(list->RemoveFront());
					for(j=0; j<n; j++) if(data[j]->object()==e->object()) {	// append also the root entry to the parents list
//						cout << "parent=" << data[j];
						parentslist.Append(data[j]);
						j=n;
					}
					delete e;
					nsamples++;
				}
				delete list;
				delete roots;
			}
			else {	// simply insert the tree and its root to the lists
				char *tmp=new char[50];

				strcpy(tmp, newname);
				nameslist.Append(tmp);
//				cout << "parent=" << data[samples[i]];
				parentslist.Append(parent);
			}
			tree->Close();
			delete tree->Store();	// it was created in tree->Open()
		}
		parents=new MTentry *[nsamples];
		trees=new char *[nsamples];
		for(i=0; i<nsamples; i++) {	// convert the lists into arrays
			trees[i]=nameslist.RemoveFront();
			parents[i]=parentslist.RemoveFront();
		}
		// build the super-tree upon the parents
		sprintf(newname, "%s.0", name);
//		cout << "Now building super-tree " << newname << " on " << nsamples << " data...\n";
		BulkLoad(parents, nsamples, padFactor, newname);
		// attach each sub-tree to the leaves of the super-tree
		path.MakeRoot();
		node=(MTnode *)ReadNode(path);
		oldList->Append(node);
//		cout << "super-tree built!\n";
		l=node->Level();
		while(l>0) {	// build the leaves list for super-tree
			GiSTlist<MTnode *> *newList=new GiSTlist<MTnode *>;

			while(!oldList->IsEmpty()) {
				node=oldList->RemoveFront();
				path=node->Path();
				node->SetLevel(node->Level()+minLevel);	// update level of the upper nodes of the super-tree
				WriteNode(node);
				for(i=0; i<node->NumEntries(); i++) {
					MTentry *e=(MTentry *)(*node)[i].Ptr();

					path.MakeChild(e->Ptr());
					newList->Append((MTnode *)ReadNode(path));
					path.MakeParent();
				}
				delete node;
			}
			delete oldList;
			oldList=newList;
			l--;
		}
//		cout << "Finished " << newname << endl;
		while(!oldList->IsEmpty()) {	// attach each sub-tree to its leaf
			GiSTpath rootpath;

			rootpath.MakeRoot();
			node=oldList->RemoveFront();	// retrieve next leaf (root of sub tree)
			node->SetLevel(minLevel);	// update level of the root of the sub-tree
			path=node->Path();
			for(i=0; i<node->NumEntries(); i++) {
				MTnode *newnode=(MTnode *)CreateNode();
				MTentry *e=(MTentry *)(*node)[i].Ptr();
				GiSTpath newpath;

				path.MakeChild(Store()->Allocate());
				newnode->Path()=path;
				e->SetPtr(path.Page());
				path.MakeParent();
				for(j=0; e->object()!=parents[j]->object(); j++);	// search the tree to append
				tree->Open(trees[j]);
//				cout << "Now appending sub-tree " << trees[j] << endl;
				Append(newnode, (MTnode *)tree->ReadNode(rootpath));	// append this sub-tree to the super-tree
				tree->Close();
				delete tree->Store();	// it was created in tree->Open()
				newpath=newnode->Path();
				delete newnode;
			}
			WriteNode(node);
			delete node;
		}
		tree->Open(trees[0]);	// in order to destroy the object tree
		delete tree;
		for(i=0; i<nsamples; i++) delete []trees[i];
		delete []trees;
		// update radii of the upper nodes of the result M-tree
		path.MakeRoot();
		node=(MTnode *)ReadNode(path);
		oldList->Append(node);
		l=node->Level();
		while(l>=minLevel) {	// build the list of the nodes which radii should be recomputed
			GiSTlist<MTnode *> *newList=new GiSTlist<MTnode *>;

			while(!oldList->IsEmpty()) {

				node=oldList->RemoveFront();
				path=node->Path();
				for(i=0; i<node->NumEntries(); i++) {
					MTentry *e=(MTentry *)(*node)[i].Ptr();

					path.MakeChild(e->Ptr());
					newList->Append((MTnode *)ReadNode(path));
					path.MakeParent();
				}
				delete node;
			}
			delete oldList;
			oldList=newList;
			l--;
		}
		while(!oldList->IsEmpty()) {	// adjust the radii of the nodes
			MTnode *node=oldList->RemoveFront();

			AdjKeys(node);
			delete node;
		}
		// be tidy...
		delete oldList;
		delete []parents;
		delete []sizes;
		delete []ns;
		delete []sampled;
		delete []samples;
		for(i=0; i<=ncreated; i++) {	// delete all temporary sub-trees
			  sprintf(newname, "%s.%i", name, i);
			  unlink(newname);
		}
	}
	else {	// we can insert all the entries in a single node
		GiSTpath path;
		GiSTnode *node;

		path.MakeRoot();
		node=ReadNode(path);
		for(i=0; i<n; i++)
			node->Insert(*(data[i]));
		assert(!node->IsOverFull(*Store()));
//		cout << "real size=" << node->Size() << endl;
		WriteNode(node);
		delete node;
	}
}

// append the sub-tree rooted at from to the node to
// this is used in the "append" phase of the BulkLoad algorithm
void
MT::Append(MTnode *to, MTnode *from)
{
	GiSTlist<MTnode *> *oldList=new GiSTlist<MTnode *>;	// list of the nodes to append
	GiSTlist<GiSTpath> pathList;
	MT *fromtree=(MT *)from->Tree();
	MTnode *node=new MTnode, *newnode;

//	cout << "Appending " << from;
	oldList->Append(from);
	pathList.Append(to->Path());
	do {
		GiSTlist<MTnode *> *newList=new GiSTlist<MTnode *>;

		while(!oldList->IsEmpty()) {
			GiSTpath newpath=pathList.RemoveFront();

			delete node;
			node=oldList->RemoveFront();
			newnode=(MTnode *)ReadNode(newpath);
//			cout << "Inserting " << node->NumEntries() << " entries:\n";
			for(int i=0; i<node->NumEntries(); i++) {
				MTentry *e=(MTentry *)(*node)[i].Ptr()->Copy();

				if(node->Level()>0) {	// if node isn't a leaf, we've to allocate its children
					GiSTpath nodepath=node->Path();
					MTnode *childnode=(MTnode *)CreateNode(), *fromnode;

					nodepath.MakeChild(e->Ptr());
					fromnode=(MTnode *)fromtree->ReadNode(nodepath);
					newList->Append(fromnode);
					e->SetPtr(Store()->Allocate());
					newpath.MakeChild(e->Ptr());
					childnode->Path()=newpath;
					childnode->SetTree(this);
					WriteNode(childnode);	// write the empty node
					pathList.Append(newpath);
					newpath.MakeParent();
					nodepath.MakeParent();
					delete childnode;
				}
				newnode->Insert(*e);
//				cout << "\tInserted " << e;
				delete e;
			}
			newnode->SetLevel(node->Level());
			WriteNode(newnode); // write the node
//			cout << "Created " << newnode;
			delete newnode;
		}
		delete oldList;
		oldList=newList;
	} while(node->Level()>0);	// until we reach the leaves' level
//	cout << node;
	delete node;
	delete oldList;
}

// adjust the keys of node
// this is used during the final phase of the BulkLoad algorithm
void
MT::AdjKeys(GiSTnode *node)
{
	GiSTnode *P;
	GiSTpath parent_path=node->Path();
	GiSTentry *entry, *actual;

	if(node->Path().IsRoot()) return;
	parent_path.MakeParent();
	P=ReadNode(parent_path);
	entry=P->SearchPtr(node->Path().Page());
	assert(entry!=NULL);
	actual=node->Union();
	actual->SetPtr(node->Path().Page());
	((MTkey *)actual->Key())->distance=((MTkey *)entry->Key())->distance;	// necessary to keep track of the distance from the parent
	if(!entry->IsEqual(*actual)) {	// replace this entry
		int pos=entry->Position();

		P->DeleteEntry(pos);
		P->Insert(*actual);
/*		if(P->IsOverFull(*Store())) {	// this code should be unnecessary (if we have fixed length entries)
		  GiSTpage page=node->Path().Page();

		  Split(&P, *actual);
		  node->Path()=P->Path();
		  node->Path().MakeChild(page);
		}
		else {
		  WriteNode(P);
		  AdjKeys(P);
		}	*/
		WriteNode(P);
		AdjKeys(P);
	}
	delete P;
	delete actual;
	delete entry;
}