Árbol B*

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 18 de diciembre de 2016; las comprobaciones requieren 6 ediciones .

Un árbol B*  es un tipo de árbol B en el que cada nodo del árbol está lleno al menos ⅔ (a diferencia de un árbol B donde esta cifra es 1/2).

Los árboles B* fueron propuestos por Rudolf Bayer y Edward McCraith , quienes estudiaron el problema de la compacidad de los árboles B. El árbol B* es relativamente más compacto porque cada nodo se utiliza de forma más completa. En otros aspectos, este tipo de árbol no difiere de un árbol B simple.

Para cumplir con el requisito "el nodo está lleno al menos en 2/3", se debe abandonar el procedimiento simple para dividir un nodo desbordado. En cambio, hay una "transfusión" en el nodo vecino. Si el nodo vecino también está lleno, entonces las claves se dividen aproximadamente por igual en 3 nuevos nodos.

Un árbol B + que satisface estos requisitos se denomina árbol B *+ [1] .

Notas

1. ↑ Rigin AM , Shershakov SA SQLite RDBMS Extensión para indexación de datos mediante modificaciones de árbol B  . Actas del Instituto de Programación de Sistemas del RAS (Proceedings of ISP RAS) . Instituto de Programación de Sistemas del RAS (ISP RAS) (10 de septiembre de 2019). doi : 10.15514/ispras-2019-31(3)-16 . Consultado el 29 de agosto de 2021. Archivado desde el original el 29 de agosto de 2021.

Enlaces

• Entrada del diccionario de algoritmos y estructuras de datos para B*  -tree
• Donald Knuth . 4. Generación de todos los árboles. Historia de la generación combinatoria // El arte de la programación = El arte de la programación informática. - M. : "Williams" , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión