NESTED B-TREE: EFFICIENT INDEXING METHOD FOR FAST INSERTIONS WITH ASYMPTOTICALLY OPTIMAL QUERY

MPhil Thesis Defence


Title: "NESTED B-TREE: EFFICIENT INDEXING METHOD FOR FAST INSERTIONS WITH 
ASYMPTOTICALLY OPTIMAL QUERY"

By

Mr. Sepanta ZEIGHAMI


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:			Monday, 5 August 2019

Time:			3:00pm - 5:00pm

Venue:			Room 3494
 			Lifts 25/26

Committee Members:	Dr. Raymond Wong (Supervisor)
 			Prof. Andrew Horner (Chairperson)
 			Dr. Sunil Arya


**** ALL are Welcome ****