Banca de DEFESA: JOÃO VITOR VENCESLAU COELHO

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
STUDENT : JOÃO VITOR VENCESLAU COELHO
DATE: 06/07/2026
TIME: 14:00
LOCAL: Google meet
TITLE:

Concurrent B+-tree for managing disjoint intervals

KEY WORDS:

Virtual Memory Areas (VMAs); B+ Tree; Rust; Micro-architectural Performance; Relaxed Algorithm; Disjoint Interval Management.

PAGES: 65
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUBÁREA: Sistemas de Computação
SUMMARY:

Efficient management of disjoint intervals, particularly virtual memory areas (VMAs), is a bottleneck in operating system performance due to the poor cache locality of traditional binary trees. While modern structures like the Maple Tree address this, they introduce significant complexity, deep kernel coupling, and possible memory safety risks. This paper proposes a memory-safe, modular B+ Tree variant implemented in Rust, designed to decouple interval management from kernel internals. We introduce a ''relaxed'' removal algorithm that amortizes rebalancing costs to optimize write-heavy workloads. Extensive evaluation using both synthetic benchmarks and real-world execution traces from the Firefox browser demonstrates that our approach significantly outperforms a traditional AVL-based Interval Tree and is competitive with a userspace Maple Tree. Micro-architectural analysis reveals that the B+ Tree design reduces last level cache (LLC) misses and system bus traffic, directly translating to lower CPU cycle consumption. These results validate that strict memory safety and architectural modularity can be achieved without compromising the low-latency requirements of system software.

COMMITTEE MEMBERS:
Presidente - 1673543 - SAMUEL XAVIER DE SOUZA
Interno - 2579664 - ALLAN DE MEDEIROS MARTINS
Externo à Instituição - Pedro Henrique de Mello Morado Penna