Chapter 2.  Access Method Configuration

Table of Contents

What are the available access methods?
Selecting an access method
Hash or Btree?
Queue or Recno?
Logical record numbers
General access method configuration
Selecting a page size
Selecting a cache size
Selecting a byte order
Duplicate data items
Non-local memory allocation
Btree access method specific configuration
Btree comparison
Btree prefix comparison
Minimum keys per page
Retrieving Btree records by logical record number
Hash access method specific configuration
Page fill factor
Specifying a database hash
Hash table size
Queue and Recno access method specific configuration
Managing record-based databases
Selecting a Queue extent size
Flat-text backing files
Logically renumbering records

What are the available access methods?

Berkeley DB currently offers four access methods: Btree, Hash, Queue and Recno.


The Btree access method is an implementation of a sorted, balanced tree structure. 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 only half-full. Berkeley DB makes ordered (or inverse ordered) insertion the best case, resulting in nearly full-page space utilization.


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.


The Queue access method stores fixed-length records with logical record numbers as keys. It is designed for fast inserts at the tail and has a special cursor consume operation that deletes and returns a record from the head of the queue. The Queue access method uses record level locking.


The Recno access method stores both fixed and variable-length records with logical record numbers as keys, optionally backed by a flat text (byte stream) file.