El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Arbres B

Següent ►
►

L'AVL de la lliçó anterior és imbatible... mentre l'arbre càpiga a la RAM. Però imagina TaskFlow desplegat en una empresa amb deu milions de tasques: l'índex ja no cap en memòria i viu a disc, i el disc canvia les regles del joc — no es llegeix byte a byte sinó per blocs de milers de bytes, i cada lectura costa desenes de milers de vegades més que un accés a RAM. De sobte, la mètrica que importa no és "quantes comparacions faig" sinó "quants blocs llegeixo", i l'arbre binari, amb un mísero node per salt, llegeix un bloc gairebé sencer per aprofitar-ne uns pocs bytes. L'arbre B inverteix el disseny: nodes enormes, de la mida exacta d'un bloc, amb centenars de claus i fills cadascun — arbres baixíssims i amplíssims on tres o quatre lectures basten per trobar una clau entre milions. En aquesta lliçó entendràs per què existeix, com funciona la seva inserció amb divisió de nodes (amb esquemes, no amb una implementació completa), què hi afegeix la seva variant B+ i on te'l trobes cada dia: a l'índex de qualsevol base de dades.

Contingut

  1. El disc canvia les regles: blocs i cost d'accés
  2. Què és un arbre B: ordre, propietats i invariants
  3. Cercar en un arbre B
  4. Inserir: créixer partint nodes (splits)
  5. L'arbre B+: dades a les fulles, fulles encadenades
  6. On viuen: bases de dades i sistemes de fitxers — TaskFlow sobre SQLite
  7. ABC vs AVL vs B: la taula comparativa

El disc canvia les regles: blocs i cost d'accés

Al mòdul 1 vam veure la jerarquia de memòria de passada; ara ens toca la factura. Ordres de magnitud (arrodonits, però fidels):

Accés Cost aproximat Equivalència humana
RAM ~100 ns 1 segon
SSD (llegir un bloc) ~100 µs ~15 minuts
Disc mecànic (un bloc) ~10 ms ~1 dia

I el matís clau: el disc no ven bytes solts. Es llegeix per blocs (o pàgines, típicament 4-16 KB): demanar 8 bytes costa el mateix que demanar els 4 096 del bloc sencer. Dues conseqüències immediates:

  • El cost d'un algorisme sobre disc es mesura en nombre de blocs llegits, no en comparacions. Les comparacions dins d'un bloc ja carregat a RAM són gratis en comparació.
  • Un bon algorisme de disc ha d'aprofitar el bloc sencer cada cop que el paga.

Ara mira l'AVL amb aquestes ulleres. Deu milions de claus → altura ≈ 23. Cada salt de node a node és, en el pitjor cas, un bloc diferent (els nodes, creats en moments diferents, viuen dispersos): 23 lectures de bloc per portar... 23 nodes minúsculs d'unes desenes de bytes cadascun. De cada bloc de 4 KB pagat, n'aprofitem potser l'1 %. En un disc mecànic, 23 lectures són un quart de segon — per a una cerca. L'arbre binari és un disseny magnífic per a RAM i un malbaratament per a disc.

La idea que ho arregla és d'una lògica aclaparadora: si el bloc ve sencer de totes maneres, omplim-lo de claus. Un node de 4 KB pot acollir centenars de claus i punters a fills; amb centenars de fills per node, l'altura es desploma.

Què és un arbre B: ordre, propietats i invariants

Un arbre B d'ordre m és un arbre de cerca on cada node pot tenir fins a m fills. Les seves propietats:

  • Cada node guarda fins a m − 1 claus ordenades; un node intern amb k claus té exactament k + 1 fills.
  • Les claus d'un node actuen de separadors: el fill i conté només claus entre la clau i−1 i la clau i del pare — la generalització directa de "esquerra menor, dreta major" a molts fills.
  • Tot node (llevat de l'arrel) està almenys mig ple: com a mínim ⌈m/2⌉ − 1 claus. Res de nodes raquítics que malgastin blocs.
  • Totes les fulles són al mateix nivell: l'arbre B està perfectament equilibrat, sempre. Ni factors d'equilibri ni rotacions: el seu mecanisme de creixement (el veurem de seguida) fa impossible el desequilibri.
graph TD
    A["[ 20 | 40 ]"] --> B["[ 5 | 12 ]"]
    A --> C["[ 25 | 31 | 38 ]"]
    A --> D["[ 50 | 60 | 75 ]"]

Un arbre B d'ordre 4 (una "arrel" pedagògica de mida joguina): l'arrel té 2 claus i 3 fills; el fill del mig conté només claus entre 20 i 40. A la pràctica real, amb blocs de 4-16 KB, l'ordre m volta els centenars: i aquí hi ha el miracle de l'altura —

Claus totals Altura arbre binari equilibrat Altura arbre B (m = 200)
10 000 ~13 2
10 000 000 ~23 3
1 000 000 000 ~30 4

L'altura creix com log_m(n), i amb m = 200, log₂₀₀(10⁷) ≈ 3. Tres lectures de bloc per trobar una tasca entre deu milions (i a la pràctica menys: l'arrel i el segon nivell es queden a la memòria cau, a RAM). Davant de les 23 de l'AVL, és la diferència entre un índex usable i un que s'arrossega.

Cercar en un arbre B

La cerca generalitza el descens de l'ABC: a cada node, en lloc d'una comparació i dos camins, es busca la posició de la clau entre els separadors (dins del node es pot usar cerca binària — el mòdul 1 treballant dins de cada bloc!) i es descendeix pel fill del forat corresponent. Cercar el 31 a l'arbre del diagrama:

  1. Arrel [20 | 40]: 31 és entre 20 i 40 → fill del mig. (1 bloc llegit)
  2. Node [25 | 31 | 38]: el 31 és aquí. Trobada. (2 blocs llegits)

En pseudocodi (aquesta lliçó treballa amb pseudocodi i esquemes; la implementació completa d'un arbre B — amb la seva gestió de blocs, mínims d'ocupació i fusions en esborrar — és un projecte de setmanes que excedeix el nivell del curs, i a la pràctica l'escriuen els motors de bases de dades, no les aplicacions):

cercar(node, clau):
    i = posició de la primera clau del node >= clau        # cerca binària interna
    si claus[i] == clau: retornar el valor associat
    si node és fulla:    retornar NO_HI_ES
    altrament:           retornar cercar(fills[i], clau)   # <- 1 lectura de bloc

Cost: O(log_m n) lectures de bloc, amb O(log₂ m) comparacions gratis dins de cadascuna.

Inserir: créixer partint nodes (splits)

Aquí hi ha l'elegància de l'arbre B. Les insercions van sempre a una fulla (baixant com a la cerca), i la clau s'acomoda en ordre dins d'ella. I si la fulla ja és plena (té m − 1 claus)? Llavors es divideix (split):

  1. La fulla desbordada es parteix en dos nodes, cadascun amb la meitat de les claus.
  2. La clau mediana no es queda en cap dels dos: puja al pare com a nou separador entre els dos mitjos nodes.
  3. Si amb això el pare desborda, el pare es divideix igual... i la divisió es pot propagar cap amunt. Si desborda l'arrel, es divideix i es crea una arrel nova amb una sola clau: és l'únic moment en què l'arbre guanya altura.

Vegem-ho pas a pas, inserint 10, 20, 30, 40, 50 en un arbre B d'ordre 4 buit (màxim 3 claus per node):

Passos 1-3 — 10, 20, 30 caben a l'arrel-fulla:

graph TD
    A["[ 10 | 20 | 30 ]"]

Pas 4 — arriba el 40: la fulla tindria 4 claus. Split: es parteix en [10] i [30|40], i la mediana 20 puja... però no hi ha pare: es crea una arrel nova.

graph TD
    A["[ 20 ]"] --> B["[ 10 ]"]
    A --> C["[ 30 | 40 ]"]

Pas 5 — el 50 baixa a la dreta i hi cap: [30|40|50].

graph TD
    A["[ 20 ]"] --> B["[ 10 ]"]
    A --> C["[ 30 | 40 | 50 ]"]

Pas 6 — inserim el 60: la fulla dreta desborda, es parteix en [30] i [50|60], i la mediana 40 puja a l'arrel, que té lloc:

graph TD
    A["[ 20 | 40 ]"] --> B["[ 10 ]"]
    A --> C["[ 30 ]"]
    A --> D["[ 50 | 60 ]"]

Atura't en el detall que ho explica tot: l'arbre B no creix cap avall, creix cap amunt — les fulles es queden on són i és l'arrel la que, molt de tant en tant, s'eleva un pis. Per això totes les fulles són sempre al mateix nivell: van néixer al mateix nivell i només es reparteixen en horitzontal. L'equilibri perfecte no es manté amb rotacions correctores com a l'AVL: és estructuralment impossible desequilibrar-lo. (L'esborrat és el procés invers — nodes que cauen per sota del mínim es fusionen amb germans o els demanen claus en préstec — amb la mateixa garantia.)

En pseudocodi:

inserir(clau):
    baixar fins a la fulla corresponent (com a cercar)
    inserir la clau en ordre dins de la fulla
    mentre el node actual tingui m claus (desbordament):
        partir-lo en dues meitats
        pujar la mediana al pare (creant arrel nova si no hi ha pare)
        el node actual passa a ser el pare

Un split costa O(m) (repartir claus entre dos blocs), i n'hi ha com a molt un per nivell: inserció en O(log_m n) escriptures de bloc. I l'ocupació mínima del 50 % queda garantida de fàbrica: cada meitat d'un split neix just mig plena.

L'arbre B+: dades a les fulles, fulles encadenades

La variant que domina el món real és l'arbre B+, amb dos retocs sobre l'arbre B:

  • Els nodes interns només guarden separadors (claus de guia, sense dades associades); les dades completes viuen exclusivament a les fulles. Avantatge: sense dades a transportar, a cada bloc intern hi caben més separadors → ordre efectiu més gran → arbre encara més baix. (Conseqüència curiosa: les claus separadores poden aparèixer duplicades — una vegada com a guia a dalt i una altra amb les seves dades a la fulla.)
  • Les fulles estan encadenades entre si en una llista enllaçada ordenada (el mòdul 2 reapareixent a la sala de màquines de les bases de dades!).
graph TD
    A["[ 20 | 40 ]"] --> B["fulla: 5,10,12"]
    A --> C["fulla: 20,25,31"]
    A --> D["fulla: 40,50,60"]
    B -.->|següent| C
    C -.->|següent| D

Aquest encadenament és or per a la consulta estrella d'aquest mòdul: l'interval. A l'ABC/AVL, interval(a, b) navegava l'arbre amb podes; al B+, es baixa una sola vegada fins a la fulla d'a i després s'avança en línia recta per la cadena de fulles fins a passar-se de b — lectures seqüencials de blocs contigus, el patró d'accés més barat que existeix a disc. "Tasques amb id entre 1 000 i 5 000": un descens més un passeig. Pel mateix motiu, el recorregut complet en ordre ni tan sols toca els nodes interns.

On viuen: bases de dades i sistemes de fitxers — TaskFlow sobre SQLite

Els arbres B/B+ són, gairebé amb seguretat, l'estructura de dades que més vegades has usat avui sense saber-ho:

  • Bases de dades: els índexs de SQLite, PostgreSQL, MySQL (InnoDB), Oracle i SQL Server són arbres B+ (o variants molt properes). Cada CREATE INDEX en planta un.
  • Sistemes de fitxers: NTFS (Windows), APFS (Apple), Btrfs i ext4 (Linux) usen arbres B per a directoris i metadades — la jerarquia de carpetes de 06-01, indexada.

Tanquem el cercle amb TaskFlow. El dia que les seves tasques es mudin de les nostres estructures en RAM a una base de dades:

CREATE TABLE tasques (
    id        INTEGER PRIMARY KEY,   -- SQLite crea aquí un arbre B+ sobre id
    titol     TEXT,
    prioritat INTEGER,
    estat     TEXT
);

CREATE INDEX idx_prioritat ON tasques (prioritat, id);   -- la nostra clau composta!

SELECT * FROM tasques WHERE prioritat BETWEEN 1 AND 3 ORDER BY prioritat, id;

Llegeix la segona línia amb els ulls d'aquest mòdul: (prioritat, id) és exactament la clau composta que vam inventar a 06-04 per a l'índex d'urgències — la base de dades i tu heu arribat a la mateixa solució, perquè és la mateixa pregunta. I el SELECT final s'executa com acabem de descriure: descens al primer (1, ...), passeig per les fulles encadenades fins a passar (3, ∞), resultats ja ordenats sense ordenar res. Tot el mòdul 6, servit en tres línies de SQL — la diferència és que ara saps què hi ha a sota i per què és ràpid, que és el que separa qui usa una base de dades de qui l'entén.

ABC vs AVL vs B: la taula comparativa

ABC (06-04) AVL (06-05) Arbre B / B+ (06-06)
Fills per node ≤ 2 ≤ 2 fins a m (centenars)
Claus per node 1 1 fins a m − 1
Altura amb n = 10⁷ fins a 10⁷ (degenerat!) ~23 garantida ~3 garantida
Mecanisme d'equilibri cap rotacions (FE) splits/fusions: sempre perfecte
Hàbitat RAM (didàctic) RAM disc / blocs
Cost de cercar O(altura)... la que sigui O(log₂ n) comparacions O(log_m n) lectures de bloc
Intervals inordre amb podes inordre amb podes descens + fulles encadenades (B+)
L'implementa... tu (aquí) tu (aquí) / llibreries motors de BD i sistemes de fitxers

La progressió del mòdul, llegida de correguda: l'ABC va aportar la idea (comparar i descartar), l'AVL hi va afegir la garantia (equilibri mantingut), i l'arbre B adapta totes dues al maquinari (la unitat de cost és el bloc). Mateixa lògica, tres hàbitats.

Errors Comuns i Consells

  • Mesurar un arbre de disc en comparacions. La mètrica correcta són les lectures de bloc; dins d'un bloc a RAM, comparar és gratis a efectes pràctics. Confondre les mètriques porta a "optimitzacions" irrellevants.
  • Creure que la mediana es queda en una de les meitats de l'split. No: puja al pare com a separador. Si als teus esquemes els comptes de claus no quadren, revisa això — és el despiste número u en traçar splits a mà.
  • Pensar que l'arbre B necessita reequilibratge tipus AVL. No hi ha rotacions: créixer per dalt (split d'arrel) manté totes les fulles al mateix nivell per construcció. Són dues filosofies d'equilibri diferents.
  • Confondre B amb B+. Al B clàssic, els nodes interns també porten dades; al B+, només separadors, i les fulles van encadenades. Quan llegeixis "les bases de dades usen arbres B", gairebé sempre vol dir B+.
  • Consell pràctic: la propera vegada que una consulta SQL amb WHERE ... BETWEEN o ORDER BY vagi lenta, pregunta't si existeix un índex B+ les primeres columnes del qual casin amb la consulta (l'ordre de les columnes a l'índex importa: és l'ordre de la tupla de 06-04). EXPLAIN et dirà si el motor l'està usant.

Exercicis

Exercici 1: traçar splits a mà

En un arbre B d'ordre 4 (màxim 3 claus per node) inicialment buit, insereix en aquest ordre: 8, 5, 1, 7, 3, 12, 9, 6. Dibuixa l'arbre després de cada split, indicant quina clau puja. Quants splits es produeixen i quina és l'altura final?

Exercici 2: el compte del bloc

Un node d'arbre B+ intern ha de cabre en un bloc de 4 096 bytes. Cada clau (id de tasca) ocupa 8 bytes i cada punter a fill 8 més. (a) Quin ordre màxim m admet el bloc? (b) Amb aquest m, quantes tasques indexa com a màxim un arbre d'altura 2 (arrel + 1 nivell intern + fulles, suposant fulles de fins a 255 entrades)? (c) Quina altura necessitaria un arbre binari per a aquesta quantitat?

Exercici 3: triar estructura, hàbitat a hàbitat

Per a cada escenari de TaskFlow, tria entre dict/TaulaHash, ArbreAVL i arbre B+ (via base de dades), i justifica-ho en una frase amb la mètrica correcta: (a) memòria cau en memòria de sessions actives, consultada per token exacte; (b) índex en RAM de les 10 000 tasques de l'esprint per (prioritat, id), amb llistats per interval constants; (c) historial complet de 20 milions de tasques arxivades, consultat per intervals de dates.

Solucions

Solució 1

  • 8, 5, 1 omplen l'arrel: [1|5|8].
  • 7 desborda → split 1: meitats [1|5] i [8]... amb la mediana 7 pujant a una arrel nova. Ull: les quatre claus en joc ordenades són 1, 5, 7, 8; es parteixen com [1|5], puja el 7, queda [8]. Arbre: arrel [7], fills [1|5] i [8].
  • 3 baixa a l'esquerra: [1|3|5]. 12 baixa a la dreta: [8|12]. 9: [8|9|12].
  • 6 baixa a l'esquerra, que desborda (1, 3, 5, 6) → split 2: [1|3], puja el 5, queda [6]. Arrel: [5|7] amb fills [1|3], [6], [8|9|12].

Total: 2 splits, altura final 1 (arrel + fulles). Comentari: fixa't que les vuit claus han quedat repartides amb totes les fulles al mateix nivell i cap per sota del mínim (⌈4/2⌉ − 1 = 1 clau) — l'invariant s'ha mantingut sol, sense que cap regla externa hi intervingués.

Solució 2

(a) Un node amb k claus té k + 1 punters: 8k + 8(k+1) ≤ 4096 → k ≤ 255. Ordre m = 256. (b) Arrel amb 256 fills → 256 nodes interns → 256 × 256 = 65 536 fulles de fins a 255 entrades ≈ 16,7 milions de tasques amb altura 2 (tres lectures de bloc, i les dues primeres probablement a la memòria cau). (c) Un arbre binari necessitaria altura ⌊log₂(16,7·10⁶)⌋ = 23. Comentari: la moralitat en una frase — mateix logaritme, base diferent, i la base la dicta la mida del bloc: log₂₅₆ davant de log₂ és la diferència entre 3 lectures i 23.

Solució 3

(a) dict/TaulaHash: clau exacta, sense necessitat d'ordre, tot a RAM — O(1) imbatible; un arbre pagaria un logaritme a canvi de res. (b) ArbreAVL: intervals i ordre constants a RAM amb ids que arriben creixents — el hash no sap d'intervals i l'ABC degeneraria; el B+ seria sobreenginyeria sense disc pel mig. (c) Arbre B+ (base de dades): 20 milions no caben còmodament a RAM i la consulta és per interval — tres lectures de bloc i passeig per fulles encadenades; un AVL a disc faria ~24 salts de bloc per descens. Comentari: cap resposta no és "la millor estructura en abstracte"; les tres són "la millor per a aquell patró d'accés en aquell hàbitat" — el criteri que desenvoluparem a fons al mòdul 8.

Conclusió

L'arbre B completa l'escala del mòdul: quan les dades es muden a disc, la unitat de cost passa de la comparació al bloc, i la resposta és un arbre a la mida del bloc — nodes amb centenars de claus, altura 3 o 4 per a milions d'elements, equilibri perfecte mantingut per splits que fan créixer l'arbre per l'arrel, i en la seva variant B+, fulles encadenades que converteixen els intervals en lectures seqüencials. Ara saps què planta un CREATE INDEX i per què el BETWEEN de TaskFlow sobre SQLite volarà: és el mateix índex (prioritat, id) que tu vas construir a mà, en versió industrial. Ens queda una promesa per complir, i és antiga: al mòdul 4 vam usar heapq com a caixa negra per a la SafataUrgencies, jurant que algun dia l'obriríem. Aquell dia és la propera lliçó: el monticle, un arbre binari que renuncia a l'ordre total de l'ABC a canvi d'una sola cosa — tenir sempre el mínim a mà — i que, gràcies a la representació en array de 06-02, ni tan sols necessita nodes. Anem a obrir la caixa.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats