1<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml">
4  <head>
5    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
6    <title>Access Methods</title>
7    <link rel="stylesheet" href="gettingStarted.css" type="text/css" />
8    <meta name="generator" content="DocBook XSL Stylesheets V1.73.2" />
9    <link rel="start" href="index.html" title="Getting Started with Berkeley DB" />
10    <link rel="up" href="introduction.html" title="Chapter��1.��Introduction to Berkeley DB" />
11    <link rel="prev" href="concepts.html" title="Berkeley DB Concepts" />
12    <link rel="next" href="databaseLimits.html" title="Database Limits and Portability" />
13  </head>
14  <body>
15    <div class="navheader">
16      <table width="100%" summary="Navigation header">
17        <tr>
18          <th colspan="3" align="center">Access Methods</th>
19        </tr>
20        <tr>
21          <td width="20%" align="left"><a accesskey="p" href="concepts.html">Prev</a>��</td>
22          <th width="60%" align="center">Chapter��1.��Introduction to Berkeley DB </th>
23          <td width="20%" align="right">��<a accesskey="n" href="databaseLimits.html">Next</a></td>
24        </tr>
25      </table>
26      <hr />
27    </div>
28    <div class="sect1" lang="en" xml:lang="en">
29      <div class="titlepage">
30        <div>
31          <div>
32            <h2 class="title" style="clear: both"><a id="accessmethods"></a>Access Methods</h2>
33          </div>
34        </div>
35      </div>
36      <div class="toc">
37        <dl>
38          <dt>
39            <span class="sect2">
40              <a href="accessmethods.html#selectAM">Selecting Access Methods</a>
41            </span>
42          </dt>
43          <dt>
44            <span class="sect2">
45              <a href="accessmethods.html#BTreeVSHash">Choosing between BTree and Hash</a>
46            </span>
47          </dt>
48          <dt>
49            <span class="sect2">
50              <a href="accessmethods.html#QueueVSRecno">Choosing between Queue and Recno</a>
51            </span>
52          </dt>
53        </dl>
54      </div>
55      <p>
56        While this manual will focus primarily on the BTree access method, it is
57        still useful to briefly describe all of the access methods that DB
58        makes available.
59    </p>
60      <p>
61        Note that an access method can be selected only when the database is
62        created. Once selected,  actual API usage is generally
63        identical across all access methods. That is, while some 
64        exceptions exist, mechanically you interact with the library in the same
65        way regardless of which access method you have selected.
66    </p>
67      <p>
68        The access method that you should choose is gated first by what you want
69        to use as a key, and then secondly by the performance that you see
70        for a given access method. 
71    </p>
72      <p>
73        The following are the available access methods:
74    </p>
75      <div class="informaltable">
76        <table border="1" width="80%">
77          <colgroup>
78            <col align="left" />
79            <col align="left" />
80          </colgroup>
81          <thead>
82            <tr>
83              <th align="center">Access Method</th>
84              <th align="center">Description</th>
85            </tr>
86          </thead>
87          <tbody>
88            <tr>
89              <td align="left">BTree</td>
90              <td align="left" valign="top">
91                <p>
92                    Data is stored in a sorted, balanced tree structure. 
93                    Both the key and the data for BTree records can be
94                    arbitrarily complex. That is, they can contain single values
95                    such as an integer or a string, or complex types such as a
96                    structure. Also, although not the default
97                    behavior, it is possible for two records to
98                    use keys that compare as equals. When this occurs, the
99                    records are considered to be duplicates of one another.
100                </p>
101            </td>
102            </tr>
103            <tr>
104              <td align="left">Hash</td>
105              <td align="left" valign="top">
106                <p>
107                    Data is stored in an extended linear hash table.  Like
108                    BTree, the key and the data used for Hash records can be of
109                    arbitrarily complex data.  Also, like BTree, duplicate
110                    records are optionally supported.
111                </p>
112            </td>
113            </tr>
114            <tr>
115              <td align="left">Queue</td>
116              <td align="left" valign="top">
117                <p>
118                    Data is stored in a queue as fixed-length records. Each
119                    record uses a logical record number as its key. This access
120                    method is designed for fast inserts at the tail of the
121                    queue, and it has a special operation that deletes and
122                    returns a record from the head of the queue.
123                </p>
124                <p>
125                    This access method is unusual in that it provides record
126                    level locking. This can provide
127                    beneficial performance improvements in applications
128                    requiring concurrent access to the queue.
129                </p>
130            </td>
131            </tr>
132            <tr>
133              <td align="left">Recno</td>
134              <td align="left" valign="top">
135                <p>
136                    Data is stored in either fixed or variable-length records.
137                    Like Queue, Recno records use logical record numbers as keys.
138                </p>
139            </td>
140            </tr>
141          </tbody>
142        </table>
143      </div>
144      <div class="sect2" lang="en" xml:lang="en">
145        <div class="titlepage">
146          <div>
147            <div>
148              <h3 class="title"><a id="selectAM"></a>Selecting Access Methods</h3>
149            </div>
150          </div>
151        </div>
152        <p>
153            To select an access method, you should first consider what you want
154            to use as a key for you database records. If you want to use
155            arbitrary data (even strings), then you should use either BTree or
156            Hash. If you want to use logical record numbers (essentially
157            integers) then you should use Queue or Recno.
158        </p>
159        <p>
160            Once you have made this decision, you must choose between either
161            BTree or Hash, or Queue or Recno. This decision is described next.
162        </p>
163      </div>
164      <div class="sect2" lang="en" xml:lang="en">
165        <div class="titlepage">
166          <div>
167            <div>
168              <h3 class="title"><a id="BTreeVSHash"></a>Choosing between BTree and Hash</h3>
169            </div>
170          </div>
171        </div>
172        <p>
173            For small working datasets that fit entirely in memory, there is no
174            difference between BTree and Hash. Both will perform just as well
175            as the other. In this situation, you might just as well use BTree,
176            if for no other reason than the majority of DB applications use
177            BTree.
178         </p>
179        <p>
180            Note that the main concern here is your
181            working dataset, not your entire dataset. Many applications maintain
182            large amounts of information but only need to access some small
183            portion of that data with any frequency. So what you want to
184            consider is the data that you will routinely use, not the sum total
185            of all the data managed by your application.
186         </p>
187        <p>
188            However, as your working dataset grows to the point
189            where you cannot fit it all into memory, then you need to take more
190            care when choosing your access method. Specifically, choose:
191        </p>
192        <div class="itemizedlist">
193          <ul type="disc">
194            <li>
195              <p>
196                    BTree if your keys have some locality of reference. That is,
197                    if they sort well and you can expect that a query for a
198                    given key will likely be followed by a query for one of its
199                    neighbors. 
200                </p>
201            </li>
202            <li>
203              <p>
204                    Hash if your dataset is extremely large. For any given
205                    access method, DB must maintain a certain amount of internal
206                    information. However, the amount of information that DB
207                    must maintain for BTree is much greater than for Hash. The
208                    result is that as your dataset grows, this internal
209                    information can dominate the cache to the point where there
210                    is relatively little space left for application data. 
211                    As a result, BTree can be forced to perform disk I/O much more
212                    frequently than would Hash given the same amount of data. 
213                </p>
214              <p>
215                    Moreover, if your dataset becomes so large that DB will
216                    almost certainly have to perform disk I/O to satisfy a
217                    random request, then Hash will definitely out perform BTree
218                    because it has fewer internal records to search through than
219                    does BTree.
220                </p>
221            </li>
222          </ul>
223        </div>
224      </div>
225      <div class="sect2" lang="en" xml:lang="en">
226        <div class="titlepage">
227          <div>
228            <div>
229              <h3 class="title"><a id="QueueVSRecno"></a>Choosing between Queue and Recno</h3>
230            </div>
231          </div>
232        </div>
233        <p>
234            Queue or Recno are used when the application wants to use logical
235            record numbers for the primary database key. Logical record numbers
236            are essentially integers that uniquely identify the database
237            record. They can be either mutable or fixed, where a mutable record
238            number is one that might change as database records are stored or
239            deleted. Fixed logical record numbers never change regardless of
240            what database operations are performed.
241        </p>
242        <p>
243            When deciding between Queue and Recno, choose:
244        </p>
245        <div class="itemizedlist">
246          <ul type="disc">
247            <li>
248              <p>
249                    Queue if your application requires high degrees of
250                    concurrency. Queue provides record-level locking (as opposed
251                    to the page-level locking that the other access methods
252                    use), and this can result in significantly faster throughput
253                    for highly concurrent applications.
254                </p>
255              <p>
256                    Note, however, that Queue provides support only for fixed
257                    length records. So if the size of the data that you want to
258                    store varies widely from record to record, you should
259                    probably choose an access method other than Queue.
260                </p>
261            </li>
262            <li>
263              <p>
264                    Recno if you want mutable record numbers. Queue is only
265                    capable of providing fixed record numbers. Also, Recno
266                    provides support for databases whose permanent storage is a
267                    flat text file. This is useful for applications looking for
268                    fast, temporary storage while the data is being read or
269                    modified.
270                </p>
271            </li>
272          </ul>
273        </div>
274      </div>
275    </div>
276    <div class="navfooter">
277      <hr />
278      <table width="100%" summary="Navigation footer">
279        <tr>
280          <td width="40%" align="left"><a accesskey="p" href="concepts.html">Prev</a>��</td>
281          <td width="20%" align="center">
282            <a accesskey="u" href="introduction.html">Up</a>
283          </td>
284          <td width="40%" align="right">��<a accesskey="n" href="databaseLimits.html">Next</a></td>
285        </tr>
286        <tr>
287          <td width="40%" align="left" valign="top">Berkeley DB Concepts��</td>
288          <td width="20%" align="center">
289            <a accesskey="h" href="index.html">Home</a>
290          </td>
291          <td width="40%" align="right" valign="top">��Database Limits and Portability</td>
292        </tr>
293      </table>
294    </div>
295  </body>
296</html>
297