基于闪存固态硬盘内部并行机制的R-树优化方法

陈玉标 李建中 李英姝,2 李发明 高 宏

1(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) 2(佐治亚州立大学计算机科学与技术学院 佐治亚州亚特兰大 30303)(chenyubiao@hit.edu.cn)

从个人电脑到服务器设备，基于闪存的固态硬盘已经被广泛应用.闪存固态硬盘以其耗能低、体积小、高可靠性、读写速度快等特点深受欢迎.与此同时，随着闪存固态硬盘架构的改进，比如集成更多的通道，它具有了丰富的内部并行性.近年来，已经有人对固态硬盘这种性质进行了研究和应用.例如闪存固态硬盘内部并行已经被用来加速关系数据库中索引扫描和聚集[1]，也使B+树索引结构的性能得到很大提升[2].

R-树[3]是一种支持高维数据索引的平衡树结构,被广泛用于空间数据管理[4].目前Spatial Hadoop,MySQL,PostgreSQL,ArcGIS等系统都支持R-树索引结构.目前，针对闪存的R-树优化工作[5-7]主要考虑的是读写不对称引发的写问题以及由频繁写带来的固态硬盘寿命缩短问题.但是，这些工作并没有考虑到固态硬盘的内部并行性[8].本文重点研究如何利用固态硬盘内部并行性加速R-树的查询和更新操作.根据我们所知，本文是最早基于固态硬盘内部并行机制对R-树进行优化的文章之一.本文的主要贡献包括5个方面:

1) 提出了适合于固态硬盘内部并行化的批量异步I/O提交技术;

2) 提出了基于R-树的贪心批量查询处理算法;

3) 提出了R-树的批量更新算法，并基于常数级别的缓冲，设计了一个查询更新的系统结构，该系统结构能大幅度加……