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 90 <code class="methodname">Db::set_bt_compare()</code> 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 139 <code class="methodname">Db::set_dup_compare()</code> 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 182 <span><code class="methodname">Db::put()</code>,</span> 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 193 <code class="methodname">Dbc::put()</code> 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 208 <code class="methodname">Dbc::put()</code> 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 218 <code class="methodname">Dbc::put()</code> 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 256 <code class="methodname">Dbc::put()</code> 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 297 <code class="methodname">Db::set_flags()</code> 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="cxx_btree_dupsort"></a> 335 <pre class="programlisting">#include <db_cxx.h> 336... 337 338Db db(NULL, 0); 339const char *file_name = "myd.db"; 340 341try { 342 // Configure the database for sorted duplicates 343 db.set_flags(DB_DUPSORT); 344 345 // Now open the database 346 db.open(NULL, // Txn pointer 347 file_name, // File name 348 NULL, // Logical db name (unneeded) 349 DB_BTREE, // Database type (using btree) 350 DB_CREATE, // Open flags 351 0); // File mode. Using defaults 352} catch(DbException &e) { 353 db.err(e.get_errno(), "Database '%s' open failed.", file_name); 354} catch(std::exception &e) { 355 db.errx("Error opening database: %s : %s\n", file_name, e.what()); 356} 357 358... 359 360try { 361 db.close(0); 362} catch(DbException &e) { 363 db.err(e.get_errno(), "Database '%s' close failed.", file_name); 364} catch(std::exception &e) { 365 db.errx("Error closing database: %s : %s\n", file_name, e.what()); 366} 367 368</pre> 369 </div> 370 </div> 371 <div class="sect2" lang="en" xml:lang="en"> 372 <div class="titlepage"> 373 <div> 374 <div> 375 <h3 class="title"><a id="comparators"></a>Setting Comparison Functions</h3> 376 </div> 377 </div> 378 </div> 379 <p> 380 By default, DB uses a lexicographical comparison function where 381 shorter records collate before longer records. For the majority of 382 cases, this comparison works well and you do not need to manage 383 it in any way. 384 </p> 385 <p> 386 However, in some situations your application's performance can 387 benefit from setting a custom comparison routine. You can do this 388 either for database keys, or for the data if your 389 database supports sorted duplicate records. 390 </p> 391 <p> 392 Some of the reasons why you may want to provide a custom sorting 393 function are: 394 </p> 395 <div class="itemizedlist"> 396 <ul type="disc"> 397 <li> 398 <p> 399 Your database is keyed using strings and you want to provide 400 some sort of language-sensitive ordering to that data. Doing 401 so can help increase the locality of reference that allows 402 your database to perform at its best. 403 </p> 404 </li> 405 <li> 406 <p> 407 You are using a little-endian system (such as x86) and you 408 are using integers as your database's keys. Berkeley DB 409 stores keys as byte strings and little-endian integers 410 do not sort well when viewed as byte strings. There are 411 several solutions to this problem, one being to provide a 412 custom comparison function. See 413 <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> 414 for more information. 415 </p> 416 </li> 417 <li> 418 <p> 419 You you do not want the entire key to participate in the 420 comparison, for whatever reason. In 421 this case, you may want to provide a custom comparison 422 function so that only the relevant bytes are examined. 423 </p> 424 </li> 425 </ul> 426 </div> 427 <div class="sect3" lang="en" xml:lang="en"> 428 <div class="titlepage"> 429 <div> 430 <div> 431 <h4 class="title"><a id="creatingComparisonFunctions"></a> 432 <span>Creating Comparison Functions</span> 433 434 </h4> 435 </div> 436 </div> 437 </div> 438 <p> 439 You set a BTree's key 440 <span> 441 comparison function 442 </span> 443 444 using 445 446 <span><code class="methodname">Db::set_bt_compare()</code>.</span> 447 448 You can also set a BTree's duplicate data comparison function using 449 450 <span><code class="methodname">Db::set_dup_compare()</code>.</span> 451 452 453 </p> 454 <p> 455 <span> 456 You cannot use these methods after the database has been opened. 457 Also, if 458 </span> 459 460 the database already exists when it is opened, the 461 <span> 462 function 463 </span> 464 465 provided to these methods must be the same as 466 that historically used to create the database or corruption can 467 occur. 468 </p> 469 <p> 470 The value that you provide to the <code class="methodname">set_bt_compare()</code> method 471 is a pointer to a function that has the following signature: 472 </p> 473 <pre class="programlisting">int (*function)(Db *db, const Dbt *key1, const Dbt *key2)</pre> 474 <p> 475 This function must return an integer value less than, equal to, 476 or greater than 0. If key1 is considered to be greater than 477 key2, then the function must return a value that is greater than 478 0. If the two are equal, then the function must return 0, and if 479 the first key is less than the second then the function must return 480 a negative value. 481 </p> 482 <p> 483 The function that you provide to <code class="methodname">set_dup_compare()</code> 484 works in exactly the same way, except that the 485 486 <code class="literal">Dbt</code> 487 parameters hold record data items instead of keys. 488 </p> 489 <p> 490 For example, an example routine that is used to sort integer 491 keys in the database is: 492 493 </p> 494 <a id="cxx_btree1"></a> 495 <pre class="programlisting">int 496compare_int(Db *dbp, const Dbt *a, const Dbt *b) 497{ 498 int ai, bi; 499 500 // Returns: 501 // < 0 if a < b 502 // = 0 if a = b 503 // > 0 if a > b 504 memcpy(&ai, a->get_data(), sizeof(int)); 505 memcpy(&bi, b->get_data(), sizeof(int)); 506 return (ai - bi); 507} </pre> 508 <p> 509 Note that the data must first be copied into memory that is 510 appropriately aligned, as Berkeley DB does not guarantee any kind of 511 alignment of the underlying data, including for comparison routines. 512 When writing comparison routines, remember that databases created on 513 machines of different architectures may have different integer byte 514 orders, for which your code may need to compensate. 515 </p> 516 <p> 517 To cause DB to use this comparison function: 518 </p> 519 <a id="cxx_btree2"></a> 520 <pre class="programlisting">#include <db_cxx.h> 521#include <string.h> 522 523... 524 525Db db(NULL, 0); 526 527// Set up the btree comparison function for this database 528db.set_bt_compare(compare_int); 529 530// Database open call follows sometime after this.</pre> 531 </div> 532 </div> 533 </div> 534 <div class="navfooter"> 535 <hr /> 536 <table width="100%" summary="Navigation footer"> 537 <tr> 538 <td width="40%" align="left"><a accesskey="p" href="cachesize.html">Prev</a>��</td> 539 <td width="20%" align="center"> 540 <a accesskey="u" href="dbconfig.html">Up</a> 541 </td> 542 <td width="40%" align="right">��</td> 543 </tr> 544 <tr> 545 <td width="40%" align="left" valign="top">Selecting the Cache Size��</td> 546 <td width="20%" align="center"> 547 <a accesskey="h" href="index.html">Home</a> 548 </td> 549 <td width="40%" align="right" valign="top">��</td> 550 </tr> 551 </table> 552 </div> 553 </body> 554</html> 555