Download Btrees(spanisch)

7.1 Búsqueda Externa
• Los algoritmos vistos hasta ahora son adecuados
cuando todos los datos están en memoria principal.
• Gran volúmen de datos: se recurre a memoria
secundatria (almacenamiento externo) incluso para
las claves.
Acceso: siempre igual a un bloque entero (página) de
datos, por ejemplo: 4096 Bytes.
Effizienz: Número de accesos a una página debe
mantenerse al mínimo!
1
Para búsqueda externa: Variante de árboles de
búsqueda con:
Knoten = Seite
Vielwegsuchbäume (árboles de búsqueda de múltiples
caminos)
2
Definición (Arbol de busqueda de multiples caminos)
El arbol vacio es {}.
Sean T0, ..., Tn Arboles de busqueda de multiples caminos de un
conjunto de claves S, und sea k1,...,kn una lista de claves con k1 <
...< kn. Entonces la serie
T0 k1 T1 k2 T2 k3 .... kn Tn
Es un Arbol de busqueda de multiples caminos cuando:
• Para todas las claves x deT0 se cumple: x < k1
• Para i=1,...,n-1, para todas las claves x en Ti se cumple : ki < x <
ki+1,
• Para cada clave x de Tn se cumple: kn < x .
3
Árbol B
Definition
Un árbol B de orden m ist es un Arbol de busqueda de multiples
caminos con las siguientes características
• 1  #(claves en la raíz)  2m
y
m  #(claves en nodo interno)  2m
• Todos los caminos de la raíz a una hoja son igual de largo.
• Cada nodo con s claves tiene exactamente s+1 hijos.
4
Beispiel: Ein B-Baum der Ordnung 2:
5
Abschätzungen zu B-Bäumen
Un árbol minimal de orden m y altura h tiene:
• Numero de nodos en el árbol izquierdo y derecho
1 + (m+1) + (m+1)2 + .... + (m+1)h-1
= ( (m+1)h – 1) / m.
La raiz tiene una clave , todos los otros nodos tiene m claves.
En total: Numero de claves n en un B-Baum de altura h:
n  2 (m+1)h – 1
Por lo tanto se cumple que para todo B-Baum de altura h con n
claves:
h  logm+1 ((n+1)/2) .
6
Ejemplo
Por lo tanto se cumple que para todo B-Baum de altura h con n
claves :
h  logm+1 ((n+1)/2).
Ejemplo: para
• Tamaño de página : 1 KByte y
• Cada entrada correspondiente a una clave: 8 Byte,
Se puede elegir m=63 y para
• Un número de datos de n= 1000 000
Se tiene
h  log 64 500 000.5 < 4 y con esto hmax = 3.
7
Algoritmos para insertar y eliminar claves en un
árbol B
Algorithmus insert (root, x)
//insertar clave x en el árbol con raíz root
buscar x en el árbol de raíz root ;
si no se encuentra
{ sea p hoja donde se terminó la búsqueda;
insertar x en la posición adecuada (ordenado);
si p tiene 2m+1 claves
{overflow(p)}
}
8
Algorithmus Split (1)
Algorithmus overflow (p) =
split (p)
Algorithmus split (p)
primer caso: p tiene un
padre q.
Dividir el nodo rebalsado. La
clave del medio va al padre.
Anmerkung: la división se
tiene que repetir hasta que
se llegue a la raiz si es
necesario, con lo que la
altura del árbol crece en 1.
9
Algorithmus Split (2)
Algorithmus split (p)
segundo caso: p es la
raiz.
Dividir el nodo
rebalsado . Abrir un
nuevo nivel hacia
arriba con una nueva
raíz que contenga la
clave que divide.
10
Algorithmus delete (root ,x)
//borrar clave x del árbol con raíz root
buscar x en el árbol con raíz root;
cuando se encuentra x
{ si x està en un nodo interno
{ intercambiar x con la clave siguiente mayor x'
// si x está en un nodo interno, hay una clave
// siguiente mayor que está en una hoja
}
sea p la hoja que contiene x;
borrar x de p;
si p no es la raíz
{ si p queda con m-1 claves
{underflow (p)} } }
11
Algorithmus underflow (p)
si p tiene un nodo hermano con s>m
{ balance (p,p') }
else
// como p no es la raíz, un hermano de p tiene que tener por
lo menos m claves
{ sea p' hermano de p; merge (p,p')}
12
Algorithmus balance (p, p')
// balancear p con su hermano p'
(s > m , r = (m+s)/2 -m )
13
Algorithmus merge (p,p')
// unir p con su hermano
realizar las siguientes operaciones:
Al final :
Si ( q != raíz) und (q
tiene m-1 claves)
underflow (q)
Else (si (q= raíz) y (q
vacío)) {liberar q y
hacer p la nueva
raíz}
14
Rekursion
Cuando por un underflow se llega a un merge, debe
eventualmente hacerse underflow de un nivel
más arriba.
Esto puede extenderse hasta la raíz.
15
Ejemplo:
ärbol B de
Orden 2
16
Costo
Sea m el orden del B-Baums,
n el número de claves.
Costo de la búsqueda, inserción y eliminación:
O(h) = O(logm+1 ((n+1)/2) )
= O(logm+1(n)).
17
Anmerkung:
B-Bäume auch als interne Speicherstruktur zu
gebrauchen:
Besonders: B-Bäume der Ordnung 1
(dann nur 1 oder 2 Schlüssel pro Knoten –
keine aufwändige Suche innerhalb von Knoten).
Aufwand für Suchen, Einfügen, Löschen:
O(log n).
18
Anmerkung: Speicherplatzausnutzung:
über 50%
Grund: die Bedingung:
1/2•k  #(Schlüssel in Knoten)  k
Für Knoten  Wurzel
(k=2m)
19
Noch höhere Speicherplatzausnutzung möglich, z.B.
über 66% mit Bedingung:
2/3•k  #(Schlüssel in Knoten)  k
für alle Knoten mit Ausnahme der Wurzel und ihrer
Kinder.
Erreichbar durch 1) modifiziertes Balancieren auch
beim Einfügen und 2) split erst, wenn zwei Nachbarn
ganz voll.
Nachteil: Häufigere Reorganisation beim Einfügen und
Löschen notwendig.
20