1<!--$Id: bt_prefix.so,v 10.22 2004/02/21 15:50:51 bostic Exp $--> 2<!--Copyright (c) 1997,2008 Oracle. All rights reserved.--> 3<!--See the file LICENSE for redistribution information.--> 4<html> 5<head> 6<title>Berkeley DB Reference Guide: Btree prefix comparison</title> 7<meta name="description" content="Berkeley DB: An embedded database programmatic toolkit."> 8<meta name="keywords" content="embedded,database,programmatic,toolkit,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,Java,C,C++"> 9</head> 10<body bgcolor=white> 11<table width="100%"><tr valign=top> 12<td><b><dl><dt>Berkeley DB Reference Guide:<dd>Access Methods</dl></b></td> 13<td align=right><a href="../am_conf/bt_compare.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/bt_minkey.html"><img src="../../images/next.gif" alt="Next"></a> 14</td></tr></table> 15<p align=center><b>Btree prefix comparison</b></p> 16<p>The Berkeley DB Btree implementation maximizes the number of keys that can be 17stored on an internal page by storing only as many bytes of each key as 18are necessary to distinguish it from adjacent keys. The prefix 19comparison routine is what determines this minimum number of bytes (that 20is, the length of the unique prefix), that must be stored. A prefix 21comparison function for the Btree can be specified by calling 22<a href="../../api_c/db_set_bt_prefix.html">DB->set_bt_prefix</a>.</p> 23<p>The prefix comparison routine must be compatible with the overall 24comparison function of the Btree, since what distinguishes any two keys 25depends entirely on the function used to compare them. This means that 26if a prefix comparison routine is specified by the application, a 27compatible overall comparison routine must also have been specified.</p> 28<p>Prefix comparison routines are passed pointers to keys as arguments. 29The keys are represented as <a href="../../api_c/dbt_class.html">DBT</a> structures. The only fields 30the routines may examine in the <a href="../../api_c/dbt_class.html">DBT</a> structures are <b>data</b> 31and <b>size</b> fields.</p> 32<p>The prefix comparison function must return the number of bytes necessary 33to distinguish the two keys. If the keys are identical (equal and equal 34in length), the length should be returned. If the keys are equal up to 35the smaller of the two lengths, then the length of the smaller key plus 361 should be returned.</p> 37<p>An example prefix comparison routine follows:</p> 38<blockquote><pre>u_int32_t 39compare_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->size > b->size ? b->size : a->size; 48 for (p1 = 49 a->data, p2 = b->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->size < b->size) 57 return (a->size + 1); 58 if (b->size < a->size) 59 return (b->size + 1); 60 return (b->size); 61}</pre></blockquote> 62<p>The usefulness of this functionality is data-dependent, but in some data 63sets can produce significantly reduced tree sizes and faster search times.</p> 64<table width="100%"><tr><td><br></td><td align=right><a href="../am_conf/bt_compare.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/bt_minkey.html"><img src="../../images/next.gif" alt="Next"></a> 65</td></tr></table> 66<p><font size=1>Copyright (c) 1996,2008 Oracle. All rights reserved.</font> 67</body> 68</html> 69
