1<!--$Id: select.so,v 10.25 2001/03/31 17:06:27 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: Selecting an access method</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="../am_conf/intro.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/logrec.html"><img src="../../images/next.gif" alt="Next"></a> 15</td></tr></table> 16<p align=center><b>Selecting an access method</b></p> 17<p>The Berkeley DB access method implementation unavoidably interacts with each 18application's data set, locking requirements and data access patterns. 19For this reason, one access method may result in dramatically better 20performance for an application than another one. Applications whose data 21could be stored using more than one access method may want to benchmark 22their performance using the different candidates.</p> 23<p>One of the strengths of Berkeley DB is that it provides multiple access methods 24with nearly identical interfaces to the different access methods. This 25means that it is simple to modify an application to use a different access 26method. Applications can easily benchmark the different Berkeley DB access 27methods against each other for their particular data set and access pattern.</p> 28<p>Most applications choose between using the Btree or Hash access methods 29or between using the Queue and Recno access methods, because each of the 30two pairs offer similar functionality.</p> 31<b>Hash or Btree?</b> 32<p>The Hash and Btree access methods should be used when logical record 33numbers are not the primary key used for data access. (If logical record 34numbers are a secondary key used for data access, the Btree access method 35is a possible choice, as it supports simultaneous access by a key and a 36record number.)</p> 37<p>Keys in Btrees are stored in sorted order and the relationship between 38them is defined by that sort order. For this reason, the Btree access 39method should be used when there is any locality of reference among keys. 40Locality of reference means that accessing one particular key in the 41Btree implies that the application is more likely to access keys near to 42the key being accessed, where "near" is defined by the sort order. For 43example, if keys are timestamps, and it is likely that a request for an 448AM timestamp will be followed by a request for a 9AM timestamp, the 45Btree access method is generally the right choice. Or, for example, if 46the keys are names, and the application will want to review all entries 47with the same last name, the Btree access method is again a good choice.</p> 48<p>There is little difference in performance between the Hash and Btree 49access methods on small data sets, where all, or most of, the data set 50fits into the cache. However, when a data set is large enough that 51significant numbers of data pages no longer fit into the cache, then 52the Btree locality of reference described previously becomes important 53for performance reasons. For example, there is no locality of reference 54for the Hash access method, and so key "AAAAA" is as likely to be stored 55on the same database page with key "ZZZZZ" as with key "AAAAB". In the 56Btree access method, because items are sorted, key "AAAAA" is far more 57likely to be near key "AAAAB" than key "ZZZZZ". So, if the application 58exhibits locality of reference in its data requests, then the Btree page 59read into the cache to satisfy a request for key "AAAAA" is much more 60likely to be useful to satisfy subsequent requests from the application 61than the Hash page read into the cache to satisfy the same request. 62This means that for applications with locality of reference, the cache 63is generally much more effective for the Btree access method than the 64Hash access method, and the Btree access method will make many fewer 65I/O calls.</p> 66<p>However, when a data set becomes even larger, the Hash access method can 67outperform the Btree access method. The reason for this is that Btrees 68contain more metadata pages than Hash databases. The data set can grow 69so large that metadata pages begin to dominate the cache for the Btree 70access method. If this happens, the Btree can be forced to do an I/O 71for each data request because the probability that any particular data 72page is already in the cache becomes quite small. Because the Hash access 73method has fewer metadata pages, its cache stays "hotter" longer in the 74presence of large data sets. In addition, once the data set is so large 75that both the Btree and Hash access methods are almost certainly doing 76an I/O for each random data request, the fact that Hash does not have to 77walk several internal pages as part of a key search becomes a performance 78advantage for the Hash access method as well.</p> 79<p>Application data access patterns strongly affect all of these behaviors, 80for example, accessing the data by walking a cursor through the database 81will greatly mitigate the large data set behavior describe above because 82each I/O into the cache will satisfy a fairly large number of subsequent 83data requests.</p> 84<p>In the absence of information on application data and data access 85patterns, for small data sets either the Btree or Hash access methods 86will suffice. For data sets larger than the cache, we normally recommend 87using the Btree access method. If you have truly large data, then the 88Hash access method may be a better choice. The <a href="../../utility/db_stat.html">db_stat</a> utility 89is a useful tool for monitoring how well your cache is performing.</p> 90<b>Queue or Recno?</b> 91<p>The Queue or Recno access methods should be used when logical record 92numbers are the primary key used for data access. The advantage of the 93Queue access method is that it performs record level locking and for this 94reason supports significantly higher levels of concurrency than the Recno 95access method. The advantage of the Recno access method is that it 96supports a number of additional features beyond those supported by the 97Queue access method, such as variable-length records and support for 98backing flat-text files.</p> 99<p>Logical record numbers can be mutable or fixed: mutable, where logical 100record numbers can change as records are deleted or inserted, and fixed, 101where record numbers never change regardless of the database operation. 102It is possible to store and retrieve records based on logical record 103numbers in the Btree access method. However, those record numbers are 104always mutable, and as records are deleted or inserted, the logical record 105number for other records in the database will change. The Queue access 106method always runs in fixed mode, and logical record numbers never change 107regardless of the database operation. The Recno access method can be 108configured to run in either mutable or fixed mode.</p> 109<p>In addition, the Recno access method provides support for databases whose 110permanent storage is a flat text file and the database is used as a fast, 111temporary storage area while the data is being read or modified.</p> 112<table width="100%"><tr><td><br></td><td align=right><a href="../am_conf/intro.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/logrec.html"><img src="../../images/next.gif" alt="Next"></a> 113</td></tr></table> 114<p><font size=1>Copyright (c) 1996,2008 Oracle. All rights reserved.</font> 115</body> 116</html> 117
