Table of Contents
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.