本次主题跟我目前的课题结合的比较紧密.我目前主要研究的是基于道路网的时空索引技术,我主要负责利用R-tree数据结构对道路网进行索引构建.
我们索引的基本单位是路段.道路有三种表示方式:路径,路段与直线.
1)路径即是指在行政区划时所标识的道路
2)路段则以路径交点为分割点的道路.
3)直线则是用来拟合曲线道路时所得到的.
由以上定义我们可以得到,路段是折线表示的,在R-tree的索引结构当中如何来表示这种结构呢?其主要问题有几点:
1)路段数据我们用Entry来包含,即最底层的Entry结构中要包含路段信息
2)R-tree结构是基于物体坐标点结构的,因此,每个Entry中要包含此路段中折线的所有折点坐标信息
3)由于我们在存储R-tree结构时, 每一个包含Entry数组的结点RTNode用一个固定大小的页面块来进行存放.但上述原因使得每一个RTNode的字节数并不固定.
因此如何能够找到一种简单的数据结构来维持RTNode的大小一致,同时又能在结点的任一个Entry内取到此路段任一折点的相应坐标,这是这篇文章所要实现的目标.
我采用的方法是利用一个折点文件来存储所有路段中折点的坐标信息.由于坐标信息只要X,Y两个实型数即可表示,因此每一个坐标信息其字节数是固定的,均为16个字节.加上两个实型数之间的空格,与其后的回车字符,每块数据固定字节数为18.因此在记录路段信息的Entry对象中,我只需记录下起始折点的块号与终止折点的块号,即可从折点文件中取到相应数据.而每个Entry中,我只需放入两个长整型,共8个字节,数据块扩展不多,且保证了所有RTNode的空间大小是一致的.
在构建的折点文件中,需要支持以下两个主要工作,即成块地从文件中读取与写入数据,以减少磁盘的I/O次数,提高程序的效率.同时,在文件头我加入一个long型值,以记录文件中存放的块数.文件类定义如下：
#ifndef POINTS_H
#define POINTS_H
#define HEAD_LENGTH (sizeof(long))
#define BLOCK_LENGTH 18
#define TRUE 1
#define FALSE 0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/******* Added these 3 lines ***********/
//文件指针基准常量
//0为文件头,1为当前位置,2为文件尾
#define SEEK_CUR 1
#define SEEK_SET 0
#define SEEK_END 2
/******* end of addition ***************/
typedef char Block[];
class pointsFile{
FILE *fp;
char *fileName;
long number; //存放了多少个点
//----------------------------------------
//读写当前文件中的块数
void fwrite_number(long value)
{ put_bytes((char *) &value,sizeof(long));}
void put_bytes(const char* bytes,long num)
{ fwrite(bytes,num,1,fp); }
void get_bytes(char* bytes,long num)
{ fread(bytes,num,1,fp); }
long fread_number()
{ char ca[sizeof(long)];
get_bytes(ca,sizeof(long));
return *((long *)ca);
}
//----------------------------------------
public:
pointsFile(char* fName);
~pointsFile();
//----------------------------------------
bool read_block(Block b,long pos,int size);
int append_block(const Block b,int size);
int get_num_of_blocks()
{ return number; }
//----------------------------------------
void seek_block(long bnum) //块号由1开始
{ fseek(fp,HEAD_LENGTH+(bnum-1)*BLOCK_LENGTH,SEEK_SET); }
};
#endif
构造函数如下：
pointsFile::pointsFile(char* fName)
{
fileName=new char[sizeof(fName)+1];
strcpy(fileName,fName);
number=0;
//创建文件并写下块数为0
fp=fopen(fileName,"wb+");
if (fp == 0)
{ cout<<"折点文件创建失败"<<endl;
exit(0);
}
fwrite_number(number);
//将文件指针移至文件头
fseek(fp,0,SEEK_SET);
}
按块来读写数据的函数定义如下：
int pointsFile::append_block(const Block b,int size)
{
fseek(fp,0,SEEK_END);
put_bytes(b,BLOCK_LENGTH*size);
//更新块数...
number=number+size;
fseek(fp,0,SEEK_SET);
fwrite_number(number);
fseek(fp,0,SEEK_SET);
//cout<<fread_number()<<endl;
return number;
}
bool pointsFile::read_block(Block b,long pos,int size)
{
//依据块号pos读取相应长度内容，写入b中去
if ((pos+size)<=number+1 && pos>0)
seek_block(pos);
else
return FALSE;
get_bytes(b,BLOCK_LENGTH*size);
//cout<<b<<endl;
fseek(fp,0,SEEK_SET);
//程序读入一串实数字符，长度为size
return TRUE;
}
如何在程序中利用此文件进行块数据写入：
//按块写入数据
char *temp=new char[BLOCK_LENGTH];
for(int i=1;i<=10;i++)
{
b=new char[BLOCK_LENGTH*(i+1)];
sprintf(temp,"%f %f\n",(float)i/10,((float)i/10+0.1));
strcpy(b,temp);
for(int j=1;j<i;j++)
{
strcat(b,temp);
}
points->append_block(b,i);
}
如何从文件中读出数块数据：
//取块数据，从中提取多个数据
//逐字节拷贝实数串，形成一单位后，提取数据
b=new char[BLOCK_LENGTH*3];
points->read_block(b,1,3);
float ff[6];
char *c=new char[BLOCK_LENGTH];
for(int k=0;k<3;k++){
for(int p=0;p<BLOCK_LENGTH;p++)
c[p]=b[k*BLOCK_LENGTH+p];
sscanf(c,"%f %f\n",&ff[k*2],&ff[k*2+1]);
}
经测试，此文件能较好地完成我们预期的任务与目标
