在数据库系统中,查询速度的快慢直接影响到应用系统的生命力,其中连接作为关系数据库模型的一个基本的操作,将在不同的关系上进行,使用频率较高,执行的开销也很大,因此查询优化的关键是多元连接查询的优化。本课题将基于连接索引来优化连接查询。关于多元连接查询的优化的讨论,一般都是先讨论连接顺序,选择最小代价的连接先执行。本课题将忽略这个部分,而集中在具体连接操作的优化上,即连接算法的改进。在分析传统连接算法所采用的优化途径和影响连接算法的各个因素的基础上,将利用连接索引来进一步优化连接查询。由于连接索引是预连接产生的,建立在多个关系上,故而需要付出较大的维护代价,在分析连接索引的存储结构和算法改进的过程中,考虑了连接索引对整个DBMS的影响。在对一些已有的基于连接索引的算法分析和比较的基础上,优化了它们的部分实现,并改进了连接索引应用于复杂查询中的情况。空间数据的无序性,使得应用在其上的利用连接索引的算法需要进一步的改进,为此分析了其中关键的最佳页访问次序问题。在分析已有的连接算法的基础上,本课题研究并实现了基于连接索引的改进算法,它有较好的性能,因为它合理利用了分配的内存,只扫描关系中参与连接的部分,尽量避免了冗余的I/O的同时,考虑了排序的代价。实验中考虑了影响连接算法性能的各个因素,采用有针对性的数据集,在不同执行环境下,分析比较了它和以前算法的性能,验证了以上的观点。