BTREE
Section: C Library Functions (3)
Updated: 18 agosto 1994
Index Return to Main
Contents
NONMBRE
btree - método de acceso a bases de datos árbolB
SINOPSIS
#include <sys/types.h>
#include <db.h>
DESCRIPCIÓN
La rutina dbopen es la interfaz de biblioteca para los
ficheros de bases de datos. Uno de los formatos de fichero
soportado es el de los ficheros árbolB. La descripción general de
los métodos de acceso a las bases de datos se encuentra en dbopen(3),
esta página de manual describe únicamente información especifíca de
árbolB.
La estructura de datos árbolB es una estructura de árbol
balanceado y ordenado que almacena pares clave/datos asociados.
La estructura de datos específica del método de acceso a árbolB
proporcionada por dbopen se define en el fichero cabecera
<db.h> como sigue:
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;
Los elementos de esta estructura son los siguientes:
- flags
- El valor del campo de opciones se especifica mediante un
O-lógico de cualquiera de los siguientes valores:
-
- R_DUP
- Permite claves duplicadas en el árbol, es decir, permite la
inserción si la clave a ser insertada ya existen en el árbol. El
comportamiento por defecto, como se describe en dbopen(3),
es sobrescribir una clave coincidente cuando se inserta una nueva
clave o fallar si se especifica la opción R_NOOVERWRITE. La opción
R_NOOVERWRITE predomina sobre la opción R_DUP y si se especifica la
opción R_NOOVERWRITE, los intentos de insertar claves duplicadas en
el árbol fracasarán.
- Si la base de datos contiene claves duplicadas, el orden de
recuperación de los pares clave/datos es indefinido si se usa la
rutina get sin embargo, las llamadas a la rutina seq
con la opción R_CURSOR activa siempre devolverá el primero
``lógico'' de cualquier grupo de claves duplicadas.
- cachesize
- Un tamaño máximo sugerido (en bytes) de la memoria caché. Este
valor es sólo consultivo y el método de acceso reservará más
memoria antes que fallar. Ya que toda búsqueda examina la página
raíz del árbol, ocultar en caché las páginas más recientemente
usadas mejorará sustancialmente el tiempo de acceso. Además, las
escrituras físicas se demorarán tanto como sea posible, por lo que
una caché moderada puede reducir el número de operaciones de E/S de
forma significativa. Obviamente, usar una caché incrementa (pero
sólo incrementa) la probabilidad de corrupción o de pérdida de
datos si el sistema cae mientras se está modificando un árbol. Si
cachesize es 0 (no se especifica un tamaño) se utiliza un
tamaño de caché por defecto.
- maxkeypage
- El número máximo de claves que se almacenarán en una única
página. No implementado actualmente.
- minkeypage
- El número mínimo de claves que se almacenarán en una única
página. Este valor se usa para determinar qué claves se almacenarán
en páginas de overflow, es decir, si una clave o elementos de datos
es mayor que el tamaño de página dividido por el valor de
minkeypage, se almacenará en páginas de overflow en lugar de en la
propia página. Si minkeypage es 0 (no se especifica un
número mínimo de claves) se usa un valor de 2.
- psize
- Es el tamaño (en bytes) de las páginas usadas por los nodos del
árbol. El tamaño mínimo de página es 512 bytes y el tamaño máximo
de página es 64K. Si psize es 0 (no se especifica un tamaño
de página) se selecciona un tamaño de página basado en el tamaño de
bloque de E/S del sistema de ficheros subyacente.
- compare
- Es la función de comparación de claves. Debe devolver un entero
menor, igual o mayor que cero si se considera que el argumento de
la primera clave es, respectivamente, menor, igual o mayor que el
argumento de la segunda clave. Se debe usar la misma función de
comparación para un árbol dado cada vez que se abre. Si
compare es NULL (no se especifica un función de
comparación), las claves se comparan léxicamente, considerando las
claves más cortas menores que las claves más largas.
- prefix
- Es la función de comparación de prefijos. Si se especifica,
esta rutina debe devolver el número de bytes del argumento de la
segunda clave que se necesitan para determinar que es mayor que el
argumento de la primera clave. Si las claves son iguales, se
debería devolver la longitud de la clave. Dese cuenta que la
utilidad de esta rutina es muy dependiente de los datos pero, en
algunos conjuntos de datos, puede producir unos tamaños de árbol y
tiempos de búsqueda reducidos de forma significativa. Si
prefix es NULL (no se especifica una función de prefijo)
y no se especifca una función de comparación, se usa por
defecto una rutina de comparación léxica. Si prefix es NULL
y se especifica una función de comparación, no se hace comparación
de prefijos.
- lorder
- El orden de bytes para los enteros de los metadatos almacenados
en la base de datos. El número debería representar el orden como un
entero; por ejemplo, el orden `el byte de mayor peso el último'
(orden ascendente) sería el número 4321. Si lorder es 0 (no
se especifica un orden) se utiliza el orden del anfitrión
actual.
Si el fichero ya existe (y no se ha especificado la opción
O_TRUNC), se ignoran los valores indicados para las opciones de los
parámetros, lorder y psize, en favor de los valores usados cuando
se creó el árbol.
Los recorridos secuenciales hacia adelante de un árbol van desde
la clave más pequeña a la más grande.
El espacio liberado al borrar los pares clave/datos del árbol
nunca se recupera, aunque normalmente se pone a disposición para su
reutilización. Esto significa que la estructura de almacenamiento
árbolB es de sólo crecimiento. Las únicas soluciones son evitar
excesivas eliminaciones o crear periódicamente un árbol nuevo
recorriendo el que ya existe.
Todas las búsquedas, insercciones y eliminaciones de un árbolB
se terminarán en un orden O(logaritmo en base N) donde `base' es el
factor medio de relleno. Con frecuencia, la inserción de datos
ordenados en un árbolB produce un factor de relleno bajo. Esta
implementación se ha modificado para hacer las inserciones
ordenadas el caso mejor, produciendo un factor de relleno de
páginas mucho mejor de lo normal.
ERRORES
Las rutinas del método de acceso árbolB pueden fracasar y
asignar a errno cualquiera de los errores especificados en
la rutina de biblioteca dbopen(3).
VÉASE TAMBIÉN
dbopen(3),
hash(3),
mpool(3),
recno(3)
The Ubiquitous B-tree, Douglas Comer, ACM Comput. Surv.
11, 2 (June 1979), 121-138.
Prefix B-trees, Bayer and Unterauer, ACM Transactions on
Database Systems, Vol. 2, 1 (March 1977), 11-26.
The Art of Computer Programming Vol. 3: Sorting and
Searching, D.E. Knuth, 1968, pp 471-480.
FALLOS
Sólo se soportan los órdenes de bytes ascendente (el byte de mayor
peso el último) y descente (el bytes de menor peso el último).
Index
- NONMBRE
- SINOPSIS
- DESCRIPCIÓN
- ERRORES
- VÉASE TAMBIÉN
- FALLOS
This document was created by man2html, using
the manual pages.
Time: 06:16:27 GMT, January 22, 2005