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