<!--$Id: intro.html,v 1.2 2004/03/30 01:22:41 jtownsen Exp $--> <!--Copyright 1997-2003 by Sleepycat Software, Inc.--> <!--All rights reserved.--> <!--See the file LICENSE for redistribution information.--> <html> <head> <title>Berkeley DB Reference Guide: What are the available access methods?</title> <meta name="description" content="Berkeley DB: An embedded database programmatic toolkit."> <meta name="keywords" content="embedded,database,programmatic,toolkit,b+tree,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,Java,C,C++"> </head> <body bgcolor=white> <a name="2"><!--meow--></a> <table width="100%"><tr valign=top> <td><h3><dl><dt>Berkeley DB Reference Guide:<dd>Access Methods</dl></h3></td> <td align=right><a href="../simple_tut/close.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../toc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../am_conf/select.html"><img src="../../images/next.gif" alt="Next"></a> </td></tr></table> <p> <h3 align=center>What are the available access methods?</h3> <p>Berkeley DB currently offers four access methods: Btree, Hash, Queue and Recno.</p> <h3>Btree</h3> <p>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.</p> <h3>Hash</h3> <p>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, <i>Proceedings of the 6th International Conference on Very Large Databases (VLDB)</i>, 1980.</p> <h3>Queue</h3> <p>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.</p> <h3>Recno</h3> <p>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.</p> <table width="100%"><tr><td><br></td><td align=right><a href="../simple_tut/close.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../toc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../am_conf/select.html"><img src="../../images/next.gif" alt="Next"></a> </td></tr></table> <p><font size=1><a href="../../sleepycat/legal.html">Copyright (c) 1996-2003</a> <a href="http://www.sleepycat.com">Sleepycat Software, Inc.</a> - All rights reserved.</font> </body> </html>