1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml"> 4 <head> 5 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> 6 <title>BTree Configuration</title> 7 <link rel="stylesheet" href="gettingStarted.css" type="text/css" /> 8 <meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /> 9 <link rel="start" href="index.html" title="Getting Started with Berkeley DB" /> 10 <link rel="up" href="dbconfig.html" title="Chapter��6.��Database Configuration" /> 11 <link rel="prev" href="cachesize.html" title="Selecting the Cache Size" /> 12 </head> 13 <body> 14 <div class="navheader"> 15 <table width="100%" summary="Navigation header"> 16 <tr> 17 <th colspan="3" align="center">BTree Configuration</th> 18 </tr> 19 <tr> 20 <td width="20%" align="left"><a accesskey="p" href="cachesize.html">Prev</a>��</td> 21 <th width="60%" align="center">Chapter��6.��Database Configuration</th> 22 <td width="20%" align="right">��</td> 23 </tr> 24 </table> 25 <hr /> 26 </div> 27 <div class="sect1" lang="en" xml:lang="en"> 28 <div class="titlepage"> 29 <div> 30 <div> 31 <h2 class="title" style="clear: both"><a id="btree"></a>BTree Configuration</h2> 32 </div> 33 </div> 34 </div> 35 <div class="toc"> 36 <dl> 37 <dt> 38 <span class="sect2"> 39 <a href="btree.html#duplicateRecords">Allowing Duplicate Records</a> 40 </span> 41 </dt> 42 <dt> 43 <span class="sect2"> 44 <a href="btree.html#comparators">Setting Comparison Functions</a> 45 </span> 46 </dt> 47 </dl> 48 </div> 49 <p> 50 In going through the previous chapters in this book, you may notice that 51 we touch on some topics that are specific to BTree, but we do not cover 52 those topics in any real detail. In this section, we will discuss 53 configuration issues that are unique to BTree. 54 </p> 55 <p> 56 Specifically, in this section we describe: 57 </p> 58 <div class="itemizedlist"> 59 <ul type="disc"> 60 <li> 61 <p> 62 Allowing duplicate records. 63 </p> 64 </li> 65 <li> 66 <p> 67 Setting comparator callbacks. 68 </p> 69 </li> 70 </ul> 71 </div> 72 <div class="sect2" lang="en" xml:lang="en"> 73 <div class="titlepage"> 74 <div> 75 <div> 76 <h3 class="title"><a id="duplicateRecords"></a>Allowing Duplicate Records</h3> 77 </div> 78 </div> 79 </div> 80 <p> 81 BTree databases can contain duplicate records. One record is 82 considered to be a duplicate of another when both records use keys 83 that compare as equal to one another. 84 </p> 85 <p> 86 By default, keys are compared using a lexicographical comparison, 87 with shorter keys collating higher than longer keys. 88 You can override this default using the 89 <code class="methodname">DB->set_bt_compare()</code> 90 91 92 method. See the next section for details. 93 </p> 94 <p> 95 By default, DB databases do not allow duplicate records. As a 96 result, any attempt to write a record that uses a key equal to a 97 previously existing record results in the previously existing record 98 being overwritten by the new record. 99 </p> 100 <p> 101 Allowing duplicate records is useful if you have a database that 102 contains records keyed by a commonly occurring piece of information. 103 It is frequently necessary to allow duplicate records for secondary 104 databases. 105 </p> 106 <p> 107 For example, suppose your primary database contained records related 108 to automobiles. You might in this case want to be able to find all 109 the automobiles in the database that are of a particular color, so 110 you would index on the color of the automobile. However, for any 111 given color there will probably be multiple automobiles. Since the 112 index is the secondary key, this means that multiple secondary 113 database records will share the same key, and so the secondary 114 database must support duplicate records. 115 </p> 116 <div class="sect3" lang="en" xml:lang="en"> 117 <div class="titlepage"> 118 <div> 119 <div> 120 <h4 class="title"><a id="sorteddups"></a>Sorted Duplicates</h4> 121 </div> 122 </div> 123 </div> 124 <p> 125 Duplicate records can be stored in sorted or unsorted order. 126 You can cause DB to automatically sort your duplicate 127 records by 128 <span> 129 specifying the <code class="literal">DB_DUPSORT</code> flag at 130 database creation time. 131 </span> 132 133 </p> 134 <p> 135 If sorted duplicates are supported, then the 136 <span> 137 sorting function specified on 138 <code class="methodname">DB->set_dup_compare()</code> 139 140 </span> 141 142 is used to determine the location of the duplicate record in its 143 duplicate set. If no such function is provided, then the default 144 lexicographical comparison is used. 145 </p> 146 </div> 147 <div class="sect3" lang="en" xml:lang="en"> 148 <div class="titlepage"> 149 <div> 150 <div> 151 <h4 class="title"><a id="nosorteddups"></a>Unsorted Duplicates</h4> 152 </div> 153 </div> 154 </div> 155 <p> 156 For performance reasons, BTrees should always contain sorted 157 records. (BTrees containing unsorted entries must potentially 158 spend a great deal more time locating an entry than does a BTree 159 that contains sorted entries). That said, DB provides support 160 for suppressing automatic sorting of duplicate records because it may be that 161 your application is inserting records that are already in a 162 sorted order. 163 </p> 164 <p> 165 That is, if the database is configured to support unsorted 166 duplicates, then the assumption is that your application 167 will manually perform the sorting. In this event, 168 expect to pay a significant performance penalty. Any time you 169 place records into the database in a sort order not know to 170 DB, you will pay a performance penalty 171 </p> 172 <p> 173 That said, this is how DB behaves when inserting records 174 into a database that supports non-sorted duplicates: 175 </p> 176 <div class="itemizedlist"> 177 <ul type="disc"> 178 <li> 179 <p> 180 If your application simply adds a duplicate record using 181 <span><code class="methodname">DB->put()</code>,</span> 182 183 184 then the record is inserted at the end of its sorted duplicate set. 185 </p> 186 </li> 187 <li> 188 <p> 189 If a cursor is used to put the duplicate record to the database, 190 then the new record is placed in the duplicate set according to the 191 flags that are provided on the 192 <code class="methodname">DBC->put()</code> 193 194 method. The relevant flags are: 195 </p> 196 <div class="itemizedlist"> 197 <ul type="circle"> 198 <li> 199 <p> 200 <code class="literal">DB_AFTER</code> 201 202 </p> 203 <p> 204 The data 205 <span> 206 provided on the call to 207 <code class="methodname">DBC->put()</code> 208 209 </span> 210 is placed into the database 211 as a duplicate record. The key used for this operation is 212 the key used for the record to which the cursor currently 213 refers. Any key provided on the call 214 215 <span> 216 to 217 <code class="methodname">DBC->put()</code> 218 219 </span> 220 221 is therefore ignored. 222 </p> 223 <p> 224 The duplicate record is inserted into the database 225 immediately after the cursor's current position in the 226 database. 227 </p> 228 <p> 229 This flag is ignored if sorted duplicates are supported for 230 the database. 231 </p> 232 </li> 233 <li> 234 <p> 235 <code class="literal">DB_BEFORE</code> 236 237 </p> 238 <p> 239 Behaves the same as 240 <code class="literal">DB_AFTER</code> 241 242 except that the new record is inserted immediately before 243 the cursor's current location in the database. 244 </p> 245 </li> 246 <li> 247 <p> 248 <code class="literal">DB_KEYFIRST</code> 249 250 </p> 251 <p> 252 If the key 253 <span> 254 provided on the call to 255 <code class="methodname">DBC->put()</code> 256 257 </span> 258 already exists in the 259 database, and the database is configured to use duplicates 260 without sorting, then the new record is inserted as the first entry 261 in the appropriate duplicates list. 262 </p> 263 </li> 264 <li> 265 <p> 266 <code class="literal">DB_KEYLAST</code> 267 268 </p> 269 <p> 270 Behaves identically to 271 <code class="literal">DB_KEYFIRST</code> 272 273 except that the new duplicate record is inserted as the last 274 record in the duplicates list. 275 </p> 276 </li> 277 </ul> 278 </div> 279 </li> 280 </ul> 281 </div> 282 </div> 283 <div class="sect3" lang="en" xml:lang="en"> 284 <div class="titlepage"> 285 <div> 286 <div> 287 <h4 class="title"><a id="specifyingDups"></a>Configuring a Database to Support Duplicates</h4> 288 </div> 289 </div> 290 </div> 291 <p> 292 Duplicates support can only be configured 293 at database creation time. You do this by specifying the appropriate 294 <span> 295 flags to 296 <code class="methodname">DB->set_flags()</code> 297 298 </span> 299 300 before the database is opened for the first time. 301 </p> 302 <p> 303 The 304 <span>flags</span> 305 306 that you can use are: 307 </p> 308 <div class="itemizedlist"> 309 <ul type="disc"> 310 <li> 311 <p> 312 <code class="literal">DB_DUP</code> 313 314 </p> 315 <p> 316 The database supports non-sorted duplicate records. 317 </p> 318 </li> 319 <li> 320 <p> 321 <code class="literal">DB_DUPSORT</code> 322 323 </p> 324 <p> 325 The database supports sorted duplicate records. 326 </p> 327 </li> 328 </ul> 329 </div> 330 <p> 331 The following code fragment illustrates how to configure a database 332 to support sorted duplicate records: 333 </p> 334 <a id="c_btree_dupsort"></a> 335 <pre class="programlisting">#include <db.h> 336... 337 338DB *dbp; 339FILE *error_file_pointer; 340int ret; 341char *program_name = "my_prog"; 342char *file_name = "mydb.db"; 343 344/* Variable assignments omitted for brevity */ 345 346/* Initialize the DB handle */ 347ret = db_create(&dbp, NULL, 0); 348if (ret != 0) { 349 fprintf(error_file_pointer, "%s: %s\n", program_name, 350 db_strerror(ret)); 351 return(ret); 352} 353 354/* Set up error handling for this database */ 355dbp->set_errfile(dbp, error_file_pointer); 356dbp->set_errpfx(dbp, program_name); 357 358/* 359 * Configure the database for sorted duplicates 360 */ 361ret = dbp->set_flags(dbp, DB_DUPSORT); 362if (ret != 0) { 363 dbp->err(dbp, ret, "Attempt to set DUPSORT flag failed."); 364 dbp->close(dbp, 0); 365 return(ret); 366} 367 368/* Now open the database */ 369ret = dbp->open(dbp, /* Pointer to the database */ 370 NULL, /* Txn pointer */ 371 file_name, /* File name */ 372 NULL, /* Logical db name (unneeded) */ 373 DB_BTREE, /* Database type (using btree) */ 374 DB_CREATE, /* Open flags */ 375 0); /* File mode. Using defaults */ 376if (ret != 0) { 377 dbp->err(dbp, ret, "Database '%s' open failed.", file_name); 378 dbp->close(dbp, 0); 379 return(ret); 380} </pre> 381 </div> 382 </div> 383 <div class="sect2" lang="en" xml:lang="en"> 384 <div class="titlepage"> 385 <div> 386 <div> 387 <h3 class="title"><a id="comparators"></a>Setting Comparison Functions</h3> 388 </div> 389 </div> 390 </div> 391 <p> 392 By default, DB uses a lexicographical comparison function where 393 shorter records collate before longer records. For the majority of 394 cases, this comparison works well and you do not need to manage 395 it in any way. 396 </p> 397 <p> 398 However, in some situations your application's performance can 399 benefit from setting a custom comparison routine. You can do this 400 either for database keys, or for the data if your 401 database supports sorted duplicate records. 402 </p> 403 <p> 404 Some of the reasons why you may want to provide a custom sorting 405 function are: 406 </p> 407 <div class="itemizedlist"> 408 <ul type="disc"> 409 <li> 410 <p> 411 Your database is keyed using strings and you want to provide 412 some sort of language-sensitive ordering to that data. Doing 413 so can help increase the locality of reference that allows 414 your database to perform at its best. 415 </p> 416 </li> 417 <li> 418 <p> 419 You are using a little-endian system (such as x86) and you 420 are using integers as your database's keys. Berkeley DB 421 stores keys as byte strings and little-endian integers 422 do not sort well when viewed as byte strings. There are 423 several solutions to this problem, one being to provide a 424 custom comparison function. See 425 <a class="ulink" href="http://www.oracle.com/technology/documentation/berkeley-db/db/ref/am_misc/faq.html" target="_top">http://www.oracle.com/technology/documentation/berkeley-db/db/ref/am_misc/faq.html</a> 426 for more information. 427 </p> 428 </li> 429 <li> 430 <p> 431 You you do not want the entire key to participate in the 432 comparison, for whatever reason. In 433 this case, you may want to provide a custom comparison 434 function so that only the relevant bytes are examined. 435 </p> 436 </li> 437 </ul> 438 </div> 439 <div class="sect3" lang="en" xml:lang="en"> 440 <div class="titlepage"> 441 <div> 442 <div> 443 <h4 class="title"><a id="creatingComparisonFunctions"></a> 444 <span>Creating Comparison Functions</span> 445 446 </h4> 447 </div> 448 </div> 449 </div> 450 <p> 451 You set a BTree's key 452 <span> 453 comparison function 454 </span> 455 456 using 457 <span><code class="methodname">DB->set_bt_compare()</code>.</span> 458 459 460 You can also set a BTree's duplicate data comparison function using 461 <span><code class="methodname">DB->set_dup_compare()</code>.</span> 462 463 464 465 </p> 466 <p> 467 <span> 468 You cannot use these methods after the database has been opened. 469 Also, if 470 </span> 471 472 the database already exists when it is opened, the 473 <span> 474 function 475 </span> 476 477 provided to these methods must be the same as 478 that historically used to create the database or corruption can 479 occur. 480 </p> 481 <p> 482 The value that you provide to the <code class="methodname">set_bt_compare()</code> method 483 is a pointer to a function that has the following signature: 484 </p> 485 <pre class="programlisting">int (*function)(DB *db, const DBT *key1, const DBT *key2)</pre> 486 <p> 487 This function must return an integer value less than, equal to, 488 or greater than 0. If key1 is considered to be greater than 489 key2, then the function must return a value that is greater than 490 0. If the two are equal, then the function must return 0, and if 491 the first key is less than the second then the function must return 492 a negative value. 493 </p> 494 <p> 495 The function that you provide to <code class="methodname">set_dup_compare()</code> 496 works in exactly the same way, except that the 497 <code class="literal">DBT</code> 498 499 parameters hold record data items instead of keys. 500 </p> 501 <p> 502 For example, an example routine that is used to sort integer 503 keys in the database is: 504 <span> 505 506 </span> 507 </p> 508 <a id="c_btree1"></a> 509 <pre class="programlisting">int 510compare_int(DB *dbp, const DBT *a, const DBT *b) 511{ 512 int ai, bi; 513 514 /* 515 * Returns: 516 * < 0 if a < b 517 * = 0 if a = b 518 * > 0 if a > b 519 */ 520 memcpy(&ai, a->data, sizeof(int)); 521 memcpy(&bi, b->data, sizeof(int)); 522 return (ai - bi); 523} </pre> 524 <p> 525 Note that the data must first be copied into memory that is 526 appropriately aligned, as Berkeley DB does not guarantee any kind of 527 alignment of the underlying data, including for comparison routines. 528 When writing comparison routines, remember that databases created on 529 machines of different architectures may have different integer byte 530 orders, for which your code may need to compensate. 531 </p> 532 <p> 533 To cause DB to use this comparison function: 534 </p> 535 <a id="c_btree2"></a> 536 <pre class="programlisting">#include <db.h> 537#include <string.h> 538 539... 540 541DB *dbp; 542int ret; 543 544/* Create a database */ 545ret = db_create(&dbp, NULL, 0); 546if (ret != 0) { 547 fprintf(stderr, "%s: %s\n", "my_program", 548 db_strerror(ret)); 549 return(-1); 550} 551 552/* Set up the btree comparison function for this database */ 553dbp->set_bt_compare(dbp, compare_int); 554 555/* Database open call follows sometime after this. */ </pre> 556 </div> 557 </div> 558 </div> 559 <div class="navfooter"> 560 <hr /> 561 <table width="100%" summary="Navigation footer"> 562 <tr> 563 <td width="40%" align="left"><a accesskey="p" href="cachesize.html">Prev</a>��</td> 564 <td width="20%" align="center"> 565 <a accesskey="u" href="dbconfig.html">Up</a> 566 </td> 567 <td width="40%" align="right">��</td> 568 </tr> 569 <tr> 570 <td width="40%" align="left" valign="top">Selecting the Cache Size��</td> 571 <td width="20%" align="center"> 572 <a accesskey="h" href="index.html">Home</a> 573 </td> 574 <td width="40%" align="right" valign="top">��</td> 575 </tr> 576 </table> 577 </div> 578 </body> 579</html> 580