alt=Unha raíz con dúas claves separa tres follas de claves ordenadas; cada rama indica un intervalo.|miniatura|311x311px|Exemplo dunha árbore B de grao mínimo 2. As claves de cada subárbore pertencen ao intervalo delimitado polas claves do seu pai. Unha árbore B é unha estrutura de datos de procura equilibrada na que cada nodo pode almacenar varias claves ordenadas e ter varios fillos. Todas as follas están á mesma profundidade, e as operacións de inserción e eliminación conservan límites de ocupación dos nodos. Esta organización permite manter unha colección dinámica de claves con custos logarítmicos de procura e actualización, e resulta especialmente apropiada cando os datos se transfiren en bloques entre niveis de memoria.
A estrutura é unha base dos índices de bases de datos e de sistemas de almacenamento. O seu interese non se limita ao número de comparacións: agrupar moitas claves nun nodo permite reducir o número de bloques que se deben ler para localizar un rexistro. Na práctica, a expresión «índice de árbore B» pode designar tamén variantes próximas, en particular a árbore B+, cuxas entradas de datos se concentran nas follas.
Unha árbore B non é unha árbore binaria: o número de fillos dun nodo adoita ser moi superior a dous. Tampouco almacena necesariamente os rexistros completos en todos os nodos. A disposición concreta de claves, identificadores, páxinas e valores depende da variante e do sistema que a emprega.
Historia e motivación Bayer e McCreight desenvolveron a estrutura para organizar índices ordenados de gran tamaño. O artigo publicado en 1972 describiu un esquema que conservaba a eficiencia de procura, inserción e eliminación sen reorganizar periodicamente todo o ficheiro. A relación entre tamaño da páxina, número de entradas por nodo e altura da árbore constituíu unha parte esencial da proposta.
As árbores binarias equilibradas permiten buscas logarítmicas en memoria, mais cada paso pode requirir acceder a unha localización diferente. Nos dispositivos organizados en bloques, unha lectura transfire moitos bytes á vez. Se só se aproveita unha clave desa transferencia, desaprovéitase parte do traballo. A árbore B aumenta a ramificación para que unha páxina permita decidir entre numerosos subintervalos.
Esta motivación segue sendo pertinente en xerarquías con memoria principal, cachés e almacenamento persistente, aínda que os seus custos relativos cambien. A elección do tamaño dos nodos non depende unicamente da capacidade do disco: tamén interveñen a localidade, a compresión, o procesamento de comparacións e a concorrencia. A familia de técnicas modernas conserva a estrutura ordenada, pero adapta a representación aos dispositivos e ás cargas de traballo.
Estrutura e invariantes Existen convencións diferentes para definir a «orde» dunha árbore B. Unha definición habitual utiliza o grao mínimo . Cada nodo non raíz contén entre e claves. Un nodo interno con claves ten fillos. A raíz non baleira ten polo menos unha clave e, se é interna, polo menos dous fillos; todas as follas están no mesmo nivel.
As claves dun nodo están ordenadas. Se son , o primeiro fillo contén claves menores ca , os fillos intermedios conteñen os intervalos entre claves consecutivas e o último contén claves maiores ca . Esta descrición supón claves distintas. Un sistema con duplicados debe definir como ordenalos e representalos, por exemplo engadindo un identificador de rexistro ou agrupando varias referencias baixo unha clave.
O equilibrio non se obtén rotando arbitrariamente unha rama longa. A igualdade de profundidade das follas consérvase mediante operacións locais de división, redistribución e fusión. A altura só aumenta cando se divide a raíz e só diminúe cando unha raíz interna perde todas as súas claves e é substituída polo único fillo que queda. Así, a modificación da altura afecta simultaneamente a todos os camiños ás follas.
Os límites de ocupación garanten que unha árbore alta contén moitas claves. Se a altura é , medida en arestas entre raíz e folla, e hai claves, a ocupación mínima implica
A cota non afirma que todas as árbores teñan exactamente esa altura; expresa o peor caso baixo esta convención. A cantidade de claves que cabe fisicamente nunha páxina pode variar se as claves teñen lonxitude variable.
Operacións básicas
Procura Para localizar unha clave compárase coas claves da raíz. Se coincide cunha delas e a variante almacena alí a entrada buscada, a procura remata. Se non coincide, as claves delimitan un único intervalo e, polo tanto, un único fillo polo que continuar. Nunha folla, a ausencia da clave permite concluír que non está no índice. As buscas por predecesor e sucesor aproveitan a mesma orde.
Dentro dun nodo poden empregarse unha procura secuencial, unha procura binaria ou métodos adaptados á representación. Unha páxina pequena pode favorecer un percorrido simple; claves longas, compresión por prefixos e comparacións de cadeas poden modificar o custo efectivo. O número de accesos a bloques e o número de instrucións do procesador son métricas distintas, polo que unha análise en termos dunha delas non substitúe automaticamente a outra.
O índice tamén pode responder a un intervalo de claves. Primeiro localiza o extremo inicial e despois percorre as entradas na orde apropiada. En variantes B+, a ligazón entre follas facilita ese percorrido sen volver á raíz para cada rexistro. A saída de moitos resultados ten un custo inevitable proporcional aos datos devoltos, aínda que localizar a primeira entrada sexa rápido.
Inserción e división Unha inserción busca a posición ordenada da nova clave. Se a folla dispón de espazo, a operación consiste en inserir a entrada e desprazar as necesarias. Se un nodo alcanza a súa capacidade, unha división reparte as claves entre dous nodos e promove unha clave separadora ao pai. O pai pode necesitar á súa vez outra división. alt=Tres etapas mostran un nodo cheo, a promoción da mediana e a inserción dunha nova clave na folla dereita.|miniatura|464x464px|División dunha raíz chea nunha árbore B de grao mínimo 2 e inserción da clave 25. A clave 20 pasa a separar os dous intervalos. Na formulación de grao mínimo , un nodo cheo con claves divídese en dous nodos de claves e promove a clave mediana. Un algoritmo descendente pode dividir os nodos cheos antes de entrar neles, asegurando espazo para a eventual promoción. Outras formulacións admiten primeiro o desbordamento e reparan despois no camiño de volta; non deben mesturarse os límites dunha convención co procedemento doutra.
Por exemplo, nunha árbore de grao mínimo 2, o nodo [10, 20, 30] está cheo. A división promove 20 e produce e . A inserción posterior de 25 corresponde ao nodo dereito, que pasa a conter [25, 30]. Se o nodo inicial era a raíz, créase unha nova raíz con 20; a profundidade de ambas as follas aumenta igualmente.
Eliminación e fusión Eliminar unha clave pode deixar un nodo por baixo da ocupación mínima. Se un irmán adxacente ten claves de sobra, redistribúense entradas a través dunha clave do pai. Se non é posible, fusiónanse dous nodos e a clave separadora intermedia nun único nodo. A perda dunha clave no pai pode obrigar a reparar tamén o nivel superior.
Na árbore B clásica, a clave que se elimina pode estar nun nodo interno. Un procedemento substitúea polo seu predecesor ou sucesor e elimina a entrada correspondente nun nivel inferior, ou fusiona os fillos apropiados antes de continuar. O tratamento exacto depende de se se reparan preventivamente os nodos mínimos durante o descenso ou se se corrixe a falta de ocupación despois.
Estas regras preservan os intervalos e a profundidade das follas. Un motor de bases de datos pode, con todo, pospoñer a compactación física, marcar entradas como mortas ou empregar políticas máis flexibles de ocupación. Esa implementación non debe describirse como se executase necesariamente o algoritmo elemental de eliminación en cada modificación lóxica.
Custos e organización en páxinas alt=Curvas de altura mínima por capacidade para ramificacións 2, 8 e 64, que medran por chanzos ao aumentar o número de claves.|miniatura|376x376px|Modelo ilustrativo dunha árbore perfectamente chea: unha maior ramificación permite almacenar máis claves con poucos niveis. Non representa tempos medidos nin a ocupación mínima dunha implementación real. No modelo de memoria externa, un bloque contén unidades de datos. Unha ramificación proporcional a permite realizar buscas en transferencias de bloques, baixo as hipóteses de tamaño e ocupación correspondentes. A memoria principal adoita conservar a raíz e outros nodos superiores, reducindo aínda máis as lecturas físicas dunha procura concreta.
A maior ramificación reduce a altura, pero non é gratuíta. Os nodos máis grandes poden requirir mover máis bytes nas actualizacións; unha ocupación elevada deixa pouco espazo para novas claves; e as claves extensas diminúen o número de separadores por páxina. Compresión de prefixos, separadores abreviados e factores de recheo son técnicas para xestionar estes compromisos.
Unha carga masiva de datos ordenados pode construír as follas e os niveis superiores de maneira secuencial. Esta operación difire de inserir unha a unha todas as claves, que pode provocar divisións repetidas. Reservar espazo libre durante a construción permite absorber futuras insercións, pero incrementa inicialmente o tamaño do índice. A mellor política depende de se a carga é principalmente de lectura, de inserción ordenada ou de actualización dispersa.
Variantes Na árbore B+, os nodos internos actúan como directorio e as entradas de datos están nas follas. Unha clave separadora pode repetirse entre un nodo interno e unha folla, sen que iso signifique almacenar dous rexistros distintos. Os enlaces laterais entre follas permiten percorridos ordenados e consultas por intervalo. Esta separación simplifica moitos índices de bases de datos e dá ás páxinas internas unha representación diferente da das follas.
As árbores B* buscan unha ocupación mínima maior mediante redistribucións con irmáns e divisións que implican máis dun nodo. O asterisco forma parte do nome da variante; non indica unha relación co algoritmo de procura A*. As vantaxes de ocupación deben ponderarse fronte á complexidade das modificacións e ao número de páxinas implicadas.
As árbores B-link engaden información lateral que permite continuar unha procura cando unha división concorrente cambiou a estrutura. O traballo de Lehman e Yao formulou un método de concorrencia que evita bloquear todo o índice durante modificacións locais. A información adicional permite recoñecer que a clave pertence a un irmán situado á dereita e avanzar cara a el.
Adaptación á memoria principal As árbores CSB+ de Rao e Ross adaptan a organización B+ ao aproveitamento das liñas de caché. Os fillos dun mesmo nodo almacénanse de maneira contigua, de modo que basta un punteiro ao primeiro e un desprazamento para localizar os demais. O espazo que ocupaban parte dos punteiros pode dedicarse a claves, aumentando a información útil que proporciona unha transferencia. Esta contigüidade debe conservarse durante as divisións: as variantes propostas intercambian memoria reservada, movemento de nodos e custo das actualizacións. O resultado non se explica só pola altura da árbore, senón tamén pola súa disposición física.
Outra liña é a Bw-tree, que separa as páxinas lóxicas da súa localización física mediante unha táboa de correspondencias e representa actualizacións con rexistros de cambios. A súa proposta evita peches curtos de exclusión mutua para certas modificacións concorrentes e consolida periodicamente os cambios. Esa propiedade concirne ao acceso á estrutura, non elimina por si soa os requisitos de illamento e recuperación das transaccións que a empregan.
Bases de datos e persistencia