Berkeley DB Reference Guide: Btree prefix comparison

Berkeley DB Reference Guide:
Access Methods

Btree prefix comparison

The Berkeley DB Btree implementation maximizes the number of keys that can be stored on an internal page by storing only as many bytes of each key as are necessary to distinguish it from adjacent keys. The prefix comparison routine is what determines this minimum number of bytes (that is, the length of the unique prefix), that must be stored. A prefix comparison function for the Btree can be specified by calling DB->set_bt_prefix.

(Btree구현에서는 내부페이지에 저장된 키의 최대값을 이웃키와 구별하기 위해 필요한 바이트만큼을 저장함으로서 결정할 수 있다.접두어비교루틴은 저정되어야 하는 이 최소바이트수를 결정한다.Btreee의 하나의 접두어 비교함수는 DB->set_bt_prefix를 호출하여 설정할 수 있다.)

The prefix comparison routine must be compatible with the overall comparison function of the Btree, since what distinguishes any two keys depends entirely on the function used to compare them. This means that if a prefix comparison routine is specified by the application, a compatible overall comparison routine must also have been specified.

(접두어 비교루틴은 Btree의 전체적 비교함수와 호환가능해야 한다.즉 접두어 비교함수가 설정되면 두키의 비교를 위해서 호환가능한 전체적인 비교함수도 설정되어야 한다.)

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 if 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:

u_int32_t
compare_prefix(dbp, a, b)
	DB *dbp;
	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 (b->size);
}

The usefulness of this functionality is data-dependent, but in some data sets can produce significantly reduced tree sizes and faster search times.

Berkeley DB Reference Guide:Access Methods

Btree prefix comparison

Berkeley DB Reference Guide:
Access Methods