Berkeley DB Reference Guide: Access Methods
What are the available access methods?
Berkeley DB currently offers three access methods: Btree, Hash and Recno.
Btree
The Btree access method is an implementation of a sorted, balanced tree structure, more specifically a B+tree. Searches, insertions, and deletions in the tree all take O(log base_b N) time, where base_b is the average number of keys per page, and N is the total number of keys stored. Often, inserting ordered data into btree implementations results in pages that are half-full. This implementation has been modified to make ordered (or inverse ordered) insertion the best case, resulting in nearly perfect page space utilization.
Space freed by deleting key/data pairs from a Btree database is never reclaimed from the filesystem, although it is reused where possible. This means that the Btree storage structure is grow-only. If sufficiently many keys are deleted from a tree that shrinking the underlying database file is desirable, this can be accomplished by creating a new tree from a scan of the existing one.
Hash
The Hash access method data structure is an implementation of Extended Linear Hashing, as described in Linear Hashing: A New Tool for File and Table Addressing, Witold Litwin, Proceedings of the 6th International Conference on Very Large Databases (VLDB), 1980.
Recno
The Recno access method is an implementation of Fixed and Variable-length records, optionally backed by a flat text (byte stream) file. Both fixed and variable length records are accessed by their logical record number.
It is valid to create a record whose record number is more than one greater than the last record currently in the database. For example, the creation of record number 8, when records 6 and 7 do not yet exist, is not an error. However, any attempt to retrieve such records (e.g., records 6 and 7) will fail.
By default, deleting a record will not renumber records following the deleted record. Any attempt to retrieve deleted records will fail.
