Ergens deze week schreef je een regel die eindigde op ->where('email', $email). Je hebt er geen seconde over nagedacht. Hij kwam in twee milliseconden terug, je ging door, en dat was precies genoeg aandacht.
Onder die regel zat een datastructuur uit 1972.
Rudolf Bayer en Ed McCreight publiceerden dat jaar Organization and maintenance of large ordered indexes in Acta Informatica. Ze losten een probleem op voor een machine waar de meeste lezers nooit aan hebben gezeten: een IBM 360/44 met een 2311-disk, waarbij de index niet in het geheugen paste en elke pagina die je ophaalde echte milliseconden kostte op een draaiende schijf. Hun testset was 100.000 sleutels.
Dat ontwerp is nog steeds de index die je standaard krijgt in PostgreSQL, MySQL, SQL Server en Oracle, en de enige die SQLite ooit heeft gehad. Dezelfde structuur, onder dezelfde naam, met dezelfde taak: de B-tree.
Wat elke uitleg je geeft, en waar hij ophoudt
Zoek op "b-tree uitleg" en je krijgt honderd versies van hetzelfde artikel. Een plaatje van een boom. De invarianten: elke node bevat tussen de m/2 en m sleutels, alle bladeren liggen op dezelfde diepte, opzoeken kost O(log n). Misschien een animatie van een node die splitst.
Allemaal correct. Allemaal nutteloos om twee uur 's nachts.
Wat geen van die artikelen doet, is het plaatje verbinden met de regels die je allang volgt. Je weet dat de kolom waarop je een exacte match doet vooraan hoort in een samengestelde index. Je weet dat een lower() om een kolom heen je index laat verdampen. Je weet dat een covering index sneller is en dat je negende index de writes trager maakte. Je kent die dingen zoals je bijgeloof kent: het werkt, en je kunt de ene niet uit de andere afleiden.
Het is allemaal hetzelfde feit. De boom is gesorteerd, hij is in precies één volgorde gesorteerd, en hem zo houden is duur.
De rekensom is de hele truc
Begin met het getal dat B-trees saai maakt, in de goede zin van het woord.
InnoDB leest en schrijft in pagina's van 16KB, en een node is een pagina. Jeremy Cole heeft een echte tabel met een INT als primary key uit elkaar gehaald en gemeten wat erin past: ongeveer 1.203 verwijzingen naar onderliggende pagina's in een interne pagina, ongeveer 468 rijen in een bladpagina. Die verhouding, de fanout, bepaalt alles aan de leeskant.
| Boomhoogte | Bladpagina's | Rijen die erin passen | Indexgrootte |
|---|---|---|---|
| 2 | 1.203 | 563.000 | 18,8 MiB |
| 3 | 1,4 miljoen | 677 miljoen | 22,1 GiB |
| 4 | 1,7 miljard | 814 miljard | 25,9 TiB |
Lees die middelste rij nog een keer. Een tabel met 600 miljoen rijen erin heeft een primary key die drie niveaus diep is. Eén rij vinden kost drie pagina's.
PostgreSQL, met pagina's van 8KB, komt via een iets andere weg op ongeveer hetzelfde uit: rond de 600 onderliggende pagina's per interne pagina en 300 entries per blad, dus drie niveaus dekken zo'n 108 miljoen rijen, en meer dan 99% van de pagina's in de index zijn bladeren.
Dat laatste cijfer is de praktische clou. De interne pagina's zijn qua omvang een afrondingsfout en ze worden door élke query gelezen, dus zodra je database even draait staan ze in de buffer pool en blijven ze daar. Je lookup van drie pagina's is meestal twee reads uit het geheugen en één van schijf.
Die getallen komen wel uit één tabel van Cole met een INT als sleutel, dus beschouw ze als bovengrens: dikke rijen en brede sleutels drukken de fanout van je bladeren flink omlaag. Aan de vorm verandert dat niets. Een fanout in de honderden levert een boom op die maar een paar niveaus diep is, voor elke tabel die je ooit gaat hebben.
Bayer en McCreight optimaliseerden voor een apparaat waarop het ophalen van een pagina rampzalig was, dus bouwden ze iets dat laag en breed is: honderden onderliggende pagina's per node, en maar een handvol niveaus om af te dalen. Vierenvijftig jaar later is die schijf een NVMe geworden en is random access zo'n drie ordes van grootte goedkoper. Aan de structuur hoefde niets te veranderen. Zo ziet een goede datastructuur eruit.
Eén correctie die elke uitleg je schuldig is, en dit stuk ook: wat ik hier beschrijf is een B+tree, waarbij de rijen alleen in de bladeren zitten en die bladeren aan elkaar geregen zijn. Dat is wat al deze engines daadwerkelijk gebruiken. Het paper van Bayer en McCreight uit 1972 beschrijft de B-tree, en de B+tree is de verfijning die uit het gebruik ervan is voortgekomen. Iedereen noemt het resultaat toch een B-tree, inclusief de syntax van CREATE INDEX.
Eén keer gesorteerd, in één richting
De rest volgt uit die sortering.
Een B-tree op (status, created_at) is geen twee indexen. Het is één lijst, gesorteerd op status, en binnen elke status op created_at. Denk aan een telefoonboek op achternaam, en daarbinnen op voornaam.
Elke regel die je uit je hoofd hebt geleerd is nu gewoon een vraag over dat telefoonboek.
Waarom moet de eerste kolom in je WHERE staan? Omdat je elke Jansen meteen vindt, terwijl je voor iedereen die Pieter heet het hele boek moet doorlezen. Niets in de structuur weet waar de Pieters zitten.
Dit is trouwens ook de regel die stilletjes een stuk minder absoluut is geworden, en de vorm laat zien waarom. Oracle heeft index skip scan sinds 9i, MySQL sinds 8.0, en PostgreSQL kreeg het in september 2025 met versie 18. Een skip scan werkt precies zoals jij het met de hand zou doen: zoek de eerste achternaam op, doe je zoekactie binnen die groep, spring naar de volgende achternaam, herhaal.
Zo wordt één onmogelijke lookup duizenden goedkope lookups, en dat is een prima ruil bij twaalf verschillende statussen en een dramatische bij twaalf miljoen verschillende achternamen. De optimizer kijkt naar de cardinaliteit van je eerste kolom en beslist. Dat scherpt de regel aan in plaats van hem af te schaffen: je betaalt één keer per unieke waarde die vóór de kolom staat waar het je echt om ging.
Waarom slaat WHERE lower(email) = ? de index over? De boom is gesorteerd op email, en lower(email) is een andere sortering. De database zou die functie op elke entry moeten toepassen om te weten waar hij moet zoeken, en dat is precies de scan die je wilde vermijden. Dat is wat "sargable" betekent, en het is de reden dat je in plaats daarvan een functionele index aanmaakt: je sorteert de boom op de expressie waar je echt op zoekt.
Waarom staan gelijkheidskolommen vóór range-kolommen? Omdat je met een range in een reeks entries belandt in plaats van op één punt. Alles rechts van die eerste range is alleen nog binnen die reeks gesorteerd, dus het beperkt wel wat je terugkrijgt, maar niet wat er gelezen wordt. (status, created_at) werkt voor status = 'open' AND created_at > ?. Draai de kolommen om en de database loopt langs elk openstaand ticket dat ooit is aangemaakt.
Waarom is ORDER BY soms gratis? De bladeren vormen een doubly linked list in sleutelvolgorde. Past je sortering bij de index, dan komen de rijen al gesorteerd binnen en verdwijnt de sort uit het plan.
Waarom helpt een covering index zoveel? Een gewone index-scan levert je een verwijzing op, en daarna moet je de echte rij nog ophalen, wat weer een andere pagina op een andere plek is. Zet elke kolom die de query nodig heeft in de index en die tweede stap vervalt. Postgres noemt dat een index-only scan en laat je de extra kolommen met INCLUDE meeliften. Er zit een kanttekening bij die iets wezenlijks over de engine laat zien: Postgres moet nog steeds vaststellen of die rij zichtbaar is voor jouw transactie, dus een index-only scan raadpleegt eerst de visibility map. Op een tabel die continu verandert is die map koud en haal je de rij alsnog op.
Eén vorm. Vijf regels. Je hoeft ze niet meer uit je hoofd te leren.
De helft die niemand tekent
Elk plaatje in elke uitleg is een read. De boom ligt vast, de pijl wijst naar beneden, de rij komt terug.
Bij writes ga je pas echt betalen.
Voeg een rij toe en de engine moet in élke index op die tabel een entry kwijt, elk op zijn eigen gesorteerde plek, elk op een ander stuk schijf. Zit de bladpagina in kwestie vol, dan splitst hij: nieuwe pagina claimen, de helft van de records verhuizen, de bovenliggende pagina bijwerken. Zit die ook vol, dan splitst die op zijn beurt, en in het ergste geval loopt dat door tot aan de root en groeit de boom een niveau.
Dit is het mechanisme achter iets wat je vast al eens hebt zien gebeuren bij een tabel die al een paar jaar meegaat. Indexen worden er één voor één bijgezet om één trage query tegelijk op te lossen, en niemand haalt er ooit één weg, omdat weghalen riskant voelt en erbij zetten gratis voelde.
De write latency kruipt omhoog en bloat hoopt zich sneller op. Bij Postgres komt daar autovacuum bovenop: meer indexpagina's om op te ruimen, dus vaker draaien, en dat vecht met jouw writes om dezelfde I/O. Percona heeft die hele keten uitgeschreven. Kort samengevat: op een tabel met veel indexen weegt dat aantal zwaarder mee in je insert-tijd dan wat je verder ook kunt tunen.
De B-tree is een trade-off, en elke uitleg laat je maar één kant daarvan zien.
Waarom juist deze het waard is om te kennen
Ik kom steeds terug bij dit soort fundamenten omdat ze niet verouderen. De B-tree heeft het drumgeheugen overleefd, de draaiende schijf, drie generaties ORM en elk framework dat je beloofde dat je nooit meer over de database hoefde na te denken. De trie en depth-first search waarmee ik een woordspel snel maakte komen uit dezelfde periode en zijn even actueel.
Er is ook een directere reden. Een agent schrijft je met plezier een migratie die een index toevoegt, en meestal is dat een redelijke index. Wat hij er niet bij vertelt, is dat de kolomvolgorde niet past bij de query die hij moet bedienen, dat de index die hij toevoegt dezelfde eerste kolommen heeft als een index die je al hebt, of dat die tabel 4.000 writes per seconde te verwerken krijgt.
Die migratie beoordelen kost je vijf seconden als je de vorm kent. Ken je hem niet, dan is het blind vertrouwen. Dat is precies het argument om nooit code te shippen die je zelf niet snapt, toegepast op de kleinst denkbare diff. Datamodellering staat op mijn korte lijst van dingen die je nu goed zou moeten leren, precies om deze reden.
Bayer en McCreight hebben nooit verteld waar de B voor staat. Balanced, Bayer, Boeing, broad en bushy zijn allemaal voorbijgekomen. McCreight zei er zelf over dat je B-trees beter begrijpt naarmate je langer nadenkt over wat die B betekent.
Vierenvijftig jaar later is dat nog steeds het nuttigste wat er ooit over is gezegd.