A Verified Implementation of B+-Trees in Isabelle/HOL

08/18/2022
by   Niels Mündler, et al.
0

In this paper we present the verification of an imperative implementation of the ubiquitous B+-tree data structure in the interactive theorem prover Isabelle/HOL. The implementation supports membership test, insertion and range queries with efficient binary search for intra-node navigation. The imperative implementation is verified in two steps: an abstract set interface is refined to an executable but inefficient purely functional implementation which is further refined to the efficient imperative implementation.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset