Estudiante

Árboles B y B+

Tema 6: Árboles B y B

+

1.Gestión mediante índices de grandes volúmenes de  información 2.Árboles B 3.Acceso secuencial indexado: Árboles B+

1

Árboles B y B+

Gestión mediante índices de grandes  volúmenes de información
Los índices simples proporcionan un método  sencillo y eficiente para manejar ficheros de registrosPero ¿Que ocurre si el volúmen del fichero es tal  que los índices no pueden mantenerse en memoria? Mantener un índice simple en disco, aunque  posible, es extremadamente ineficiente
Las inserciones deben ser ordenadas, y por tanto implican abrir huecos y  desplazar registros Los borrados implican eliminar huecos (en el fichero índice no puede utilizarse el  borrado lógico)Las búsquedas binarias requieren demasiados accesos. Buscar un registro entre  1000000 registros → ≃20 accesos
2

Árboles B y B+

Una posible alternativa consiste ordenar  lógicamente los registros siguiendo un esquema de  árbol binario de búsqueda
Izq    Der     Clave             Resto de campos... AbbChi01 BeaMyb01 BeaCal01 AbbFer01 PriIwa01 EagThe01 RoxLov01
0 34 68 102 136 170 204 238 272 306 340 374 408 442 ­1 68 170 204 ­1 ­1 272 272 ­1 408 374 ­1 ­1 ­1 34AbbChi01 | 102 BeaMyb01 | ­1 BeaCal01 | 136 PriIwa01 | 306 EagThe01 | ­1 AbbFer01 | 238 BeaTha01 | 340 BobLik01 | ­1 BeaShe01 | ­1 RoxLov01 | ­1 FleSar01 | ­1 EagHot01 | ­1 QueWea01 | ­1 BeaShe02 | Chiquitita|Abba|1979|3:34 My Bonnie|Beatles|1964|3:45 California Girls|Beach Boys|1965|1:27 I Wanna Be Your Lover|Prince|1979|1:40 The Long Run|Eagles|1979|1:15 Fernando|Abba|1976|3:35Thank You Girl|Beatles|1964|2:07 Like A Rolling Stone|Bob Dylan|1965|1:28 She Loves You|Beatles|1964|3:36 Love Is The Drug|Roxy Music|1976|3:03 Sara|Fleetwood Mac|1979|2:13 Hotel California|Eagles|1977|3:28 We Are The Champions|Queen|1977|2:16 She's A Woman|Beatles|1964|3:50

BeaTha01

BeaShe01 BeaShe02

BobLik01

FleSar01 QueWea01

EagHot01

Representación  lógica

Representación  física

3Árboles B y B+

Una pequeña cabecera en el fichero indica la  posición del nodo raiz del árbol Los nodos hoja son aquellos cuyos índices izquierda  y derecha apuntan a ­1 Representación muy compacta: tanto los datos como  los índices están almacenados en un único fichero Operaciones muy eficientes
Una búsqueda implica sólo O(log n) lecturas en el ficheroNo es necesario ordenar físicamente los datos. Los datos se insertan al final y se  enganchan al nodo hoja correspondiente en O(log n)  Los borrados aunque un poco más complejos, también requieren O(log n) lecturas

4

Árboles B y B+

Problema grave: desequilibrado del árbol tras varias  inserciones y borrados
Solución posible: utilizar un árbol balanceado (p. e. AVL), aunque resolver las  rotaciones en el fichero requiere nuevos accesosLa búsqueda binaria no es suficientemente eficiente El uso del disco es muy deficiente
Cada acceso implica leer un bloque, y de este bloque únicamente se utiliza un  registro, cuyos índices izquierda y derecha apuntan, con mucha probabilidad, a un  registro de otro bloque

5

Árboles B y B+

Los índices multinivel hacen un uso del disco mucho  más eficiente que los árboles binariosSe define un registro de claves, de tamaño igual a un bloque de disco o un  divisor de éste El índice de primer nivel consiste en un fichero de registros de claves con  apuntadores al fichero de datos El índice de segundo nivel sirve para indexar el índices de primer nivel y tiene la  misma estructura que éste. Cada entrada aquí incluye la clave de la primera entrada de cada registro del índice de primer nivel y un apuntador a éste El índice de tercer nivel indexa al de segúndo nivel, etc.
Fichero índice de segundo nivel
AbbChi01|BeaShe01|EagHot01

...

Fichero índice de primer nivel
AbbChi01|AbbFer01|BeaCal1|BeaMyb01 BeaShe01|BeaShe02|BeaTha01|BobLik01 EagHot01|EagThe01|FleSar01|PriIwa01

...

Fichero de datos

6

Árboles B y B+...