We present an indexing system where a database index is divided into two parts: the main index located on disk and the differential index in the main memory. Both indices are implemented as B-trees. All updates performed by active transactions are written in the differential index. Periodically, writes of committed transactions are transferred from differential index to the main index as a batch-update operation. Thus, updates falling into the same leaf of the tree can be performed simultaneously. In addition, the system offers a simple recovery scheme. After a system crash, no undo operations are needed and redo operations need only write to the main memory.
['Kerttu Pollari-Malmi', 'Jarmo Ruuth', 'Eljas Soisalon-Soininen']
Concurrency control for B-trees with differential indices