upscaledb has a unique implementation for ACID transactions. Each database is stored in a B-Tree. If transactions are enabled, an additional "transaction tree" is generated. This tree structure is stored in RAM and contains the transactional modifications and updates of a database. Whenever a transaction is committed, its updates are merged with the persistent B-Tree. Whenever a transaction is aborted, its RAM structures are simply discarded.
Since the RAM structures are volatile, the transactions are logged in a journal file. In case of recovery, i.e. after a system crash, the RAM structures are simply recreated from the journal. Non-committed transactions are ignored, committed transactions are re-applied and merged with the B-Tree. This design really simplifies the implementation of the B-Tree, which only stores committed items. It does not require complex logic to serialize transactions, for undoing partially committed Transactions etc.
Similar to an AUTO_INCREMENT column in an SQL
database, record-number databases automatically assign
unique numerical keys to inserted records.
Common use cases are unique user IDs for newly signed up users, unique order IDs for incoming orders etc.
Record-Number keys can be of 32bit or 64bit. The 32bit keys can be compressed.
The sample db4.c reads words from stdin and stores each word with record-number keys, then prints each word in its original order.
Duplicate keys are used to model 1:n relationships, i.e. of customers and their orders (1 customer can have n orders) or to count occurrences of a key.
The duplicates are managed in the RecordList of the B-Tree node. If a key has only few duplicates then all the associated records are stored in the B-Tree leaf. Otherwise a blob is allocated which stores a list of all the records.
Cursors can be used to traverse all associated records of a key, or to retrieve the number of duplicates of a key. The sample db5.c reads words from stdin and stores the line number of each occurrence, then prints the words in alphabetical order.