select.so

berkeley db 4.6.21的源码。berkeley db是一个简单的数据库管理系统

m4_comment([$Id: select.so,v 10.25 2001/03/31 17:06:27 bostic Exp $])

m4_ref_title(Access Methods,
    Selecting an access method,
    selecting an @access method,
    am_conf/intro, am_conf/logrec)

m4_p([dnl
The m4_db access method implementation unavoidably interacts with each
application's data set, locking requirements and data access patterns.
For this reason, one access method may result in dramatically better
performance for an application than another one.  Applications whose data
could be stored using more than one access method may want to benchmark
their performance using the different candidates.])

m4_p([dnl
One of the strengths of m4_db is that it provides multiple access methods
with nearly identical interfaces to the different access methods.  This
means that it is simple to modify an application to use a different access
method.  Applications can easily benchmark the different m4_db access
methods against each other for their particular data set and access pattern.])

m4_p([dnl
Most applications choose between using the Btree or Hash access methods
or between using the Queue and Recno access methods, because each of the
two pairs offer similar functionality.])

m4_section(Hash or Btree?)

m4_p([dnl
The Hash and Btree access methods should be used when logical record
numbers are not the primary key used for data access.  (If logical record
numbers are a secondary key used for data access, the Btree access method
is a possible choice, as it supports simultaneous access by a key and a
record number.)])

m4_p([dnl
Keys in Btrees are stored in sorted order and the relationship between
them is defined by that sort order.  For this reason, the Btree access
method should be used when there is any locality of reference among keys.
Locality of reference means that accessing one particular key in the
Btree implies that the application is more likely to access keys near to
the key being accessed, where "near" is defined by the sort order.  For
example, if keys are timestamps, and it is likely that a request for an
8AM timestamp will be followed by a request for a 9AM timestamp, the
Btree access method is generally the right choice.  Or, for example, if
the keys are names, and the application will want to review all entries
with the same last name, the Btree access method is again a good choice.])

m4_p([dnl
There is little difference in performance between the Hash and Btree
access methods on small data sets, where all, or most of, the data set
fits into the cache.  However, when a data set is large enough that
significant numbers of data pages no longer fit into the cache, then
the Btree locality of reference described previously becomes important
for performance reasons.  For example, there is no locality of reference
for the Hash access method, and so key "AAAAA" is as likely to be stored
on the same database page with key "ZZZZZ" as with key "AAAAB".  In the
Btree access method, because items are sorted, key "AAAAA" is far more
likely to be near key "AAAAB" than key "ZZZZZ".  So, if the application
exhibits locality of reference in its data requests, then the Btree page
read into the cache to satisfy a request for key "AAAAA" is much more
likely to be useful to satisfy subsequent requests from the application
than the Hash page read into the cache to satisfy the same request.
This means that for applications with locality of reference, the cache
is generally much more effective for the Btree access method than the
Hash access method, and the Btree access method will make many fewer
I/O calls.])

m4_p([dnl
However, when a data set becomes even larger, the Hash access method can
outperform the Btree access method.  The reason for this is that Btrees
contain more metadata pages than Hash databases.  The data set can grow
so large that metadata pages begin to dominate the cache for the Btree
access method.  If this happens, the Btree can be forced to do an I/O
for each data request because the probability that any particular data
page is already in the cache becomes quite small.  Because the Hash access
method has fewer metadata pages, its cache stays "hotter" longer in the
presence of large data sets.  In addition, once the data set is so large
that both the Btree and Hash access methods are almost certainly doing
an I/O for each random data request, the fact that Hash does not have to
walk several internal pages as part of a key search becomes a performance
advantage for the Hash access method as well.])

m4_p([dnl
Application data access patterns strongly affect all of these behaviors,
for example, accessing the data by walking a cursor through the database
will greatly mitigate the large data set behavior describe above because
each I/O into the cache will satisfy a fairly large number of subsequent
data requests.])

m4_p([dnl
In the absence of information on application data and data access
patterns, for small data sets either the Btree or Hash access methods
will suffice.  For data sets larger than the cache, we normally recommend
using the Btree access method.  If you have truly large data, then the
Hash access method may be a better choice.  The m4_ref(db_stat) utility
is a useful tool for monitoring how well your cache is performing.])

m4_section(Queue or Recno?)

m4_p([dnl
The Queue or Recno access methods should be used when logical record
numbers are the primary key used for data access.  The advantage of the
Queue access method is that it performs record level locking and for this
reason supports significantly higher levels of concurrency than the Recno
access method.  The advantage of the Recno access method is that it
supports a number of additional features beyond those supported by the
Queue access method, such as variable-length records and support for
backing flat-text files.])

m4_p([dnl
Logical record numbers can be mutable or fixed: mutable, where logical
record numbers can change as records are deleted or inserted, and fixed,
where record numbers never change regardless of the database operation.
It is possible to store and retrieve records based on logical record
numbers in the Btree access method.  However, those record numbers are
always mutable, and as records are deleted or inserted, the logical record
number for other records in the database will change. The Queue access
method always runs in fixed mode, and logical record numbers never change
regardless of the database operation. The Recno access method can be
configured to run in either mutable or fixed mode.])

m4_p([dnl
In addition, the Recno access method provides support for databases whose
permanent storage is a flat text file and the database is used as a fast,
temporary storage area while the data is being read or modified.])

m4_page_footer