miniatura|400px|dereita|alt=Exemplo sinxelo dunha árbore B+ que liga as chaves 1–7 cos datos d1–d7.|Exemplo sinxelo dunha árbore B+ que liga as chaves 1–7 cos valores d1–d7. A lista ligada (en vermello) permite un percorrido en orde rápido. O factor de ramificación desta árbore é .
Unha árbore B+ é unha árbore m-aria cun número variable, a miúdo grande, de fillos por nó. Unha árbore B+ consta dunha raíz, nós interiores e follas. A raíz pode ser unha folla ou un nó con dous ou máis fillos.
Unha árbore B+ pódese ver como unha variante da árbore-B na que os nós interiores gardan chaves separadoras e punteiros aos fillos, mentres que os rexistros ou os punteiros aos datos se gardan nas follas. Estas poden estar ligadas entre si para facilitar o percorrido ordenado.
O valor principal dunha árbore B+ está no almacenamento de datos para a súa recuperación eficiente nun contexto de almacenamento orientado a bloques, en particular nos sistemas de ficheiros. Isto débese sobre todo a que, a diferenza das árbores binarias de busca, as árbores B+ teñen un factor de ramificación moi alto (número de punteiros a nós fillos nun nó, tipicamente da orde de 100 ou máis), o que reduce o número de operacións de entrada/saída necesarias para atopar un elemento.
Historia Non hai un único artigo que introduza o concepto de árbore B+. A idea de manter todos os datos nos nós folla aparece repetidamente como unha variante interesante da árbore-B, introducida por R. Bayer e E. McCreight. Douglas Comer sinala nunha das primeiras revisións das árbores-B (que tamén abrangue as B+) que a árbore B+ se usou no software de acceso a datos VSAM de IBM, e remite a un artigo publicado por IBM en 1973.
Estrutura Estrutura de punteiros miniatura|304x304px|alt=Formato dun nó B+ con K=4.|Formato dun nó dunha árbore B+ con K=4 (pi representa os punteiros e ki as chaves de busca). Como outras árbores, as árbores B+ pódense representar como unha colección de tres tipos de nós: raíz, interior e folla. Nas árbores B+ mantéñense as seguintes propiedades: Se existe nun nó calquera da árbore B+, entón existe nese nó, para . Todos os nós folla teñen o mesmo número de antepasados (é dicir, están todos á mesma profundidade).
A estrutura de punteiros dos nós resúmese nas táboas seguintes: : número máximo de chaves de busca potenciais por nó, constante en toda a árbore. : o punteiro no índice de nó (con base cero). : a chave de busca no índice de nó (con base cero).
+ Estrutura de punteiros dun nó interior cando existe e existen existe e non existe nin nin existen : apunta á subárbore na que todas as chaves está baleiro
+ Estrutura de punteiros dun nó folla cando existe cando non existe e Apunta a un rexistro cun valor igual a Aquí está baleiro Apunta á folla seguinte da árbore
Límites dos nós Tipo de nó Número de chaves Número de nós fillos Mín. Máx. Mín. Máx. Raíz (cando é folla) 0 0 0 Raíz (cando é interior) 1 2 Nó interior Nó folla 0 0
Intervalos nos nós interiores Por definición, cada valor contido na árbore B+ é unha chave contida exactamente nun nó folla. Cada chave debe ser directamente comparable con calquera outra, o que forma unha orde total. Isto permite que cada nó folla manteña as súas chaves ordenadas en todo momento, o que permite que cada nó interior constrúa unha colección ordenada de intervalos que representan a extensión contigua dos valores contidos nunha folla dada. Os nós interiores superiores poden construír os seus propios intervalos, que agregan recursivamente os intervalos dos seus fillos. Finalmente, a raíz representa todo o rango de valores da árbore.
Para conservar esta información recursiva, os nós interiores deben conter ademais copias das chaves , con , que representan o elemento menor dentro do intervalo cuberto polo fillo de índice . Aquí é o número real de fillos dese nó interior.
Características A orde ou factor de ramificación é o número máximo de fillos dun nó interior. Coas capacidades da táboa anterior, sexan o mínimo de fillos dun nó interior non raíz e o mínimo de rexistros dunha folla non raíz. Se conta todos os niveis, incluídos a raíz e as follas: O número máximo de rexistros é . O número mínimo de rexistros é . Contando tamén as copias das chaves nos nós interiores, o mínimo é e o máximo . Se a raíz é a única folla (), contén entre 0 e rexistros. As cotas seguintes supoñen fixo; o número de accesos a nós debe distinguirse do custo de buscar ou desprazar chaves dentro de cada nó: O espazo necesario para almacenar a árbore é . Inserir un rexistro require operacións. Atopar un rexistro require operacións. Eliminar un rexistro (previamente localizado) require operacións. Realizar unha consulta de rango con elementos dentro do rango require operacións. A estrutura expándese ou contráese segundo aumente ou diminúa o número de rexistros, sen restricións de tamaño. As insercións e os borrados poden dividir, fusionar ou redistribuír nós e cambiar a altura, pero manteñen a cota logarítmica de accesos aos niveis. Os datos gárdanse nos nós folla, e unha maior ramificación dos nós interiores axuda a reducir a altura da árbore e, con ela, o tempo de busca. Por iso funciona ben nos dispositivos de almacenamento secundario. A busca é moi sinxela, porque todos os rexistros están nos nós folla, ordenados secuencialmente na lista ligada. Pódese facer recuperación por rango ou parcial usando a árbore B+; as ligazóns entre follas facilitan ese percorrido.
Algoritmos Busca Buscamos un valor na árbore B+. Isto significa que, partindo da raíz, buscamos a folla que pode conter . En cada nó determínase que fillo hai que seguir. Un nó interior ten como máximo fillos, cada un representando un subintervalo distinto. Selecciónase o fillo correspondente cunha busca linear entre as entradas e, ao chegar á folla, faise unha busca linear entre os seus elementos. Como só se percorre unha rama en cada nivel, acádase un tempo , onde é o número total de chaves almacenadas nas follas da árbore B+.
function search(k, root) is let leaf = leaf_search(k, root) for leaf_key in leaf.keys(): if k = leaf_key: return true return false
function leaf_search(k, node) is if node is a leaf: return node let p = node.children() let l = node.left_sided_intervals() assert let m = p.len() for i from 1 to m - 1: if : return leaf_search(k, p[i]) return leaf_search(k, p[m])
Este pseudocódigo usa índices baseados en 1: l[i] é a menor chave da subárbore p[i+1]. A igualdade co separador leva, polo tanto, ao fillo da dereita.
Inserción Buscar a folla correspondente e inserir nela o rexistro na posición ordenada. Se quedan como máximo rexistros, a inserción remata. Se a folla queda con rexistros, repartilos entre dúas follas e actualizar a lista ligada. Pódense deixar na esquerda e na dereita. Copiar ao pai a primeira chave da folla dereita como separador e engadir o punteiro a esa folla. O rexistro permanece na folla. Se o pai supera chaves, dividir tamén ese nó interior: promover unha chave central ao seu pai e repartir as restantes chaves e os punteiros. A chave promovida retírase dese nó interior, a diferenza da copia feita ao dividir unha folla. Repetir cara á raíz. Se esta se divide, crear unha nova raíz co separador e cos dous fillos.
As árbores B+ medran na raíz, non nas follas.
Carga masiva Dada unha colección de rexistros, queremos crear un índice de árbore B+ sobre algún campo chave. Unha opción é inserir cada rexistro nunha árbore baleira, pero é custoso, porque cada entrada require partir da raíz e baixar ata a folla axeitada. Unha alternativa eficiente é a carga masiva: Primeiro ordénanse as entradas segundo unha chave de busca en orde ascendente. Resérvase unha páxina baleira como raíz e insírese nela un punteiro á primeira páxina de entradas. Cando a raíz se enche, divídese e créase unha nova páxina raíz. Séguense inserindo entradas na páxina de índice máis á dereita, xusto por riba do nivel de follas, ata que todas as entradas estean indexadas.
Notas: Cando a páxina de índice máis á dereita por riba do nivel de follas se enche, divídese; esta acción pode, á súa vez, provocar a división da páxina de índice máis á dereita un paso máis preto da raíz; as divisións só se producen no camiño máis á dereita da raíz ás follas.
Borrado Primeiro localízase a folla e elimínase o rexistro. Se non existe, a árbore non cambia. Actualízanse os separadores afectados cando cambia a menor chave dunha subárbore.
Se a folla conserva polo menos rexistros, non necesita reequilibrado. En caso contrario, tentar redistribuír os rexistros cun irmán do mesmo pai que poida ceder un sen quedar por baixo do seu mínimo; actualizar o separador do pai. Se non se pode redistribuír, fusionar a folla cun irmán, reparar as ligazóns entre follas e retirar do pai o separador e o punteiro sobrantes. Se o pai queda por baixo do mínimo de fillos, aplicar redistribución ou fusión aos nós interiores, tendo en conta os separadores do nivel superior. A reparación pode propagarse ata a raíz. Se a raíz interior queda cun único fillo, substituíla por ese fillo. Unha raíz que tamén é folla pode quedar baleira.
A fusión pode propagarse ata a raíz, o que reduce a altura. miniatura|centro|alt=Borrado nunha árbore B+.|Borrado nunha árbore B+.
Implementación As follas (os bloques de índice inferiores) da árbore B+ están a miúdo ligadas entre si nunha lista ligada; isto fai máis simples as consultas de rango e a iteración ordenada. A diferenza dunha árbore B ordinaria, todos os rexistros da B+ están nas follas e poden percorrerse seguindo só esas ligazóns. Tamén se poden ligar as follas dunha árbore B, pero non abondan para enumerar todos os seus rexistros, xa que algúns se almacenan nos nós interiores. Por iso a B+ é especialmente útil como índice de base de datos, onde os datos residen tipicamente en disco.
Se un bloque ocupa bytes, cada chave bytes, cada punteiro bytes e a cabeceira bytes, un nó interior con fillos debe satisfacer . A capacidade depende, polo tanto, tanto das chaves como dos punteiros e da sobrecarga; as follas poden ter unha capacidade diferente segundo o tamaño dos rexistros.
Se os nós se organizan como matrices de elementos, pode levar tempo considerable inserir ou borrar un elemento, porque de media hai que desprazar a metade da matriz. Para evitalo, os elementos dun nó poden organizarse nunha árbore binaria ou B+ no canto dunha matriz.
As árbores B+ tamén se poden usar para datos en RAM, cun tamaño de bloque razoable igual ao da liña de caché do procesador.
A eficiencia de espazo pódese mellorar con técnicas de compresión, como a codificación delta das chaves. Para chaves de tipo cadea pódese gardar, no canto da chave completa, o prefixo máis curto que sexa estritamente maior (en orde lexicográfica) que a última chave do bloque anterior. Tamén hai unha forma simple de comprimir punteiros: se varios bloques consecutivos se almacenan de forma contigua, abonda con gardar un punteiro ao primeiro e o número de bloques.
Todas estas técnicas teñen inconvenientes: hai que descomprimir un bloque completo para extraer un só elemento, o que se pode paliar dividindo cada bloque en subbloques comprimidos por separado. Ademais, o número de elementos almacenados pode variar moito dun bloque a outro segundo a compresión.
Aplicacións Sistemas de ficheiros