基于LSM Tree的分布式索引实现

近年来Log-Structured-Merge(LSM)Tree在NoSQL系统中得到了广泛地应用.主要是因为LSM Tree架构提出了延迟更新和批量写入的算法,将随机写转换为批量写,减少了磁盘臂的移动开销,从而大大地提升了数据库的写入性能.然而,读性能却也因此受到影响.LSM Tree和B Tree之间的本质区别使得NoSQL系统不适宜直接引用B Tree作为辅助索引结构.本文实现了LSM Tree下的一种分布式辅助索引结构,提出针对这种读写分离架构的索引批量加载策略,并对LSM Tree的查询计划树进行了缓冲优化,避免了重复的查询解析,使得索引读的性能得到了相应的提升.

面向空间数据的LSM树索引研究综述

空间数据在城市规划、天气预报、资产管理以及路线导航上有着广泛的应用。传统的关系型数据库不能满足空间数据高频存取的需求,面向空间数据的LSM树索引能够提高空间数据的写入和查询性能。但在索引设计中,需要面临索引结构设计、提升查询性能和降低更新开销三方面问题。对此,本文分别对基于空间填充曲线的LSM树索引结构和基于树状结构的LSM树索引结构两方面的现有工作进行分析,比较其优缺点,并展望了该方向的机遇和挑战。

基于日志结构合并树的轻量级分布式索引实现方法

针对现有基于日志结构合并树(LSM-Tree)实现的分布式数据库仅支持高效的主键查询,无法让用户快速地应用在自己的集群中的问题,提出了基于LSM-Tree的轻量级分布式索引实现方法 SIBL。首先,通过对主键属性列建立索引来提高非主键属性的查询效率;然后,提出了分布式索引构建算法以及基于等距取样的索引区间划分算法,从而保证了索引在系统中的均匀分布,并且优化了传统索引的查询算法,将索引文件看作特殊的数据文件分布式地存储在系统中,从而保证了系统的负载均衡和可扩展性;最后,将该方法与华为二级索引方案HIndex在HBase数据库上进行实验来比较二者的索引构建的时间和空间开销、索引的查询性能和系统的负载均衡等性能,验证得出所提出的方法使查询性能提升了50~200倍。

日志结构合并树的查询优化技术

针对基于日志结构合并树(Log Structured Merge Tree, LSM-tree)的数据库查询性能较差的问题,目前的研究工作主要集中在利用索引和缓存技术提升LSM-tree的查询性能.本文主要从以下几个方面对LSM-tree的查询优化技术进行了综述.第一,介绍了LSM-tree的基础架构,分析了影响查询的因素.第二,分析了当前的LSM-tree查询优化技术,包括索引优化技术和缓存优化技术.第三,分析了索引和缓存技术是如何提升基于LSM-tree的数据库查询性能的,并总结了一些现有的研究工作.最后,总结并给出了未来可能的研究方法.