Berkeley DB Reference Guide: Btree comparison

Berkeley DB Reference Guide:
Access Methods

Btree comparison

The Btree data structure is a sorted, balanced tree structure storing associated key/data pairs. By default, the sort order is lexicographical, with shorter keys collating before longer keys. The user can specify the sort order for the Btree by using the DB->set_bt_compare method.

(Btree 데이타스트럭쳐는 key/data 쌍을 저자하고 소트되고 밸랜스트리이다.디폴트로 정렬순서는 사전과 같은 순이다.즉 짧은 키가 긴키보다 선행한다.사용자는 DB->set_bt_compare 를 사용하여 소트순서를 설정할 수 있다.)

Sort routines are passed pointers to keys as arguments. The keys are represented as DBT structures. The routine must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second argument. The only fields that the routines may examine in the DBT structures are data and size fields.

(소트루틴에는 키값을 전달받는다.키는 DBT 로 표현된다.이 루틴은 첫번째 인자가 두번째 인자에 비해 0보다 적다,같다,크다를 리턴해야 한다.이 루틴의 첫번째 검사는 아마도 DBT의 data,size필드에 대한 비교를 수행하는 것일 것이다.)

An example routine that might be used to sort integer keys in the database is as follows:

int
compare_int(dbp, a, b)
	DB *dbp;
	const DBT *a, *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.

(주의:데이타는 처음에 메모리로 카피되어 적절히 바이트오더가 정렬되어야 한다.왜냐하면 버클리디비는 비교루틴에서 데이타의 바이트정렬을 보장하지 않기 때문이다.비교함수를 작성할때는 다른 아키텍쳐의 머신에서 생성된 데이타베이스는 다른 바이트오더를 가지고 있음을 유의하기 바란다.따라서 이것을 보정해야 한다.)

An example routine that might be used to sort keys based on the first five bytes of the key (ignoring any subsequent bytes) is as follows:

int
compare_dbt(dbp, a, b)
	DB *dbp;
	const DBT *a, *b;
{
	int len;
	u_char *p1, *p2;

	/*
	 * Returns:
	 *	< 0 if a < b
	 *	= 0 if a = b
	 *	> 0 if a > b
	 */
	for (p1 = a->data, p2 = b->data, len = 5; len--; ++p1, ++p2)
		if (*p1 != *p2)
			return ((long)*p1 - (long)*p2);
	return (0);
}

All comparison functions must cause the keys in the database to be well-ordered. The most important implication of being well-ordered is that the key relations must be transitive, that is, if key A is less than key B, and key B is less than key C, then the comparison routine must also return that key A is less than key C. In addition, comparisons will only be able to return 0 when comparing full length keys; partial key comparisons must always return a result less than or greater than 0.

It is reasonable for a comparison function to not examine an entire key in some applications, which implies that partial keys may be specified to the Berkeley DB interfaces. When partial keys are specified to Berkeley DB, interfaces which retrieve data items based on a user-specified key (for example, DB->get and DBcursor->c_get with the DB_SET flag), will not modify the user-specified key by returning the actual key stored in the database. The actual key can be retrieved by calling the DBcursor->c_get method with the DB_CURRENT flag.

(어떤 애플리케이션에서 비교함수가 전체키를 비교하지 않는것이 합리적이다.이것은 부분적 키가 버클리디비에 설정될수 있음을 내포한다.부분키가 버클리디비의 인터페이스에 설정될때 사용자정의 키(DB->get and DBcursor->c_get with the DB_SET flag참조)에 기초한 데이타아이템을 가져오는 인터페이스는 디비에 저장된 실제키에 의해 리턴된 사용자 정의 키를 고치지 않는다.그 실제키는 DBcursor->c_get (DB_CURRENT flag)로 얻을 수 있다.)

Berkeley DB Reference Guide:Access Methods

Btree comparison

Berkeley DB Reference Guide:
Access Methods