Enter your search terms

GNU-Darwin Web Submit search form

Berkeley DB Reference Guide: Access Methods

Btree prefix function (bt_prefix)

A prefix comparison function for the Btree can be specified as part of the db_open call to open the database, specifically by setting the bt_prefix element of the DB_INFO structure.

The prefix comparison routine is used to compress keys stored on the Btree internal pages by minimizing the number of bytes that are stored to distinguish between two keys on the internal pages. The usefulness of this is data dependent, but in some data sets can produce significantly reduced tree sizes and therefore, search times.

Obviously, the prefix comparison routine must be compatible with the overall comparison function of the Btree. If no prefix comparison function is specified, and no overall comparison function is specified, a default, lexical prefix comparison function is used. If no prefix comparison function is specified, and an overall comparison function is specified, no prefix comparison is done.

Prefix comparison routines are passed pointers to keys as arguments. The keys are represented as DBT structures. The prefix comparison function must return the number of bytes of the second key argument that are necessary to determine that it is greater than the first key argument. If the keys are equal, the length of the second key should be returned. The only fields that the routines may examine in the DBT structures are data and size fields.

An example prefix comparison routine follows:

compare_prefix(a, b)
	const DBT *a, *b;
{
	size_t cnt, len;
	u_int8_t *p1, *p2;

	cnt = 1;
	len = a->size > b->size ? b->size : a->size;
	for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
		if (*p1 != *p2)
			return (cnt);
	/*
	 * They match up to the smaller of the two sizes.  Collate the
	 * longer after the shorter.
	 */
	if (a->size < b->size)
		return (a->size + 1);
	if (b->size < a->size)
		return (b->size + 1);
	return (a->size);
}