berkeley db partial match

Question

Is there any way with berkeley db 5.x C API to get all the records with a key matching a prefix ?

(without scanning the entire database)

Maybe with a Btree prefix comparison custom callback ?

Answer 1

There are two parts to the solution. First, you need to use a custom key comparison function.

dbp->set_bt_compare(dbp, cmp_fn);

In the comparison function, make it so that the keys with the same prefix are sorted next to each other in the database. This might be as simple as a bunch of less-than compares, so that something like 0x000000000000000000000001 is less than 0x000000000000000000000002.

To do the search, open a cursor and do a cursor->get() with a DB_SET_RANGE flag. Set your starting key to be at the beginning of the prefix range. Say, if you were looking for keys with the prefix 0x1138, you'd set the key to 0x113800000000000000000000. Then keep calling cursor->get() with DB_NEXT. When you see a key that doesn't have the 0x1138 prefix, you're done.

This technique does not have to scan the entire database, as the initial DB_SET_RANGE call starts the cursor in the right place, and the records are all right next to each other in the tree.