Arowwai
Industries
ÁRBOL B
B TREE
By: Alexander Aronowitz
CONTENIDO
Introducción
Fundamentos del Árbol B-tree
Operaciones Fundamentales
Aplicación Principal
Demostración y Codificación
Conclusiones
Referencias
Terminologia
RAIZ: Es el punto de partida del árbol, el
elemento más alto en la jerarquía.
RAMA: Secuencia descendente de
nodos.
NODOS: Vértices de un árbol.
NODO PADRE: Nodo superior
NODOS HIJOS: Los nodos
descendientes inmediatos de un nodo.
HOJAS: Nodos sin hijos .
BOSUQUE: Un conjunto de árboles.
ÁRBOL B
Un Árbol B o B-árbol, es una estructura de datos de árbol de búsqueda
sofisticada y autoequilibrada que está diseñada para la gestión
eficiente de grandes conjuntos de datos.
¿Por que utilizarlo?
Optimizados para manejo de datos en disco
Minimiza el numero de accesos a disco
ÁRBOL B
Arbol B de orden N: Arbol N-ario
Es un arbol equilibrado
Con K claves en cada nodo y N hijos
Orden de complejidad: log_N N
Grado
Maximo de hijos
Numero Maximo de hijos que puede tener un nodo en un arbol B
Si existen K claves, entonces tiene k+1 hijos
Un arbol B de grado M puede tener M-1
Un arbol B de grado M puede tener M hijos
claves
Grado
Minimo de hijos
Un arbol de grado M con M hijos y M-1 claves
Los nodos tiene al menos M/2 hijos
Menos la raz, que puede tener menos hijos de lo obligado, incluso uno.
EJEMPLO
ÁRBOL B
En las ciencias de la computación, los árboles-B o B-
árboles son estructuras de datos de árbol que se
encuentran comúnmente en las implementaciones
de bases de datos y sistemas de archivos.
CARACTERISTICAS
Multicamino: Puede almacenar
varias claves dentro de cada
nodo.
Autoequilibrado: Mantiene el
equilibrio de su estructura a
medida que los datos se insertan
y eliminan, lo que garantiza un
rendimiento consistente
(típicamente logarítmico) para las
operaciones de búsqueda,
inserción y eliminación a gran
escala.
Operaciones Fundamentales
Estas permiten gestionar de forma eficiente grandes volúmenes de datos
manteniendo el árbol siempre balanceado y con acceso rápido a
cualquier elemento.
Cada una de estas operaciones funcionan siguiendo las reglas del árbol B,
es decir que todas las hojas permanezcan al mismo nivel y que cada nodo
conserve un número permitido de claves
Búsqueda
Inserción
Eliminación
Búsqueda
Consiste en localizar una llave recorriendo el árbol de forma
ordenada desde la raíz. Su objetivo es determinar si la llave existe y,
de ser así, encontrar el nodo donde se almacena.
¿Cómo funciona?
1. El elemento buscado se compara con los
elementos del nodo raíz.
2. Si los elementos son iguales, la búsqueda se
detiene.
3. Si el elemento es mayor que el elemento raíz,
la búsqueda continúa pero por el subárbol
derecho
Y en caso de que el elemento sea menor que el
elemento raíz, la búsqueda continúa con el
subárbol izquierdo.
Inserción
Permite agrega una nueva llave al árbol, para de esta manera asegurar
que este cumpla sus reglas, es decir, mantenerlo balanceado y que cada
nodo tenga el número mínimo de llaves.
¿Cómo funciona?
1. Se busca la posición correcta recorriendo el árbol desde la
raíz, comparando la nueva llave con las llaves del nodo.
2. Si la llave es mayor, se continúa por el subárbol derecho; si
es menor, por el subárbol izquierdo, hasta llegar a una hoja.
3. La llave se inserta en la hoja. Si la hoja queda con más
llaves que el máximo permitido, el nodo se divide: la llave
central sube al padre y los nodos resultantes se separan.
4. Si al subir la llave el padre también se llena, la división
continúa hacia arriba, incluso pudiendo crear una nueva raíz.
Eliminación
Consiste en retirar una llave asegurando que el árbol permanezca
ordenado y balanceado, es decir que los nodos tenga el número
mínimo de llaves. Todas las eliminaciones se realizan desde hojas, por
lo que si la llave está en un nodo interno, primero se traslada a una
hoja mediante su predecesor o sucesor.
¿Cómo funciona?
1. Se recorre el árbol desde la raíz hasta encontrar la llave; si no existe, se
reporta un error.
2. Si la llave está en un nodo interno, se reemplaza con su predecesor o
sucesor para trasladarla a una hoja.
3. Ya en la hoja, si tiene más llaves que el mínimo, se elimina
directamente.
4. Si la hoja tiene el mínimo de llaves, se intenta tomar prestada una
llave de un hermano; si no es posible, se combina con un hermano y una
llave del padre.
5. Si esta combinación deja al padre con muy pocas llaves, el ajuste
continúa hacia arriba, pudiendo reducir la altura del árbol.
APLICACIONES
Y CASOS DE
USO
Árboles B en bases de datos
modernas
Indexación de bases de datos: Son la base de los índices en SGBD, permitiendo
localizar rápidamente registros y mejorar el rendimiento de consultas.
Sistemas de archivos: Utilizados para gestionar directorios y metadatos (ej. Btrfs,
ReiserFS), garantizando acceso rápido y almacenamiento eficiente.
Indexación multinivel: Ideales para organizar grandes volúmenes de datos en
estructuras jerárquicas, reduciendo operaciones de E/S.
Caché y gestión de memoria: Ayudan a rastrear datos almacenados en caché y
optimizar la asignación de memoria, mejorando el rendimiento del sistema.
Aplicaciones prácticas de los árboles B
Indexación de Bases de Datos
Se usan para construir índices primarios, secundarios y compuestos.
Permiten localizar registros de forma rápida, mejorando el rendimiento de las
consultas.
Casos de uso:
Búsqueda de clientes por ID.
Consulta de productos dentro de un rango de precios.
Filtrado de registros por fecha.
Aplicaciones prácticas de los árboles B
2. Sistemas de Archivos
Los sistemas de archivos modernos (como Btrfs y ReiserFS) usan árboles B para
organizar directorios y metadatos.
Garantizan acceso rápido a archivos incluso cuando hay miles o millones.
Casos de uso:
Gestión de grandes carpetas con muchos archivos.
Operaciones rápidas de creación, lectura y eliminación de archivos.
Aplicaciones prácticas de los árboles B
3. Indexación Multinivel
Ideales para manejar bases de datos de gran escala.
Su estructura jerárquica reduce las operaciones de disco necesarias para
acceder a datos.
Casos de uso:
Sistemas de almacenamiento masivo.
Data warehouses con millones de registros.
Aplicaciones prácticas de los árboles B
4. Caché y Gestión de Memoria
Permiten rastrear datos en caché y optimizar la asignación de memoria.
Aseguran acceso rápido a los datos más utilizados.
Casos de uso:
Sistemas operativos que administran páginas de memoria.
Aplicaciones que guardan datos temporales de alta demanda.
Aplicaciones prácticas de los árboles B
CODIFICACIÓN
a
Problem 01 Problem 02 Problem 03
Lorem ipsum dolor sit Lorem ipsum dolor sit Lorem ipsum dolor sit
amet, consectetur amet, consectetur amet, consectetur
adipiscing elit. Nullam adipiscing elit. Nullam adipiscing elit. Nullam
laoreet risus fringilla, laoreet risus fringilla, laoreet risus fringilla,
egestas elit a, consequat egestas elit a, consequat egestas elit a, consequat
augue. Phasellus augue. Phasellus augue. Phasellus
sollicitudin felis mi, quis sollicitudin felis mi, quis sollicitudin felis mi, quis
egestas ex ornare sed. egestas ex ornare sed. egestas ex ornare sed.
Our Team
Aaron Loeb Alfredo Torres Juliana Silva Daniel Gallego Olivia Wilson
CEO & Founder Project manager CEO & Founder IT Expert Marketing Head
REFERENCIAS BIBLIOGRÁFICAS
Malik, D. S. (2013). Estructuras de Datos con C++. Cengage Learning Colombia.
https://bibliotechnia.com.mx/otros/visor/?bock=17351
Loza Washington (2023). Material Modelos Discretos Para Ingeniería - Arboles. ESPE.
Árboles B,B+ y B.Google.com.
https://sites.google.com/unsa.edu.pe/aspe/algoritmos/%C3%A1rboles-
multicamino/%C3%A1rboles-bb-y-b
Understanding the basics of B-Tree data structures. (2024, agosto 30). TiDB; PingCAP.
https://www.pingcap.com/article/understanding-basics-b-tree-data-structures/
Carrillo, A. G. (2005). Abstracción y estructura de datos en C+.
https://elibro.net/es/ereader/espe/167034
martino (2020). Arboles B [[Object Object]]. Youtube. https://www.youtube.com/watch?
v=Cqtc81Iee08
Resource Page
