The Spine: An Efficient Two-level Dynamic B-Tree with Fast Selection
Name
Jennifer Veismann
Abstract
This thesis compares the efficiency of the Rust programming language standard library B-Tree implementation against a simplified alternative, the “Spine”. As the work is highly context-dependent, the thesis also provides an overview of the Rust programming language. As the “Spine” is a two-level B-Tree indexed by a Fenwick tree, an overview of the basic operations of the Fenwick tree is also provided.
The comparison of the different operations of the two data structures reveals that the "Spine" is significantly faster in the select operation than the regular B-Tree, especially for larger data sizes. In the case of other operations, depending on the dataset size, there was not as big a difference as with the select operation.
The comparison of the different operations of the two data structures reveals that the "Spine" is significantly faster in the select operation than the regular B-Tree, especially for larger data sizes. In the case of other operations, depending on the dataset size, there was not as big a difference as with the select operation.
Graduation Thesis language
English
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
Bruno Rucy Carneiro Alves de Lima
Defence year
2024