随着生物技术的发展,许多致力于研究物种基因的项目已取得了很大的成就。大量的物种引起了人类浓厚兴趣,如果能加快序列处理技术的发展,就能从许多新的序列中发现更多的特征。在这样的情况下,研究人员利用索引技术来改进序列的处理。对于较小的序列来说,后缀树索引无疑是一种很好的解决办法,但由于它产生了“内存瓶颈”,不适合大的序列;后缀数组是另一种最具有竞争力的索引结构,与后缀树相比,它需更少的存储空间,但在数据搜索方面却效率较低;基于q-gram和q-sample的索引方法虽然能用于快速搜索,但是不能用于搜索相似度低的数据。本文提出了一种分层的索引结构,使用这种结构能够建立超过内存容量的索引,而且能有效得执行各种数据搜索。分层索引结构是基于后缀树的,它由若干层组成,通常情况下,每一层又包括若干棵子后缀树。本文按照层次递进的顺序依次建立,并独立存储每一层。在索引的建立技术上,本文采用“自顶向下且只写”的思想。整个建立算法包括三个部分:后缀排序,计算最短公共前缀和建立子后缀树。在建立每层索引的过程中,这三个步骤均能在线性时间内完成。在存储策略上,本文把整个索引划分为两部分:第一部分保存子后缀树的信息,子后缀树可以采用多种不同的优化方法存储,每种方法所需的存储空间和性能均不相同。第二部分是索引部分,包括子后缀树的索引和其他信息。利用这部分信息,可以快速定位每棵子后缀树在磁盘中的位置。根据不同的子后缀树存储方法,本文介绍了多种搜索方法。同时,还研究了内存空间中的子后缀树管理方法。在最后的实验部分中,使用本文的索引结构和建立方法建立了比内存更大的索引,并在时间和空间上都获得良好的效果。此外,还用实验验证了存储策略和搜索方法的各种性能。