1<!--$Id: bt_compare.so,v 10.26 2008/01/10 16:02:56 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 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<a name="2"><!--meow--></a> 12<table width="100%"><tr valign=top> 13<td><b><dl><dt>Berkeley DB Reference Guide:<dd>Access Methods</dl></b></td> 14<td align=right><a href="/am_conf/malloc.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_prefix.html"><img src="/images/next.gif" alt="Next"></a> 15</td></tr></table> 16<p align=center><b>Btree comparison</b></p> 17<p>The Btree data structure is a sorted, balanced tree structure storing 18associated key/data pairs. By default, the sort order is lexicographical, 19with shorter keys collating before longer keys. The user can specify the 20sort order for the Btree by using the <a href="/api_c/db_set_bt_compare.html">DB->set_bt_compare</a> method.</p> 21<p>Sort routines are passed pointers to keys as arguments. The keys are 22represented as <a href="/api_c/dbt_class.html">DBT</a> structures. The routine must return an integer 23less than, equal to, or greater than zero if the first argument is 24considered to be respectively less than, equal to, or greater than the 25second argument. The only fields that the routines may examine in the 26<a href="/api_c/dbt_class.html">DBT</a> structures are <b>data</b> and <b>size</b> fields.</p> 27<p>An example routine that might be used to sort integer keys in the database 28is as follows:</p> 29<blockquote><pre>int 30compare_int(dbp, a, b) 31 DB *dbp; 32 const DBT *a, *b; 33{ 34 int ai, bi; 35<p> 36 /* 37 * Returns: 38 * < 0 if a < b 39 * = 0 if a = b 40 * > 0 if a > b 41 */ 42 memcpy(&ai, a->data, sizeof(int)); 43 memcpy(&bi, b->data, sizeof(int)); 44 return (ai - bi); 45}</pre></blockquote> 46<p>Note that the data must first be copied into memory that is appropriately 47aligned, as Berkeley DB does not guarantee any kind of alignment of the 48underlying data, including for comparison routines. When writing 49comparison routines, remember that databases created on machines of 50different architectures may have different integer byte orders, for which 51your code may need to compensate.</p> 52<p>An example routine that might be used to sort keys based on the first 53five bytes of the key (ignoring any subsequent bytes) is as follows:</p> 54<blockquote><pre>int 55compare_dbt(dbp, a, b) 56 DB *dbp; 57 const DBT *a, *b; 58{ 59 int len; 60 u_char *p1, *p2; 61<p> 62 /* 63 * Returns: 64 * < 0 if a < b 65 * = 0 if a = b 66 * > 0 if a > b 67 */ 68 for (p1 = a->data, p2 = b->data, len = 5; len--; ++p1, ++p2) 69 if (*p1 != *p2) 70 return ((long)*p1 - (long)*p2); 71 return (0); 72}</pre></blockquote> 73<p>All comparison functions must cause the keys in the database to be 74well-ordered. The most important implication of being well-ordered is 75that the key relations must be transitive, that is, if key A is less 76than key B, and key B is less than key C, then the comparison routine 77must also return that key A is less than key C.</p> 78<p>It is reasonable for a comparison function to not examine an entire key 79in some applications, which implies partial keys may be specified to the 80Berkeley DB interfaces. When partial keys are specified to Berkeley DB, interfaces 81which retrieve data items based on a user-specified key (for example, 82<a href="/api_c/db_get.html">DB->get</a> and <a href="/api_c/dbc_get.html">DBcursor->get</a> with the <a href="/api_c/dbc_get.html#DB_SET">DB_SET</a> flag), will 83modify the user-specified key by returning the actual key stored in the 84database.</p> 85<table width="100%"><tr><td><br></td><td align=right><a href="/am_conf/malloc.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_prefix.html"><img src="/images/next.gif" alt="Next"></a> 86</td></tr></table> 87<p><font size=1>Copyright (c) 1996,2008 Oracle. All rights reserved.</font> 88</body> 89</html> 90
