Definition
Plain language
A way of organizing data so a program can find any record quickly, even among millions.
As stated in the literature
A balanced, sorted tree data structure giving logarithmic-time lookups, insertions, and deletions; the standard on-disk index for relational databases like SQLite, whose B-tree code requires a valid database state to exercise, which is why raw symbolic inputs couldn't reconstruct a triggering case.
Also called: B-trees
Why it matters: Without it, finding a single record in a large dataset would require slowly checking entries one by one, making big databases impractically slow.
For example, when a database has millions of customer records, a B-tree lets it jump straight to the one you searched for instead of scanning every entry.
Heard on the show
“And SQLite — this one is almost poetic — the symbolic engine actually triggered twelve errors inside the B-tree code, but they all required a valid database state.”Episode 014 — Why a Constrained Pipeline Beat a Full Coding Agent at Finding Bugs 30-to-1