dasf

Universidad Técnica Federico Santa María - Departamento de Informática

Estructura de Datos
Árboles B

Árboles B* Árboles B+

Prof.: Mauricio Solar

Prof.: Lorna Figueroa

Primer Semestre,
2010
1

Universidad Técnica Federico Santa María - Departamento de Informática

Introducción

• Necesidad de mantener índices en almacenamiento externo para
acceso a bases de datos,
•Problema: grave problema de la lentitud de estos dispositivos
se pretende aprovechar la gran capacidad de almacenamiento
para mantener una cantidad de información muy alta
organizada de forma que el acceso a una clave sea lo más
rápido posible.
• La letra B no significa "binario":
• Los árboles-B nunca son binarios.
• Tampoco es porque sean árboles de búsqueda, ya que en
inglés se denominanB-trees.
• Tampoco es porque sean balanceados, ya que suelen no
serlo.
2

Universidad Técnica Federico Santa María - Departamento de Informática

Introducción

• Normalmente se usan árboles binarios de búsqueda para ordenar
listas de valores, minimizando el número de lecturas, y evitando
tener que ordenar dichas listas.
• Desventajas ABB:
• Es difícil construir un ABB perfectamenteequilibrado.
• El número de consultas en el árbol no equilibrado es
impredecible.
• El número de consultas aumenta rápidamente con el
número de registros a ordenar.
• Para evitar estos inconvenientes se usan árboles-B, sobre todo
cuando se ordenan archivos, convertido en el sistema de
indexación más utilizado.
3

Universidad Técnica Federico Santa María - Departamento de InformáticaIntroducción

• Problema de los ABB al usar almacenamiento secundario:
• la búsqueda de un elemento requiere muchos accesos a disco
(extremadamente lento comparado con un acceso a memoria)
• Ej.: para un millón de elementos
⇒ Nº accesos a disco = O(h) = O(log2 1.000.000) ≈ 20
• Solución: conseguir mayor grado de ramificación para tener
menor altura en el árbol.

4

Universidad TécnicaFederico Santa María - Departamento de Informática

Introducción
• Particionar el ABB en páginas
• Mantener en memoria una de las páginas
• Con páginas de 100 nodos en un árbol de 106 nodos:
Nºmedio accesos = (log100 106) = 3 Aprovecha al máximo el acceso al disco.

⎣⎦

11

Universidad Técnica Federico Santa María - Departamento de Informática

Arboles B

• Generalización de un árbol2-3,
• Un árbol 2-3 es un árbol B de orden 3
• La ventaja de los árboles-B reside en los métodos para insertar
y borrar registros, que dejan siempre el árbol balanceado.
• Al igual que en el caso de los ABB, inserciones aleatorias de
registros dentro de un archivo pueden dejar el árbol sin
balancear.

12

Universidad Técnica Federico Santa María - Departamento de Informática

Árboles B– características

• Un parámetro muy importante en los árboles-B es el orden(m).
• El orden de un árbol-B es el número máximo de ramas que
pueden partir de un nodo.
• Si k es el número de ramas que parten de un nodo de un árbol-B,
el nodo contendrá k-1 claves.
• El árbol está ordenado.
• Todos los nodos terminales, (nodos hoja), están en el mismo
nivel.
• Todos los nodos intermedios,excepto el raíz, deben tener entre
m/2 y m ramas no nulas.

13

Universidad Técnica Federico Santa María - Departamento de Informática

Árboles B – características

• Todos los nodos intermedios, excepto el nodo raíz, deben tener
entre m/2 y m ramas no nulas.
• El máximo número de claves por nodo es m-1.
• El mínimo número de claves por nodo es (m/2)-1.
• La profundidad (h) es elnúmero máximo de consultas para
encontrar una clave.
• Perfectamente equilibrado.
• Disminuye la profundidad del árbol.

14

Universidad Técnica Federico Santa María - Departamento de Informática

Árboles B – características

• Página: nombre de los nodos.
• Se les accede en bloque.
• Como máximo: m ramas y m–1 claves
• Como mínimo: (m/2)+1 ramas y (m/2) claves
• La raíz puede estar...