学习索引:现状与研究展望*
2021-05-23金培权谢希科
软件学报 2021年4期
关键词:模型
张 洲 ,金培权 ,谢希科
1(中国科学技术大学 计算机科学与技术学院,安徽 合肥 230026)
2(电磁空间信息重点实验室(中国科学院),安徽 合肥 230026)
索引是数据库系统中用于提升数据存取性能的主要技术之一.传统数据库系统一般使用磁盘作为持久性存储设备.但是由于磁盘的访问延迟较高,磁盘I/O 次数成为影响数据库系统性能的关键指标.如何快速地在磁盘中找到数据,成为数据库系统中的重要问题.自20 世纪70 年代以来,数据库领域的研究人员提出了各种各样的索引结构,用于满足不同数据类型的存取性能需求.例如,著名的B+树索引结构[1]提供了O(logmn)的查询时间复杂度(m为一个树节点的容量)[2].通常情况下,B+树索引的I/O 次数为3~4 次,远远优于无索引的搜索算法(例如二分搜索).而且,由于数据在B+树的叶节点中有序存储,它也可以支持高效的范围查询.
传统的B+树索引是基于磁盘而设计的,即假设整个索引完全存储在磁盘中.为了提升数据库系统的读写性能,现代数据库系统倾向于将整个索引缓存在内存中.当数据库规模较小时,缓存索引是可行的.然而,在大数据时代,数据量可能达到PB 级甚至百PB 级.例如,物联网中的高频传感器采集数据、大型互联网交易平台的日志数据等每天都会产生大量的新数据,使得数据库规模极速增长.这种情况下,传统的B+树索引因其具有O(n)的空间复杂度将无法全部缓存在内存,进而影响查询性能.虽然近年来有研究者提出……
登录APP查看全文
