A theory of transactions on recoverable search trees

We consider transactions running on a database that consists of records with unique totally-ordered keys and is organized as a sparse primary search tree such as a B-tree index on disk storage. We extend the classical read-write model of transactions by considering inserts, deletes and key-range scans and by distinguishing between four types of transaction states: forward-rolling, committed, backward-rolling, and rolled- back transactions. A search-tree transaction is modelled as a two-level transaction containing structure modifications as open nested subtransactions that can commit even though the parent transaction aborts. Isolation conditions are defined for search-tree transactions with nested structure modifications that guarantee the structural consistency of the search tree, a required isolation level (including phantom prevention) for database operations, and recoverability for structure modifications and database operations.