Estudiante
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+...
Regístrate para leer el documento completo.