新时期数据管理技术

基于LevelDB的二维数据二级索引实现

  • 刘子豪 ,
  • 胡卉芪 ,
  • 徐瑞 ,
  • 周烜
展开
  • 华东师范大学 数据科学与工程学院, 上海 200062
刘子豪,男,硕士研究生,研究方向为数据库系统.E-mail:geniuslzh@qq.com.

收稿日期: 2019-07-29

  网络出版日期: 2019-10-11

基金资助

国家自然科学基金青年科学基金项目(61702189)

Implementation of LevelDB-based secondary index on two-dimensional data

  • LIU Zi-hao ,
  • HU Hui-qi ,
  • XU Rui ,
  • ZHOU Xuan
Expand
  • School of Data Science and Engineering, East China Normal University, Shanghai 200062, China

Received date: 2019-07-29

  Online published: 2019-10-11

摘要

随着科学研究中产生的空间数据尤其是二维数据量级的增长和NoSQL型数据库技术的发展,越来越多的空间数据被存储到NoSQL数据库中.LevelDB是一款开源的Key-Value型NoSQL数据库,由于它基于LSM架构并拥有较好的写入性能而被广泛应用.但是Key-Value结构的局限性使其无法有效地索引空间数据,对于这个问题本文提出了一种基于LevelDB和R-tree的二级索引,使其可以支持二维数据的索引和近邻查询.实验结果表明该结构有较好的可用性.

本文引用格式

刘子豪 , 胡卉芪 , 徐瑞 , 周烜 . 基于LevelDB的二维数据二级索引实现[J]. 华东师范大学学报(自然科学版), 2019 , 2019(5) : 159 -167 . DOI: 10.3969/j.issn.1000-5641.2019.05.013

Abstract

With the growth of spatial data generated by scientific research, especially two-dimensional data and the ongoing development of NoSQL-type database technology, more and more spatial data is now stored in NoSQL databases. LevelDB is an open source Key-Value NoSQL database that is widely used because it offers excellent write performance based on LSM architecture. Given the limitations of the Key-Value structure, it is impossible to index spatial data effectively. For this problem, a LevelDB and R-treebased secondary index was proposed to support spatial two-dimensional data indexing and neighbor queries. Experimental results show that the structure has good usability.

参考文献

[1] Google Inc. LevelDB[EB/OL].[2019-06-20]. https://githbu.com/google/leveldb.
[2] BECKMANN N, KRIEGEL H P, SCHNEIDER R, et al. The R*-tree:An efficient and robust access method for points and rectangles[C]//ACM Sigmod Record. ACM, 1990, 19(2):322-331.
[3] LUO C, CAREY M J. LSM-based storage techniques:A survey[J/OL]. arXiv preprint, arXiv:1812.07527, 2018.
[4] WU L, LIN W, XIAO X, et al. LSⅡ:An indexing structure for exact real-time search on microblogs[C]//2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 2013:482-493.
[5] KHODAEI A, SHAHABI C, LI C, et al. Hybrid indexing and seamless ranking of spatial and textual features of web documents[C]//International Conference on Database and Expert Systems Applications. Berlin:Springer, 2010:450-466.
[6] QADER M A, CHENG S, HRISTIDIS V. A comparative study of secondary indexing techniques in LSM-based NoSQL databases[C]//Proceedings of the 2018 International Conference on Management of Data. ACM, 2018:551-566.
[7] TAN W, TATA S, TANG Y, et al. Diff-Index:Differentiated index in distributed log-structured data stores[C]//EDBT. 2014:700-711.
[8] DSILVA J V, RUIZCARRILLO R, YU C, et al. Secondary indexing techniques for key-value stores:Two rings to rule them all[C]//Proceedings of the 20th International Conference on Extending Database Technology and 20th International Conference on Database Theory 2017. 2017:21-24.
文章导航

/