,I:Berkeley DB Reference Guide: Access Methods[P4

Berkeley DB Reference Guide: Access Methods



<

What are the available access methods?



IBerkeley DB currently offers three access methods: Btree, Hash and Recno.

Btree



GThe Btree access method is an implementation of a sorted, balanced treeAstructure, more specifically a B+tree. Searches, insertions, andHdeletions in the tree all take O(log base_b N) time, where base_b is theJaverage number of keys per page, and N is the total number of keys stored.IOften, inserting ordered data into btree implementations results in pagesJthat are half-full. This implementation has been modified to make orderedI(or inverse ordered) insertion the best case, resulting in nearly perfectpage space utilization.

ESpace freed by deleting key/data pairs from a Btree database is neverJreclaimed from the filesystem, although it is reused where possible. ThisJmeans that the Btree storage structure is grow-only. If sufficiently manyHkeys are deleted from a tree that shrinking the underlying database fileIis desirable, this can be accomplished by creating a new tree from a scanof the existing one.

Hash



FThe Hash access method data structure is an implementation of ExtendedLinear Hashing, as described in@Linear Hashing: A New Tool for File and Table Addressing,FWitold Litwin, Proceedings of the 6th International Conference on VeryLarge Databases (VLDB), 1980.

Recno



IThe Recno access method is an implementation of Fixed and Variable-lengthIrecords, optionally backed by a flat text (byte stream) file. Both fixedHand variable length records are accessed by their logical record number.

CIt is valid to create a record whose record number is more than oneEgreater than the last record currently in the database. For example,Gthe creation of record number 8, when records 6 and 7 do not yet exist,Fis not an error. However, any attempt to retrieve such records (e.g.,records 6 and 7) will fail.

EBy default, deleting a record will not renumber records following theCdeleted record. Any attempt to retrieve deleted records will fail.

IAHÿÿ