Point Reads

Support for searching down the tree in search of a single value.

API

BerkeleyDB offers a get() method on DB, allowing the reading of the stored value corresponding to a key. To represent a key or value, it uses a DBT struct which describes the memory and its size.

db.h
/**
 * Key/data structure -- a Data-Base Thang
 *
 * That's the actual comment from the BerkeleyDB source code.
 */
struct DBT {
  void   *data;    ///< Key/data
  u_int32_t size;  ///< Key/data length

  u_int32_t ulen;  ///< Only used with DB_DBT_USERMEM
  u_int32_t dlen;  ///< Only used with DB_DBT_PARTIAL
  u_int32_t doff;  ///< Only used with DB_DBT_PARTIAL

  void *app_data;  ///< Applications are allowed to associate opaque data.

  u_int32_t flags; ///< Unused
}

See also the official docs for DBT.

The get() method to implement is defined as:

dh.h
struct DB {
  /**
   * Get the value for a key.
   *
   * It is the user's responsibility to manage the memory pointed to by
   * `key`, and ensure that it is valid for the lifetime of the call.
   *
   * `data` should be zero-initialized upon calling get(), and it is the
   * library's responsibility to manage the memory pointed to by data->data.
   * This memory will remain valid until the next call to the library which
   * returns a DBT to the user.
   *
   * @param db The opened DB in which to fetch a key.
   * @param txn The transaction within which this get operation is scoped.
   *            For us, this must be NULL.
   * @param key A DBT owned by the user to describe the kv-pair to fetch.
   * @param data A zero-initialized DBT, which will be written to with
   *             the data and size of the associated data.
   * @param flags Ignored for us.
   * @return 0, if the key was found
   *         DB_NOTFOUND, if the key was not found
   */
  int (*get)(DB *db, DB_TXN *txn, DBT *key, DBT *data, u_int32_t flags);

  // The default mode of operation is that the library is responsible for
  // freeing or reusing any returned state when the next call to any data
  // returning operation is made.  The way that this works is that the DB
  // struct has members which let you store what had been returned to a
  // user previously, so that you can remember what pointers had been
  // returned on a previous call.  There's more to remember for other APIs
  // but for now, we only need to remember what was returned in the `data`
  // argument to `get`.
  DBT  my_rdata;  ///< My Remembered Data.
}

See also the offical docs for DB->get().

There are flags you could optionally support, if it’d make it easier for you to write tests or demo code:

If you don’t support any flags, I would suggest ASSERT()ing that flags is 0, or return -ENOTSUP, as if you try out some bindings with your library later and they happen to pass the flags, it’ll lead to a corruption or crash.

Algorithm

Examining the entries in an internal B-Tree page is going to yield InternalEntrys that look like:

Diagram

And the goal is to find the correct next page to read by comparing the target key against the data in the InternalEntry. Your goal is to find the maximum key that’s less than or equal to your target key. If get() was provided a target key of NNNN, then the goal is to identify offset 60 of PgNo: 4, Data: MMMM as the proper entry, and repeat the search on page 4 next. One could binary search this, but the offsets are maintained in order, and so I found a linear scan the easiest.

Specifically, for internal pages, iterate over the entries with a sliding window of size 2, such that one visits the offset pairs of:

in specifically that order. You’re searching to find a (left, right), where left.data <= target_key && target_key < right.data, and skip the comparison on NULL. If your target key is less than the first InternalEntry's data value, then your target key is not found in the B-Tree. Start with the root page. Repeat on each page indicated by the identified InternalEntry's PgNo until you reach a page where page.level == 1.

Once you’re on a leaf page, there will be KeyDataEntrys instead.

Diagram

Recall that there will always be an even number of offsets and entries on a leaf page, with the first entry being a key, and the second being the data. Iterate over all the entries in pairs (a tumbling window of size 2), and if pair[0].data == target_key, then return pair[1].data as the found key. If was no matching key, then the key doesn’t exist in the B-Tree.

Task

Using the test data generated by gendata.py provided in Page Format, implement the support necessary to run:

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

#define DATABASE "testdata.bdb"

void test_get(DB* dbp, const char* keystr) {
    DBT key, data;

    // Zero-initialize key/data pair
    memset(&key, 0, sizeof(DBT));
    memset(&data, 0, sizeof(DBT));
    key.data = (char*)keystr;
    key.size = strlen(key.data);

    // Get data from the database
    int rc = dbp->get(dbp, NULL, &key, &data, 0);
    if (rc == 0)
        printf("key: %s, data: %s\n", (char *)key.data, (char *)data.data);
    else if (rc == DB_NOTFOUND)
        printf("key not found\n");
    else
        printf("Unknown error: %d\n", rc);
}

int main() {
    DB *dbp;
    int ret;

    // Initialize DB structure
    if ((ret = db_create(&dbp, NULL, 0)) != 0) {
        fprintf(stderr, "db_create: %s\n", db_strerror(ret));
        exit(1);
    }

    // Open the database
    if ((ret = dbp->open(dbp, NULL, DATABASE, NULL, DB_BTREE, DB_CREATE, 0664)) != 0) {
        fprintf(stderr, "dbp->open: %d\n", ret);
        goto err;
    }

    test_get(dbp, "bbbbbbbbbbbbbbbbbbbb");
    test_get(dbp, "kjshdfkhjdsfhdsj");
    test_get(dbp, "ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss");

err:
    if (dbp != NULL)
        dbp->close(dbp, 0);

    return 0;
}

Which should output:

key: bbbbbbbbbbbbbbbbbbbb, data: bbbbbbbbbbbbbbbbbbbb
key not found
key: ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss, data: ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss