1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
<! "@(#)bt_prefix.so 10.4 (Sleepycat) 10/18/98">
<!Copyright 1997, 1998 by Sleepycat Software, Inc. All rights reserved.>
<html>
<body bgcolor=white>
<head>
<title>Berkeley DB Reference Guide: Access Methods</title>
<meta name="description" content="Berkeley DB: An embedded database programmatic toolkit.">
<meta name="keywords" content="embedded,database,programmatic,toolkit,b+tree,btr
ee,hash,hashing,transaction,transactions,locking,logging,access method,access me
thods,java,C,C++">
</head>
<h3>Berkeley DB Reference Guide: Access Methods</h3>
<p>
<h1 align=center>Btree prefix function (bt_prefix)</h1>
<p>
A prefix comparison function for the Btree can be specified as part of
the <a href="../../api_c/Db/open.html">db_open</a> call to open the database, specifically by setting
the <a href="../../api_c/DbInfo/info.html#bt_prefix">bt_prefix</a> element of the DB_INFO structure.
<p>
The prefix comparison routine is used to compress keys stored on the Btree
internal pages by minimizing the number of bytes that are stored to
distinguish between two keys on the internal pages. The usefulness of
this is data dependent, but in some data sets can produce significantly
reduced tree sizes and therefore, search times.
<p>
Obviously, the prefix comparison routine must be compatible with the
overall comparison function of the Btree. If no prefix comparison
function is specified, and no overall comparison function is specified,
a default, lexical prefix comparison function is used. If no prefix
comparison function is specified, and an overall comparison function is
specified, no prefix comparison is done.
<p>
Prefix comparison routines are passed pointers to keys as arguments. The
keys are represented as DBT structures. The prefix comparison
function must return the number of bytes of the second key argument that
are necessary to determine that it is greater than the first key argument.
If the keys are equal, the length of the second key should be returned.
The only fields that the routines may examine in the DBT structures
are <b>data</b> and <b>size</b> fields.
<p>
An example prefix comparison routine follows:
<p><ul><pre>
compare_prefix(a, b)
const DBT *a, *b;
{
size_t cnt, len;
u_int8_t *p1, *p2;
<p>
cnt = 1;
len = a->size > b->size ? b->size : a->size;
for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
if (*p1 != *p2)
return (cnt);
/*
* They match up to the smaller of the two sizes. Collate the
* longer after the shorter.
*/
if (a->size < b->size)
return (a->size + 1);
if (b->size < a->size)
return (b->size + 1);
return (a->size);
}
</pre></ul><p>
<p>
<a href="../../ref/am/bt_compare.html"><img src="../../images/prev.gif"></a>
<a href="../../ref/toc.html"><img src="../../images/toc.gif"></a>
<a href="../../ref/am/bt_minkey.html"><img src="../../images/next.gif"></a>
</tt>
</body>
</html>
|
