1<!--$Id: intro.so,v 10.25 2004/09/17 19:51:50 bostic Exp $--> 2<!--Copyright (c) 1997,2008 Oracle. All rights reserved.--> 3<!--See the file LICENSE for redistribution information.--> 4<html> 5<head> 6<title>Berkeley DB Reference Guide: What are the available access methods?</title> 7<meta name="description" content="Berkeley DB: An embedded database programmatic toolkit."> 8<meta name="keywords" content="embedded,database,programmatic,toolkit,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,Java,C,C++"> 9</head> 10<body bgcolor=white> 11<a name="2"><!--meow--></a> 12<table width="100%"><tr valign=top> 13<td><b><dl><dt>Berkeley DB Reference Guide:<dd>Access Methods</dl></b></td> 14<td align=right><a href="/intro/products.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> 15</td></tr></table> 16<p align=center><b>What are the available access methods?</b></p> 17<p>Berkeley DB currently offers four access methods: Btree, Hash, Queue and Recno.</p> 18<b>Btree</b> 19<p>The Btree access method is an implementation of a sorted, balanced tree 20structure. Searches, insertions, and deletions in the tree all take O(log 21base_b N) time, where base_b is the average number of keys per page, and 22N is the total number of keys stored. Often, inserting ordered data into 23Btree implementations results in pages that are only half-full. Berkeley DB 24makes ordered (or inverse ordered) insertion the best case, resulting in 25nearly full-page space utilization.</p> 26<b>Hash</b> 27<p>The Hash access method data structure is an implementation of Extended 28Linear Hashing, as described in "Linear Hashing: A New Tool for File and 29Table Addressing", Witold Litwin, <i>Proceedings of the 6th 30International Conference on Very Large Databases (VLDB)</i>, 1980.</p> 31<b>Queue</b> 32<p>The Queue access method stores fixed-length records with logical record 33numbers as keys. It is designed for fast inserts at the tail and has a 34special cursor consume operation that deletes and returns a record from 35the head of the queue. The Queue access method uses record level locking.</p> 36<b>Recno</b> 37<p>The Recno access method stores both fixed and variable-length records with 38logical record numbers as keys, optionally backed by a flat text (byte 39stream) file.</p> 40<table width="100%"><tr><td><br></td><td align=right><a href="/intro/products.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> 41</td></tr></table> 42<p><font size=1>Copyright (c) 1996,2008 Oracle. All rights reserved.</font> 43</body> 44</html> 45