head 1.2; access; symbols RPM_4_2_1:1.1.1.5 RPM_4_2:1.1.1.5 RPM_4_1_1:1.1.1.5 RPM_4_1:1.1.1.4 RPM_4_0_5:1.1.1.3 RPM_4_0_4:1.1.1.2 RPM_4_0_3:1.1.1.1 RPM:1.1.1; locks; strict; comment @# @; 1.2 date 2008.01.02.09.54.42; author rse; state dead; branches; next 1.1; commitid z4cpSiAhOCXk5PLs; 1.1 date 2001.07.23.20.45.37; author rse; state Exp; branches 1.1.1.1; next ; 1.1.1.1 date 2001.07.23.20.45.37; author rse; state Exp; branches; next 1.1.1.2; 1.1.1.2 date 2002.01.08.00.30.11; author rse; state Exp; branches; next 1.1.1.3; 1.1.1.3 date 2003.01.18.13.49.01; author rse; state Exp; branches; next 1.1.1.4; 1.1.1.4 date 2001.10.15.03.47.33; author rse; state Exp; branches; next 1.1.1.5; 1.1.1.5 date 2003.01.18.14.04.59; author rse; state Exp; branches; next ; desc @@ 1.2 log @remove the ancient RPM 4.2.1 source tree copy @ text @ Berkeley DB Reference Guide: What are the available access methods?

Berkeley DB Reference Guide:
Access Methods

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

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.