Duplicate records can be stored in sorted or unsorted order. You can cause DB to automatically sort your duplicate records by specifying the DB_DUPSORT flag at database creation time.

If sorted duplicates are supported, then the sorting function specified on DB->set_dup_compare() is used to determine the location of the duplicate record in its duplicate set. If no such function is provided, then the default lexicographical comparison is used.

For performance reasons, BTrees should always contain sorted records. (BTrees containing unsorted entries must potentially spend a great deal more time locating an entry than does a BTree that contains sorted entries). That said, DB provides support for suppressing automatic sorting of duplicate records because it may be that your application is inserting records that are already in a sorted order.

That is, if the database is configured to support unsorted duplicates, then the assumption is that your application will manually perform the sorting. In this event, expect to pay a significant performance penalty. Any time you place records into the database in a sort order not know to DB, you will pay a performance penalty

That said, this is how DB behaves when inserting records into a database that supports non-sorted duplicates:

Duplicates support can only be configured at database creation time. You do this by specifying the appropriate flags to DB->set_flags() before the database is opened for the first time.

The flags that you can use are:

The following code fragment illustrates how to configure a database to support sorted duplicate records:

#include <db.h>
...

DB *dbp;
FILE *error_file_pointer;
int ret;
char *program_name = "my_prog";
char *file_name = "mydb.db";

/* Variable assignments omitted for brevity */

/* Initialize the DB handle */
ret = db_create(&dbp, NULL, 0);
if (ret != 0) {
    fprintf(error_file_pointer, "%s: %s\n", program_name,
        db_strerror(ret));
    return(ret);
}

/* Set up error handling for this database */
dbp->set_errfile(dbp, error_file_pointer);
dbp->set_errpfx(dbp, program_name);

/*
 * Configure the database for sorted duplicates
 */
ret = dbp->set_flags(dbp, DB_DUPSORT);
if (ret != 0) {
    dbp->err(dbp, ret, "Attempt to set DUPSORT flag failed.");
    dbp->close(dbp, 0);
    return(ret);
}

/* Now open the database */
ret = dbp->open(dbp,        /* Pointer to the database */
                NULL,       /* Txn pointer */
                file_name,  /* File name */
                NULL,       /* Logical db name (unneeded) */
                DB_BTREE,   /* Database type (using btree) */
                DB_CREATE,  /* Open flags */
                0);         /* File mode. Using defaults */
if (ret != 0) {
    dbp->err(dbp, ret, "Database '%s' open failed.", file_name);
    dbp->close(dbp, 0);
    return(ret);
} 

You set a BTree's key comparison function using DB->set_bt_compare(). You can also set a BTree's duplicate data comparison function using DB->set_dup_compare().

You cannot use these methods after the database has been opened. Also, if the database already exists when it is opened, the function provided to these methods must be the same as that historically used to create the database or corruption can occur.

The value that you provide to the set_bt_compare() method is a pointer to a function that has the following signature:

int (*function)(DB *db, const DBT *key1, const DBT *key2)

This function must return an integer value less than, equal to, or greater than 0. If key1 is considered to be greater than key2, then the function must return a value that is greater than 0. If the two are equal, then the function must return 0, and if the first key is less than the second then the function must return a negative value.

The function that you provide to set_dup_compare() works in exactly the same way, except that the DBT parameters hold record data items instead of keys.

For example, an example routine that is used to sort integer keys in the database is:

int
compare_int(DB *dbp, const DBT *a, const DBT *b)
{
    int ai, bi;

    /* 
     * Returns: 
     * < 0 if a < b 
     * = 0 if a = b 
     * > 0 if a > b 
     */ 
    memcpy(&ai, a->data, sizeof(int)); 
    memcpy(&bi, b->data, sizeof(int)); 
    return (ai - bi); 
} 

Note that the data must first be copied into memory that is appropriately aligned, as Berkeley DB does not guarantee any kind of alignment of the underlying data, including for comparison routines. When writing comparison routines, remember that databases created on machines of different architectures may have different integer byte orders, for which your code may need to compensate.

To cause DB to use this comparison function:

#include <db.h>
#include <string.h>

...

DB *dbp;
int ret;

/* Create a database */
ret = db_create(&dbp, NULL, 0);
if (ret != 0) {
        fprintf(stderr, "%s: %s\n", "my_program",
          db_strerror(ret));
        return(-1);
}

/* Set up the btree comparison function for this database */
dbp->set_bt_compare(dbp, compare_int);

/* Database open call follows sometime after this. */