Chapter 2. Access Method Configuration
Prev |  | Next

## Chapter 2. Access Method Configuration

## What are the available access methods?

Berkeley DB currently offers four access methods: Btree, Hash, 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.

### 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.

Prev |  | Next
The Berkeley DB products | Home | Selecting an access method