← Back to branch summary

~ubuntu-branches/ubuntu/precise/rpm/precise-proposed

« back to all changes in this revision

Viewing changes to db/docs/ref/am_conf/select.html

  • Committer: Bazaar Package Importer
  • Author(s): Michael Vogt
  • Date: 2009-06-25 18:57:20 UTC
  • mfrom: (1.1.5 upstream) (4.1.2 sid)
  • Revision ID: james.westby@ubuntu.com-20090625185720-617sjskgtgmf09vf
Tags: 4.7.0-7ubuntu1
* Merge from debian unstable, remaining changes:
  - change build depends from libdwarf-dev -> libdw-dev
    (libdwarf-dev is in universe)

Show diffs side-by-side

added added

removed removed

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