Research On NoSQL Database Index Based On LSM Tree

With the development of Internet and the popularity of the Mobile Internet, the Internet has almost penetrated into every aspect of our lives. The amount of data generated by us is much faster than ever before. We are stepping into an era of big data. The feature of big data is not only reflected in the volumn of data, but also in the variety and the velocity of data. How to store and use these data effectively has become a difficult problem in the era of big data. Traditional relational database can not provide services for such a large amout of data. At the same time, an entire different database is on the rise. This kind of database system is called non-relational databases, namely NoSQL database. NoSQL database has developed rapidly in recent years, and it provides a very different solution for storing data.Index is one of the most important issues in NoSQL database and B-tree is the most common used index structure. Relational databases adopt B+tree as its index structure. However, not like relational database, No SQL database offers many different data organization patterns. Therefore, the traditional indexing methods have been unable to meet the requirements of NoSQL index.In this paper, we analysed the present situation and features of NoSQL databases and design a new index scheme for NoSQL database. We investigated the common index structure and analyse the advantages and disadvantages of different index structures and then choose LSM-tree as research target. LSM-tree improves writing throughput, but sacrifices reading performance especially for range query. We proposed an indexed LSM-tree(iLSM-tree) mainly to improve the reading performance by adding an extra index to LSM-tree. To evaluate its performance, we implemented iLSM-tree on HBase and performed a serial of comparison with original HBase which uses LSM-tree. The results demonstrated that iLSM-tree is more efficient.