A Thousand Transactions, Verified by Hand

Building a B+ tree from scratch — no internet to copy from, no concept of a unit test, just vi, gdb, and a stack of notebooks. Another patience story.

A look back — long before any of the tools we argue about now.

Another patience story. My memory’s hazy on whether it was sophomore or junior year, but the course was called something like “File Systems,” and it came after data structures. The final project was to implement a B+ tree properly, from scratch, and turn it in. I’ll say it again, because it matters: this was before you could browse the web in Netscape, so there was no copy-and-paste from anywhere outside. You built it out of your own head.

Workstation

“Computer” here didn’t mean the PC at home — it meant the university’s UNIX machines, gathered in some room on the fourth floor of one of the engineering buildings. Submitting homework by creating an account and sending it over email was a brand-new thing we were trying for the first time. Mostly, you did the work lined up at a terminal on campus, or huddled in small groups. I remember 8 a.m. classes, the long trudge up to campus from far away, and — youthful bravado — a stretch of trying to commute by bicycle.

Just putting several terminals on one screen with xterm and vi felt like a marvel. With help from the local gurus around me, things like flipping between multiple windows, or getting Korean input to work, happened for the first time. I couldn’t yet reach the machines from home over telnet, so this course in particular lives in late-night memory. It was before I’d discovered MUDs, so I was a fairly diligent student. In the days before any campus shuttle, I’d walk all the way up from the neighborhood at the foot of the hill — and the hollow-eyed, worn-out look probably started right around then.

vi + gdb

This was where I first learned vi. I almost never used a plain editor, and to this day I get anxious if I haven’t typed :wq. A lot of people I knew moved over to Emacs around then; I missed that window. Instead, all the patience of that period pooled into vi, with gdb running in the window beside it. It’s hard to convey now, but the method was to compute every scenario in advance, by hand and eye — writing out the memory states in a notebook — and then testing, one by one, whether the code I’d written actually behaved.

Get Chaesang Jung’s stories in your inbox

I didn’t know the concept of a unit test, so I verified everything by building a.out and stepping through the sequence by hand. The centerpiece of the assignment: to check the state after roughly a thousand transactions of input, I tested across nearly every notebook I owned. Of course the first run of all thousand didn’t come out right, and “debugging” meant chopping it into chunks of fifty, building each by hand, and checking whether my not-yet-trustworthy code produced what my scratch paper said it should. If the input had been a million instead of a thousand, maybe I’d have reached for something cleverer — but a thousand was doable by hand. It was a time when patience overwhelmed efficiency.

The B+ tree in the 2020s

It’s still there, sitting at the top of the data-structures boss ladder, and in the MySQL/RDB world it lives on, under the name index, as widely used as ever. Coding interviews don’t really ask about it. In practice, most people no longer wonder how it works at all — it’s become a thing you use without a second thought. Anything still in use after decades is, by that fact alone, kind of remarkable.

Postscript: I asked the AIs

I gave them a prompt — “write me code to create a B+ tree.” Gemini and ChatGPT both reached for Python. Gemini scrolled out a wall of code and then got cut off. ChatGPT showed me something that looked complete — but pasting it straight into VS Code, it threw an error.

Is AI just not there yet, or did I do something wrong? Both thoughts arrived at once. This was 2024. Should I have asked in English…?

Part of 90s Computer Science Stories — first-person notes on growing up with computers and studying CS in Korea in the 1980s and ’90s. See the full series →

Adapted from my Korean essay on Brunch: brunch.co.kr/@chaesang/50