发信人: evilknights (只为一品香), 信区: DotNET
标 题: C#的B+树程序
发信站: BBS 水木清华站 (Fri Dec 13 16:37:39 2002), 转信
我写的，为.NET做点宣传，大家随便看看。
using System;
using System.Xml;
using System.Xml.Serialization;
using System.IO;
namespace Kingsun
{
#region Node Definition Group
public class Pair//Each BPNode stores an array of Pair
{
[XmlElement("pointer")]
public object pointer;//BPNode leaves point to string,
//BPNode internal nodes point to BPNode,a downcast will work when needed
[XmlAttribute("key")]
public int key;//The key value for this pair,in C#,'int' is 32-bit(4-byte)
,
//so there is no need to define it as 'long'
public Pair(int key,object pointer)
{
this.key=key;
this.pointer=pointer;
}
public Pair()
{
}
}//class Pair
[XmlRoot("BPTroot")]
public class BPNode//The BPNode class
{
[XmlAttribute("isLeaf")]
public bool isLeaf;//True if this is a leaf
[XmlElement("Pair")]
public Pair[] recarray;//Array of key/pointer pairs
[XmlAttribute("numrec")]
public int numrec;//Number of pairs currently in node
private BPNode leftptr,rightptr;//Each level forms a doubly-linked table
public void setPrev(BPNode LNode)//protect leftptr from being serialized
{
leftptr=LNode;
}
public BPNode getPrev()
{
return leftptr;
}
public void setNext(BPNode RNode)//protect rightptr from being serialized
{
rightptr=RNode;
}
public BPNode getNext()
{
return rightptr;
}
public bool isFull//read-only property
{
get
{
if(numrec==maxSize)
return true;
else return false;
}
}
public int maxSize//read-only property
{
get
{
if(isLeaf)
return 5;
else return 4;
}
}
public BPNode()//constructor
{
recarray=new Pair[5];
for(int i=0;i<5;i++)
recarray[i]=new Pair();
}
}//class BPNode
#endregion
public class BPT
{
#region Base Section
public BPNode BPTroot;
public BPT()//Initialization
{
BPTroot=new BPNode();
BPTroot.recarray[0]=new Pair(0,"VIRTUAL RECORD");//Virtual record whose k
ey is less than any
BPTroot.numrec=1;
BPTroot.isLeaf=true;
}
[STAThread]
static void Main(string[] args)
{
BPT myBPT=new BPT();
bool running=true;
char inp;
Console.WriteLine("I.Insert a Record");
Console.WriteLine("D.Delete a Record");
Console.WriteLine("V.View a Range");
Console.WriteLine("F.Find a Record");
Console.WriteLine("S.Save to XML");
Console.WriteLine("L.Load from XML");
Console.WriteLine("Q.Quit");
while(running)
{
Console.Write("Please Input[I,D,V,F,S,L,Q]:");
inp=(char)Console.Read();
Console.ReadLine();
switch(inp)//message mapping
{
case 'i':goto case 'I';
case 'I':myBPT.InsertBPT();break;
case 'd':goto case 'D';
case 'D':myBPT.RemoveBPT();break;
case 'v':goto case 'V';
case 'V':myBPT.ViewRange();break;
case 'f':goto case 'F';
case 'F':myBPT.FindBPT();break;
case 's':goto case 'S';
case 'S':myBPT.SaveBPT();break;
case 'l':goto case 'L';
case 'L':myBPT.LoadBPT();break;
case 'q':goto case 'Q';
case 'Q':running=false;break;
}
}
}
#endregion
#region Insert Function Group
void InsertBPT()
{
try
{
Pair tmpPair=new Pair();
Console.Write("Insert Key:");
tmpPair.key=Convert.ToInt32(Console.ReadLine());
if(tmpPair.key<=0)throw new Exception("Keys must be above zero!");
Console.Write("Filename:");
tmpPair.pointer=Console.ReadLine();
Pair retPair=inserthelp(BPTroot,tmpPair);
if(retPair!=null)
{
BPNode NewRoot=new BPNode();
NewRoot.numrec=2;
NewRoot.isLeaf=false;
NewRoot.recarray[0].key=BPTroot.recarray[0].key;
NewRoot.recarray[0].pointer=BPTroot;
NewRoot.recarray[1].key=retPair.key;
NewRoot.recarray[1].pointer=retPair.pointer;
BPTroot=NewRoot;
}
}
catch(Exception e)
{
Console.WriteLine(e.Message);
}
}
//insert recursive entry
Pair inserthelp(BPNode root,Pair tmpPair)
{
Pair insPair;
int currec=binaryle(root.recarray,root.numrec,tmpPair.key);
if(root.isLeaf)//Leaf node -- set up values to insert
{
if(root.recarray[currec].key==tmpPair.key)
{
Console.WriteLine("Duplicates are not allowed for primary key! ");
return null;
}
else insPair=tmpPair;
}
else//internal node
{
insPair=inserthelp((BPNode)root.recarray[currec].pointer,tmpPair);
if(insPair==null)return null;//Child did not split, so no insert into cu
rrent node
}
//Now, do the insert to the current node. Split if neccessary
if(!root.isFull)
{
putinarray(root,currec,insPair);
return null;
}
else
{
BPNode tp=splitnode(root,currec,insPair);
return new Pair(tp.recarray[0].key,tp);
}
}
//putinarray(A,pos,pair) places pair in array A at position pos.
void putinarray(BPNode root,int pos,Pair pair)
{
for(int i=root.numrec-1;i>pos;i--)
{
root.recarray[i+1].key=root.recarray[i].key;
root.recarray[i+1].pointer=root.recarray[i].pointer;
}
root.numrec++;
root.recarray[pos+1].key=pair.key;
root.recarray[pos+1].pointer=pair.pointer;
}
//Function splitnode(rt,pos,pair) places in rt at pos.
//But, int the process, rt is split into two nodes, each
//taking half of the records, and the new node is returned.
BPNode splitnode(BPNode root,int pos,Pair pair)
{
BPNode RNode=new BPNode();
RNode.setNext(root.getNext());
root.setNext(RNode);
RNode.setPrev(root);
if(RNode.getNext()!=null)
RNode.getNext().setPrev(RNode);
//How to split the root depends on whether it's a leaf or non-leaf node
if(root.isLeaf)
{
RNode.numrec=root.numrec=3;//(5+1)/2
RNode.isLeaf=true;
}
else
{
RNode.numrec=2;root.numrec=3;
RNode.isLeaf=false;
}
for(int i=0;i<5;i++)//move the former records
{
int n=i;
if(i>pos)
n=i+1;
if(n>2)
{
RNode.recarray[n-3].key=root.recarray[i].key;
RNode.recarray[n-3].pointer=root.recarray[i].pointer;
}
}
if(pos+1>2)//process the inserted record
{
RNode.recarray[pos-2].key=pair.key;
RNode.recarray[pos-2].pointer=pair.pointer;
}
else
{
root.recarray[pos+1].key=pair.key;
root.recarray[pos+1].pointer=pair.pointer;
}//step2:redirect pointers
return RNode;
}
#endregion
#region Find/View Function Group
void FindBPT()
{
try
{
Console.Write(" Find Key:");
int K=Convert.ToInt32(Console.ReadLine());
int key=K;
BPNode ResultNode=findhelp(BPTroot,ref K);//K is used to pass a key to c
hild function
//and retrieve the index of the key from child funtion
if(ResultNode.recarray[K].key==key)Console.WriteLine((string)ResultNode.
recarray[K].pointer);
else Console.WriteLine("Cannot Find Any!");
}
catch(Exception e)
{
Console.WriteLine(e.Message);
}
}
//find recursive entry
BPNode findhelp(BPNode root,ref int K)
{
int currec=binaryle(root.recarray,root.numrec,K);
if(root.isLeaf)//if it is a leaf node...
{
K=currec;
return root;
}
else return findhelp((BPNode)root.recarray[currec].pointer,ref K);//Proce
ss Child
}
//function binaryle(A,n,K) returns the index of the greatest value
//less than or equal to K in array A containing n records.
int binaryle(Pair[] recarray,int numrec,int K)
{
int i=1;//the first virtual one(i=0) can never be greater than K
while(i<numrec)//do-while is OK
{
if(recarray[i].key>K)break;
else i++;
}
return i-1;
}
void ViewRange()
{
try
{
Console.Write("Range Start Key:");
int K1=Convert.ToInt32(Console.ReadLine());
int key=K1;
Console.Write("Range End Key:");
int K2=Convert.ToInt32(Console.ReadLine());
BPNode ResultNode=findhelp(BPTroot,ref key);//K is used to pass a key to
child function
//and retrieve the index of the key from child funtion
if(ResultNode.recarray[key].key==K1)Console.WriteLine("{0}\t
{1}",K1,(string)ResultNode.recarray[key].pointer);
key++;
for(;;)
{
if(key==ResultNode.numrec)
{
ResultNode=ResultNode.getNext();
key=0;
}
if((ResultNode!=null)&&(ResultNode.recarray[key].pointer!=null)&&(Resul
tNode.recarray[key].key<=K2))
Console.WriteLine("{0}\t{1}",ResultNode.recarray[key].key,(string)Resu
ltNode.recarray[key].pointer);
else break;
key++;
}
}
catch(Exception e)
{
Console.WriteLine(e.Message);
}
}
#endregion
#region Save/Load Function Group
void SaveBPT()
{
try
{
XmlSerializer serializerw = new XmlSerializer(typeof(BPNode));
TextWriter writer = new StreamWriter("BPTExpr.xml");
serializerw.Serialize(writer,BPTroot);
writer.Close();
}
catch(Exception e)
{
Console.WriteLine(e.Message);
}
}
void LoadBPT()
{
try
{
XmlSerializer serializerr = new XmlSerializer(typeof(BPNode));
FileStream fs = new FileStream("BPTExpr.xml", FileMode.Open);
BPTroot = (BPNode)serializerr.Deserialize(fs);
fs.Close();
ReCreateLink(BPTroot);
}
catch(Exception e)
{
Console.WriteLine(e.Message);
}
}
void ReCreateLink(BPNode root)
{
if(root.isLeaf)return;//There's no need to re-create links for single-nod
e tree
if(!((BPNode)root.recarray[0].pointer).isLeaf)
for(int i=0;i<root.numrec;i++)
ReCreateLink((BPNode)root.recarray[i].pointer);
for(int i=0;i<root.numrec-1;i++)
{
((BPNode)root.recarray[i].pointer).setNext((BPNode)root.recarray[i+1].po
inter);
((BPNode)root.recarray[i+1].pointer).setPrev((BPNode)root.recarray[i].po
inter);
}
}
#endregion
#region Delete Function Group
void RemoveBPT()
{
try
{
Console.Write("Delete Key:");
int K=Convert.ToInt32(Console.ReadLine());
if(K==0)throw new Exception("Virtual Record is not allowed to delete!");
int retvalue=removehelp(BPTroot,K,0);
if(retvalue==-2)
throw new Exception("Record Not Found");
else if(retvalue==0)
BPTroot=(BPNode)BPTroot.recarray[0].pointer;
}
catch(Exception e)
{
Console.WriteLine(e.Message);
}
}
//delete recursive entry removehelp returns position of the child node adj
usted,
//if any. If the child node did not underflow or change its first record,
//then return -1, to indicate the parent shouldn't be modified.
int removehelp(BPNode root,int K,int thispos)
{
int currec=binaryle(root.recarray,root.numrec,K);
if(root.isLeaf)
{
if(root.recarray[currec].key!=K)
return -2;
}
else
{//Delete from child
currec=removehelp((BPNode)root.recarray[currec].pointer,K,currec);
if(currec<0)//Child did not underflow -1 or cannot find record -2
return currec;
else if(((BPNode)root.recarray[currec].pointer).numrec!=0)
{//Child was shuffled -- adjust key value
root.recarray[currec].key= ((BPNode)root.recarray[currec].pointer).reca
rray[0].key;
return -1;//Child did not underflow
}
}
//Now,remove record at position currec,for internal node, this means its
child has been cleared.
removerec(root,currec);
if(root.numrec>2)//Enough records, just remove it
return -1;
else
{//Underflow, if it doesn't have any left neighbour,then merge right,else
merge left
if((root.getPrev()==null)&&(root.getNext()==null))
{//root node
if((root.numrec==1)&&(!root.isLeaf))
return 0;//0 notify BPTroot to decrease its level
else return -1;
}
else if(root.getPrev()==null)
{//the left most node
if(root.numrec+root.getNext().numrec<=root.maxSize)
{
merge_nodes(root,root.getNext());
return thispos+1;//Right neighbour is now empty
}
else
{
shuffle_nodes(root,root.getNext());
return thispos+1;//Right neighbour has new first record
}
}
else
{//other node
if(root.numrec+root.getPrev().numrec<=root.maxSize)
{
merge_nodes(root.getPrev(),root);
return thispos;//This node is now empty
}
else
{
shuffle_nodes(root.getPrev(),root);
return thispos;//This node has new first record
}
}
}
}
//Funciton merge_nodes(N1,N2) merges together the record arrays of BPNodes
N1 and N2.
void merge_nodes(BPNode left,BPNode right)
{
for(int i=left.numrec;i<left.numrec+right.numrec;i++)
{
left.recarray[i].key=right.recarray[i-left.numrec].key;
left.recarray[i].pointer=right.recarray[i-left.numrec].pointer;
}
left.numrec+=right.numrec;
right.numrec=0;
left.setNext(right.getNext());
if(right.getNext()!=null)
right.getNext().setPrev(left);
}
//Function shuffle_nodes(N1,N2) copies records as necessary within
//BPNodes N1 and N2, so that both have equal number of records.
void shuffle_nodes(BPNode left,BPNode right)
{
if(left.numrec>right.numrec)
{
for(int i=1;i>=0;i--)//at most two need to move
{
right.recarray[i+1].key=right.recarray[i].key;
right.recarray[i+1].pointer=right.recarray[i].pointer;
}
right.recarray[0].key=left.recarray[left.numrec-1].key;
right.recarray[0].pointer=left.recarray[left.numrec-1].pointer;
left.numrec--;right.numrec++;
}
else
{
left.recarray[left.numrec].key=right.recarray[0].key;
left.recarray[left.numrec].pointer=right.recarray[0].pointer;
for(int i=0;i<right.numrec-1;i++)
{
right.recarray[i].key=right.recarray[i+1].key;
right.recarray[i].pointer=right.recarray[i+1].pointer;
}
left.numrec++;right.numrec--;
}
}
//Function removerec(A,n,c) removes the record at position c from array A
containing n records.
void removerec(BPNode root,int pos)
{
for(int i=pos;i<root.numrec-1;i++)
{
root.recarray[i].key=root.recarray[i+1].key;
root.recarray[i].pointer=root.recarray[i+1].pointer;
}
root.numrec--;
}
#endregion
}//class BPT
}//namespace Kingsun
--
※ 来源:·BBS 水木清华站 smth.edu.cn·[FROM: 166.111.203.12]
返回上一页
回到目录
回到页首
下一篇
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机技术与应用 → 『 Dot NET,C#,ASP,VB 』 → C#的B+树程序
(订阅本版)
2004/11/9 2:25:00
新浪微博
C#的B+树程序
