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 c...[ Read more ]

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.