Nested b-tree : efficient indexing method for fast insertions with asymptotically optimal query time

Abstract

With the prevalence of online platforms such as social media, data is generated and accessed with a rapid rate. It is important to design a database management system that is capable of handling high-volume data insertion amd providing answers to queries efficiently. In this thesis, we introduce Nested B-trees (NB-trees), a data structure that could handle high-volume data insertion with a high insertion rate, and could provide a query performance guarantee which is similar to that of B-trees such that the query performance is asymptotically optimal. Nested B-trees can support insertions at rates higher than LSM-trees, the state-of-the-art data structure for high insertion rate workloads, while improving on their query performance and approaching the query performance of B-trees when complemented with Bloom filters. In our experiments, NB-trees could perform queries at least twice as fast as bLSM and LevelDB commonly, used LSM-tree data stores, while also outperforming them in terms of insertion rate, and performing insertions with much lower delays.

Date of Award	2019
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology