Recoverable B±trees in Centralized Database Management Systems
Ibrahim Jaluta, Eljas Soisalon-Soininen · 2015
Abstract: The B±tree is the most widely used index structure in the current commercial database systems. This paper introduces new B±tree algorithms in which tree-structure modifications such as page splits or merges are executed as atomic actions. A B±tree structure modification, once executed to completion will never be undone no matter if the transaction that triggered such a structure modification commits or aborts later on. In restart recovery from a system crash, the redo pass of the recovery algorithm will always produce a structurally consistent B±tree, on which undo operations by backward-rolling transactions can be performed. A database transaction can contain any number of operations of the form “fetch the first (or next) matching record”, “insert a record”, or “delete a record”, where database records are identified by their primary keys. Repeatable-read-level isolation for transactions is achieved by key-range locking.