← Back to branch summary

~ubuntu-branches/ubuntu/natty/evolution-data-server/natty

« back to all changes in this revision

Viewing changes to libdb/docs/ref/am_conf/bt_prefix.html

  • Committer: Bazaar Package Importer
  • Author(s): Didier Roche
  • Date: 2010-05-17 17:02:06 UTC
  • mfrom: (1.1.79 upstream) (1.6.12 experimental)
  • Revision ID: james.westby@ubuntu.com-20100517170206-4ufr52vwrhh26yh0
Tags: 2.30.1-1ubuntu1
https://launchpad.net/bugs/42199
https://launchpad.net/bugs/229669
https://launchpad.net/bugs/173703
https://launchpad.net/bugs/360344
https://launchpad.net/bugs/508494
* Merge from debian experimental. Remaining change:
  (LP: #42199, #229669, #173703, #360344, #508494)
  + debian/control:
    - add Vcs-Bzr tag
    - don't use libgnome
    - Use Breaks instead of Conflicts against evolution 2.25 and earlier.
  + debian/evolution-data-server.install,
    debian/patches/45_libcamel_providers_version.patch:
    - use the upstream versioning, not a Debian-specific one 
  + debian/libedata-book1.2-dev.install, debian/libebackend-1.2-dev.install,
    debian/libcamel1.2-dev.install, debian/libedataserverui1.2-dev.install:
    - install html documentation
  + debian/rules:
    - don't build documentation it's shipped with the tarball

Show diffs side-by-side

added added

removed removed

Lines of Context:
libdb/docs/ref/am_conf/bt_prefix.html
1
 
<!--$Id$-->
2
 
<!--Copyright 1997-2002 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: Btree prefix comparison</title>
8
 
<meta name="description" content="Berkeley DB: An embedded database programmatic toolkit.">
9
 
<meta name="keywords" content="embedded,database,programmatic,toolkit,b+tree,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,java,C,C++">
10
 
</head>
11
 
<body bgcolor=white>
12
 
<table width="100%"><tr valign=top>
13
 
<td><h3><dl><dt>Berkeley DB Reference Guide:<dd>Access Methods</dl></h3></td>
14
 
<td align=right><a href="../../ref/am_conf/bt_compare.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../../reftoc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../../ref/am_conf/bt_minkey.html"><img src="../../images/next.gif" alt="Next"></a>
15
 
</td></tr></table>
16
 
<p>
17
 
<h1 align=center>Btree prefix comparison</h1>
18
 
<p>The Berkeley DB Btree implementation maximizes the number of keys that can be
19
 
stored on an internal page by storing only as many bytes of each key as
20
 
are necessary to distinguish it from adjacent keys.  The prefix
21
 
comparison routine is what determines this minimum number of bytes (that
22
 
is, the length of the unique prefix), that must be stored.  A prefix
23
 
comparison function for the Btree can be specified by calling
24
 
<a href="../../api_c/db_set_bt_prefix.html">DB-&gt;set_bt_prefix</a>.
25
 
<p>The prefix comparison routine must be compatible with the overall
26
 
comparison function of the Btree, since what distinguishes any two keys
27
 
depends entirely on the function used to compare them.  This means that
28
 
if a prefix comparison routine is specified by the application, a
29
 
compatible overall comparison routine must also have been specified.
30
 
<p>Prefix comparison routines are passed pointers to keys as arguments.  The
31
 
keys are represented as <a href="../../api_c/dbt_class.html">DBT</a> structures.  The prefix comparison
32
 
function must return the number of bytes of the second key argument that
33
 
are necessary to determine if it is greater than the first key argument.
34
 
If the keys are equal, the length of the second key should be returned.
35
 
The only fields that the routines may examine in the <a href="../../api_c/dbt_class.html">DBT</a>
36
 
structures are <b>data</b> and <b>size</b> fields.
37
 
<p>An example prefix comparison routine follows:
38
 
<p><blockquote><pre>u_int32_t
39
 
compare_prefix(dbp, a, b)
40
 
        DB *dbp;
41
 
        const DBT *a, *b;
42
 
{
43
 
        size_t cnt, len;
44
 
        u_int8_t *p1, *p2;
45
 
<p>
46
 
        cnt = 1;
47
 
        len = a-&gt;size &gt; b-&gt;size ? b-&gt;size : a-&gt;size;
48
 
        for (p1 =
49
 
                a-&gt;data, p2 = b-&gt;data; len--; ++p1, ++p2, ++cnt)
50
 
                        if (*p1 != *p2)
51
 
                                return (cnt);
52
 
        /*
53
 
         * They match up to the smaller of the two sizes.
54
 
         * Collate the longer after the shorter.
55
 
         */
56
 
        if (a-&gt;size &lt; b-&gt;size)
57
 
                return (a-&gt;size + 1);
58
 
        if (b-&gt;size &lt; a-&gt;size)
59
 
                return (b-&gt;size + 1);
60
 
        return (b-&gt;size);
61
 
}</pre></blockquote>
62
 
<p>The usefulness of this functionality is data-dependent, but in some data
63
 
sets can produce significantly reduced tree sizes and faster search times.
64
 
<table width="100%"><tr><td><br></td><td align=right><a href="../../ref/am_conf/bt_compare.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../../reftoc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../../ref/am_conf/bt_minkey.html"><img src="../../images/next.gif" alt="Next"></a>
65
 
</td></tr></table>
66
 
<p><font size=1><a href="http://www.sleepycat.com">Copyright Sleepycat Software</a></font>
67
 
</body>
68
 
</html>