固态盘以其体积小、高带宽、低延迟、低功耗和抗震性等优点逐渐取代机械硬盘成为主流的存储。固态盘由于存储介质是闪存,因而它拥有闪存的所有特点,比如:读写不对称、写前擦除和擦除次数有限特点。早些年,数据管理系统中的外存索引和算法主要是针对磁盘的I/O特性进行设计和优化,很多在闪存介质上已经不再适用。因而,近些年基于闪存特性的索引和外存优化算法逐渐出现,但是它们都是只基于闪存介质的特点。如果把固态盘看作一个整体,随着技术的进步,越来越多的并行资源被集成进固态盘,使得它拥有了丰富的内部并行性。而目前基于固态盘内部并行性特性的工作还比较少,本文将基于固态盘内部并行性及其带来的带宽变化特点对外存排序和范围查询进行优化。具体的研究内容如下:首先,本文研究了如何让外存排序过程充分发挥固态盘内部并行性的问题。本文提出一种固态盘上新的外存排序算法,它基于run生成和run合并两阶段的经典模式。在run生成阶段通过预处理来消除合并阶段数据加载和计算的依赖问题,使得固态硬盘的内部并行性在合并阶段能够充分地发挥作用;与此同时,数据加载依赖的解除又能为进一步的流水线优化提供可能。在无序数据集上进行实验得出的结果表明,和目前固态盘上最优的外存排序算法相比,能取得比较好的加速比。第二,本文研究了闪存固态盘上外存归并排序的最优执行方案问题。外存归并排序作为很多数据管理系统的经典排序算法,它的性能对整体性能有着重要影响。在给定内存资源的情况下,固态盘上外存归并排序的I/O时间主要由输入缓冲区大小、输出缓冲区大小和合并路数决定,这里把上述配置叫做外存归并排序的执行方案。本文研究在内存资源限定的情况下,如何确定一组外存归并排序的最优执行方案使得I/O时间最小的问题。本文基于闪存固态盘带宽特性,提出Sort Decision算法计算在内存资源限定的情况下,使得外存归并排序I/O时间最少的最优执行方案。根据该方案进行外存归并排序,以获得更优秀的执行效率。这里将定内存资源的情况下固态盘上的外存归并排序问题,形式化为一个分段求解的凸优化问题,然后通过枚举每个子凸问题求解的结果,获取最终的外存归并排序策略。经理论分析,该算法的时间复杂度很低,且通过实验结果表明,由Sort Decision算法指导的外存归并排序,在给定内存资源较小的情况下明显优于经典外存归并排序算法。第三,本文研究了固态盘上外存归并排序的内存推荐问题。外存归并排序作为最常采纳的外存排序算法,内存资源对于其性能极其重要。以机械硬盘为环境进行传统的I/O代价分析,均假设单位I/O读写代价是个定值,使得外存归并排序性能最优的最小内存也是个定值。然而,在新型的主流存储固态盘上,由于内部并行性的存在,它的读写带宽随逻辑读写单元变大,带宽变化幅度很大。且当逻辑读写单元很大时,带宽增长的幅度逐渐变小。提供过大的内存会导致内存资源浪费。因而,在固态盘环境下计算出合适的内存大小推荐给外存归并排序,来使得外存排序运行时带宽接近于最大化,与此同时又不会造成内存浪费具有重要意义。因而,本文提出一个针对外存归并排序的内存推荐算法MRCD。它能根据输入的I/O时间偏差率,结合固态盘I/O特征数据和输入数据规模,给出最优的内存推荐。通过理论和实验验证,MRCD可以在任意类型固态盘上,都能保证在外存归并排序实际运行时间偏差率和输入的I/O时间偏差率近乎相等的情况下,实现比较大内存节省的性能表现。最后,本文研究了固态盘上范围查询问题。R-树是支持范围查询索引最重要的索引。因而,本文主要针对R-树上的范围查询进行优化。R-树是地理信息系统的核心索引,范围查询的性能对于地理信息系统非常重要。由于R-树索引任意一对父子结点加载过程必须严格顺序执行,因而很难并行加载,导致I/O加载的并发度降低。进而很难有效地利用固态盘内部并行性去加速范围查询过程中结点的加载。为了克服该困难,提出一种基于栈结构的范围查询算法,栈聚集查询算法SBS。它通过栈模拟查询递归范围查询的执行,通过延迟该过程中的范围查询操作,聚集批量提交提高固态盘内部并行性的触发。然后,通过理论证明该算法只需要O（Blog N）级别的内存空间资源。最后,在真实数据上,通过不同查询范围的实验来验证栈聚集查询算法的性能。