Title: Second order B+-trees


Abstract:
In this talk I will introduce Second Order B+-trees, a structure that
improves the performance of B+-tree page operations for large page
sizes. We achieve this by organizing the contents of each B+-tree page
as a B+-tree too. While such solutions have been proposed before, our
approach is novel in that an in-page B+-tree (i) has a fixed number of
branches that are always full and completely lack child pointers, and
(ii) it has a fixed number of leaves that are always present, are
never split or merged and can never be empty. Thus, our structure
largely deviates from traditional B+-trees and best fits the
characteristics of the in-memory, fixed-size storage space at hand.
Additionally, it has been designed with modern cache memory
hierarchies in mind, and takes full advantage of their performance
characteristics.

During the talk I will describe the structure and the algorithms for
maintaining it. I will also present experiments that demonstrate that
our approach maintains almost constant performance characteristics
across a wide range of page sizes, outperforming traditional B+-trees
and also surpassing similar, competing approaches.Second order
B+-trees


Abstract:
In this talk I will introduce Second Order B+-trees, a structure that
improves the performance of B+-tree page operations for large page
sizes. We achieve this by organizing the contents of each B+-tree page
as a B+-tree too. While such solutions have been proposed before, our
approach is novel in that an in-page B+-tree (i) has a fixed number of
branches that are always full and completely lack child pointers, and
(ii) it has a fixed number of leaves that are always present, are
never split or merged and can never be empty. Thus, our structure
largely deviates from traditional B+-trees and best fits the
characteristics of the in-memory, fixed-size storage space at hand.
Additionally, it has been designed with modern cache memory
hierarchies in mind, and takes full advantage of their performance
characteristics.

During the talk I will describe the structure and the algorithms for
maintaining it. I will also present experiments that demonstrate that
our approach maintains almost constant performance characteristics
across a wide range of page sizes, outperforming traditional B+-trees
and also surpassing similar, competing approaches.