Chapter 2.  Access Method Configuration

Table of Contents

What are the available access methods?
Btree
Hash
Heap
Queue
Recno
Selecting an access method
Btree or Heap?
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
Compression
Hash access method specific configuration
Page fill factor
Specifying a database hash
Hash table size
Heap access method specific configuration
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 five access methods: Btree, Hash, Heap, Queue and Recno.

Btree

The Btree access method is an implementation of a sorted, balanced tree structure. Searches, insertions, and deletions in the tree all take O(height) time, where height is the number of levels in the Btree from the root to the leaf pages. The upper bound on the height is log base_b N, where base_b is the smallest number of keys on a page, and N is the total number of keys stored.

Inserting unordered data into a Btree can result in pages that are only half-full. DB makes ordered (or inverse ordered) insertion the best case, resulting in nearly full-page space utilization.

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.

Heap

The Heap access method stores records in a heap file. Records are referenced solely by the page and offset at which they are written. Because records are written in a heap file, compaction is not necessary when deleting records, which allows for more efficient use of space than if Btree is in use. The Heap access method is intended for platforms with constrained disk space, especially if those systems are performing a great many record creation and deletions.

Queue

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.

Recno

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.