Arboles b y b+
Páginas: 2 (353 palabras)
Publicado: 8 de diciembre de 2010
ARBOLES B
Los árboles-B ó B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B mantienen losdatos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos,existiendo una relación de orden entre ellos, tal como muestra el dibujo.
Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientespropiedades:
1. Cada nodo tiene como máximo M hijos.
2. Cada nodo (excepto raíz y hojas) tiene como mínimo M/2 hijos.
3. La raíz tiene al menos 2 hijos si no es un nodo hoja.
4. Todos losnodos hoja aparecen al mismo nivel.
5. Un nodo no hoja con k hijos contiene k-1 elementos almacenados.
6. Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertascondiciones:
1. El primero tiene valor menor que r1.
2. El segundo tiene valor mayor que r1 y menor que r2, etc.
3. El último hijo tiene valor mayor que rm.
ARBOLES B+
Unárbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas seencuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.
El número máximo de claves en un registro es llamadoel orden del árbol-B+.
El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol-B+ es n, cada nodo (exceptuando la raíz) debe tener entren/2 y n claves.
El árbol-B+ fue descrito por primera vez en el documento "Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indexes. Acta Informática 1: 173-189...
Los árboles-B ó B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B mantienen losdatos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos,existiendo una relación de orden entre ellos, tal como muestra el dibujo.
Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientespropiedades:
1. Cada nodo tiene como máximo M hijos.
2. Cada nodo (excepto raíz y hojas) tiene como mínimo M/2 hijos.
3. La raíz tiene al menos 2 hijos si no es un nodo hoja.
4. Todos losnodos hoja aparecen al mismo nivel.
5. Un nodo no hoja con k hijos contiene k-1 elementos almacenados.
6. Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertascondiciones:
1. El primero tiene valor menor que r1.
2. El segundo tiene valor mayor que r1 y menor que r2, etc.
3. El último hijo tiene valor mayor que rm.
ARBOLES B+
Unárbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas seencuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.
El número máximo de claves en un registro es llamadoel orden del árbol-B+.
El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol-B+ es n, cada nodo (exceptuando la raíz) debe tener entren/2 y n claves.
El árbol-B+ fue descrito por primera vez en el documento "Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indexes. Acta Informática 1: 173-189...
Leer documento completo
Regístrate para leer el documento completo.