<!--$Id: bt_prefix.so,v 10.17 2000/07/04 18:28:27 bostic Exp $--> <!--Copyright 1997, 1998, 1999, 2000 by Sleepycat Software, Inc.--> <!--All rights reserved.--> <html> <head> <title>Berkeley DB Reference Guide: Btree prefix comparison</title> <meta name="description" content="Berkeley DB: An embedded database programmatic toolkit."> <meta name="keywords" content="embedded,database,programmatic,toolkit,b+tree,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,java,C,C++"> </head> <body bgcolor=white> <table><tr valign=top> <td><h3><dl><dt>Berkeley DB Reference Guide:<dd>Access Methods</dl></h3></td> <td width="1%"><a href="../../ref/am_conf/bt_compare.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../../ref/toc.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> </td></tr></table> <p> <h1 align=center>Btree prefix comparison</h1> <p>The Berkeley DB Btree implementation maximizes the number of keys that can be stored on an internal page by storing only as many bytes of each key as are necessary to distinguish it from adjacent keys. The prefix comparison routine is what determines this minimum number of bytes (i.e., the length of the unique prefix), that must be stored. A prefix comparison function for the Btree can be specified by calling <a href="../../api_c/db_set_bt_prefix.html">DB->set_bt_prefix</a>. <p>The prefix comparison routine must be compatible with the overall comparison function of the Btree, since what distinguishes any two keys depends entirely on the function used to compare them. This means that if a prefix comparison routine is specified by the application, a compatible overall comparison routine must also have been specified. <p>Prefix comparison routines are passed pointers to keys as arguments. The keys are represented as <a href="../../api_c/dbt.html">DBT</a> structures. The prefix comparison function must return the number of bytes of the second key argument that are necessary to determine if 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 <a href="../../api_c/dbt.html">DBT</a> structures are <b>data</b> and <b>size</b> fields. <p>An example prefix comparison routine follows: <p><blockquote><pre>u_int32_t compare_prefix(dbp, a, b) DB *dbp; 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 (b->size); }</pre></blockquote> <p>The usefulness of this functionality is data dependent, but in some data sets can produce significantly reduced tree sizes and faster search times. <table><tr><td><br></td><td width="1%"><a href="../../ref/am_conf/bt_compare.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../../ref/toc.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> </td></tr></table> <p><font size=1><a href="http://www.sleepycat.com">Copyright Sleepycat Software</a></font> </body> </html>