.\" Copyright (c) 1990, 1993 .\" The Regents of the University of California. All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" 3. All advertising materials mentioning features or use of this software .\" must display the following acknowledgement: .\" This product includes software developed by the University of .\" California, Berkeley and its contributors. .\" 4. Neither the name of the University nor the names of its contributors .\" may be used to endorse or promote products derived from this software .\" without specific prior written permission. .\" .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" .\" @(#) btree. 3 8.4 (Berkeley) 8/18/94 .\" %FreeBSD: src/lib/libc/db/man/btree. 3, v 1.3. 2.2 2001/12/14 18:33:49 ru Exp % .\" $FreeBSD: doc/ja_JP.eucJP/man/man3/btree. 3, v 1.4 2002/05/18 07:12:52 horikawa Exp $ .\" .Dd August 18, 1994 .Dt BTREE 3 .Os .Sh 명칭 .Nm btree .Nd "btree 데이타베이스 액세스 방식" .Sh 서식 .In sys/types.h .In db.h .Sh 해설 routine .Fn dbopen (은)는, 데이타베이스 파일에의 프로그램 라이브러리 인터페이스입니다. 서포트되고 있는 파일 형식의 1 개는 .Nm 파일입니다. 데이타베이스 액세스 방식의 일반적인 설명은 .Xr dbopen 3 에 있습니다. 이 메뉴얼 페이지는, .Nm 에 고유의 정보에 관해서만 설명하고 있습니다. .Pp .Nm 데이터 구조는, 관련하는 키 / 데이터의 페어를 격납하는, 정렬 끝난 밸런스를 잡힌 트리 구조입니다. .Pp .Fn dbopen 에 제공된다 .Nm 액세스 방식으로 고유의 데이터 구조는, 다음과 같이 .Aq Pa db.h 인클루드 파일에 정의되고 있습니다. .Bd -literal typedef struct { u_long flags; u_int cachesize; int maxkeypage; int minkeypage; u_int psize; int (*compare)(const DBT *key1, const DBT *key2); size_t (*prefix)(const DBT *key1, const DBT *key2); int lorder; } BTREEINFO; .Ed .Pp 이 구조체의 엘리먼트는 다음과 같습니다. .Bl -tag -width indent .It Va flags flag 의 값은 이후의 값의 .Em or (논리합)(을)를 취하는 것에 의해 정의됩니다. .Bl -tag -width indent .It Dv R_DUP 트리 내부에 중복 한 키를 허용 합니다. 즉, 삽입하는 키가 트리내에 이미 존재하는 경우에도 삽입을 허용 합니다. .Xr dbopen 3 에 기술된 디폴트의 동작으로서는, 새로운 키를 삽입할 경우에 일치하는 키를 덧쓰기하는지, 또는 .Dv R_NOOVERWRITE 플래그가 지정되어 있는 경우는 처리 실패합니다. .Dv R_DUP 플래그는 .Dv R_NOOVERWRITE 플래그에 의해 덧쓰기되어 .Dv R_NOOVERWRITE 플래그가 지정되어 있는 경우는, 중복 하는 키를 트리에 삽입하려고 하는 처리가 실패합니다. .Pp 데이타베이스에 중복 한 키가 포함되어 있는 경우, .Va get routine를 사용하면(자), 키 / 데이터의 페어의 취득의 순서는 미정도리가 됩니다. 그러나, R_CURSOR 플래그를 설정해 .Va seq routine를 호출하면(자), 중복 한 키의 논리적인 .Dq 최초 하지만 반드시 돌려주어집니다. .El .It Va cachesize 메모리캐슈의 시사하는 최대 사이즈 (바이트 단위). 이 값은 .Em 단지 어드바이스에 지나지 않고, 액세스 방식은 처리 실패하지 않고 많은 메모리를 할당합니다. 각 검색이 트리의 루트 페이지를 조사하므로, 가장 최근에 사용된 페이지를 캐쉬하면(자), 액세스 시간이 짧아집니다. 게다가 물리적인 기입은 가능한 한 지연 되므로, 적당한 캐쉬는 입출력 조작의 회수를 큰폭으로 감소할 수 있습니다. 분명하게, 캐쉬를 사용하면(자), 트리를 수정하고 있는 동안에 시스템이 크래쉬 했을 경우, 데이터가 파손 또는 상실될 전망은 증대합니다 (증대할 뿐입니다). .Va cachesize 하지만 0 (사이즈가 지정되어 있지 않다)의 경우, 디폴트의 캐쉬가 사용됩니다. .It Va maxkeypage 1 페이지에 격납되는 키의 최대수. 현시점에서는 실현되고 있지 않습니다. .\" The maximum number of keys which will be stored on any single page. .\" Because of the way the .\" .Nm .\" data structure works, .\" .Va maxkeypage .\" must always be greater than or equal to 2. .\" If .\" .Va maxkeypage .\" is 0 (no maximum number of keys is specified) the page fill factor is .\" made as large as possible (which is almost invariably what is wanted). .It Va minkeypage 1 페이지에 격납되는 키의 최소수. 이 값을 사용해, 오버플로우 페이지에 어느 키가 격납되는지를 판정합니다. 즉, 키 또는 데이터 구조가, minkeypage 치로 제산되었다 pagesize 보다 긴 경우는, 페이지 자체에가 아니고, 오버플로우 페이지에 격납됩니다. .Va minkeypage 하지만 0 (키의 최소수가 지정되어 있지 않다)의 경우, 값 2 가 사용됩니다. .It Va psize 페이지 사이즈는, 트리내의 노드에 사용되는 페이지의 사이즈 (바이트 단위)입니다. 최소 페이지 사이즈는 512 바이트이며, 최대 페이지 사이즈는 64K 입니다. .Va psize 하지만 0 (페이지 사이즈가 지정되어 있지 않다)의 경우, 페이지 사이즈는, 기반이 되고 있다 파일 시스템 입출력 블록 사이즈를 기초로 해 선택됩니다. .It Va compare compare 는 키 비교 함수입니다. 최초의 키 인수가 2 번째의 키 인수보다 작다고 생각될 때는, 0 보다 작은 정수를 돌려줄 필요가 있습니다. 2 번째의 키 인수로 같은이라고 생각될 때는, 0 을 돌려줄 필요가 있습니다. 2 번째의 키 인수보다 크다고 생각될 때는, 0 보다 큰 정수를 돌려줄 필요가 있습니다. 지정의 트리에 대해서는, 트리가 열릴 때마다, 같은 비교 함수를 사용할 필요가 있습니다. .Va compare 하지만 .Dv NULL 의 경우 (비교 함수가 지정되지 않는 경우), 키는 사전적으로 비교되어 짧은 키는 긴 키보다 작다고 보여집니다. .It Va prefix .Va prefix (은)는 접두어 비교 함수입니다. 지정하면(자), 이 routine는, 2 번째의 키가 되는 인수의 바이트수를 돌려줍니다. 이것은, 2 번째의 인수가 1 번째의 인수보다 큰 일을 판정하기 위해서 필요합니다. 키가 동일한 경우는, 키의 길이가 돌려주어질 것입니다. 이 routine의 편리함 입어 원째라고 데이터에 의존합니다. 그러나, 데이터 세트에 따라서는, 트리의 사이즈와 검색 시간을 큰폭으로 삭감할 수 있는 일도 있는 것에 주의해 주세요. .Va prefix 하지만 .Dv NULL (접두어 함수가 지정되어 있지 않다)에서 만나며, .Em 게다가 비교 함수가 지정되지 않는 경우는, 디폴트의 사전적인 비교 routine가 사용됩니다. .Va prefix 하지만 .Dv NULL (이어)여, 게다가 비교 routine가 지정되어 있는 경우, 비교는 행해지지 않습니다. .It Va lorder 격납된 데이타베이스메타데이타내의 정수의 바이트 순서. 숫자는 정수로서의 순서를 나타낼 것입니다. 예를 들어, 빅 endian순서에서는 숫자 4,321 이 됩니다. .Va lorder 하지만 0 의 (순서가 지정되어 있지 않다) 경우, 현재의 호스트 순서가 사용됩니다. .El .Pp 파일이 이미 존재하고 있는 경우 (게다가 .Dv O_TRUNC 플래그가 지정되어 있지 않은 경우), 파라미터 .Va flags , .Va lorder , .Va psize 에 붙어 지정된 값은, 트리가 작성되었을 때에 사용된 값을 위해서(때문에) 무시됩니다. .Pp 트리의 전방 시퀀셜 주사는, 가장 작은 키로부터 가장 큰 키로 향합니다. .Pp 트리로부터 키 / 데이터의 페어를 삭제하는 것에 의해 해방된 공간은, 다시 요구될 것은 없습니다만, 재사용을 위해서(때문에) 이용할 수 있도록(듯이) 되는 것이 보통입니다. 즉, .Nm 기억역은 성장만입니다. 유일한 해결책은, 과도한 삭제를 피하는 것, 또는 기존의 트리의 주사로부터 정기적으로 새로운 트리를 작성하는 것입니다. .Pp .Nm 안의 검색, 삽입, 및 삭제는 모두, 기저가 평균의 필 요인인 기저 N 의 O 의 대수로 완료합니다. 순서 붙일 수 있었던 데이터를 .Nm 에 삽입하면(자), 필 요인이 낮아지는 일이 자주 있습니다. 이 실장에서는, 순서 붙일 수 있었던 삽입이 최선의 케이스가 되어, 통상의 페이지 필 요인보다 훨씬 좋은 결과가 되도록(듯이) 수정되어 있습니다. .Sh 에러 .Nm 액세스 방식 routine는, 프로그램 라이브러리 routine .Xr dbopen 3 에 붙어 지정한 에러의 경우, 처리 실패해, .Va errno (을)를 설정할 가능성이 있습니다. .Sh 관련 항목 .Xr dbopen 3 , .Xr hash 3 , .Xr mpool 3 , .Xr recno 3 .Rs . %T "The Ubiquitous B-tree" . %A Douglas Comer . %J "ACM Comput. Surv. 11" . %N 2 . %D June 1979 . %P 121-138 .Re .Rs . %A Bayer . %A Unterauer . %T "Prefix B-trees" . %J "ACM Transactions on Database Systems" . %N 1 . %V Vol. 2 . %D March 1977 . %P 11-26 .Re .Rs . %B "The Art of Computer Programming Vol. 3: Sorting and Searching" . %A D. E. Knuth . %D 1968 . %P 471-480 .Re .Sh 버그 빅 endian 및 little endian의 바이트 순서만이 서포트 되고 있습니다.