isam

Indexed-Sequential Files — machines/isam.shoddy

Summary

isam lets a Shoddy program save records to a file and find any one of them again later by a key — a name, an ID number, whatever makes that record unique. Think of it like a box of index cards kept in alphabetical order. On top sits a little tabbed guide that tells you exactly which card to pull, instead of flipping through the whole box. You open the file and get back a handle, which is your working connection to that box of cards.

The tabbed guide itself is saved on disk too, in a small companion file next to your data. So opening the box again later is instant — no re-sorting, no matter how many cards are in it. Every change you make is written straight to disk the moment you make it. So one handle is all you ever need: open the file, use db everywhere, close it when you're done.

A Brief History of ISAM

ISAM stands for Indexed Sequential Access Method. It's an idea from the 1960s, when IBM built it for the big business computers of the day. Companies back then had the same problem you'd have with a giant box of unsorted index cards. You could read through every card in order, which was fine for printing a whole report — but painfully slow if you just wanted to find "the one card for employee #4471." Or you could jump straight to one card, but then it was hard to read them all back out in a sensible order.

ISAM's big idea was to get both at once. Records were kept in order by their key. A separate index — like the tabs on a filing cabinet — let the computer jump straight to the record it wanted, without reading every card in front of it. This became one of the standard ways that banks, payroll systems, and other business software stored data for the next twenty-plus years. It was gradually replaced by more advanced systems: VSAM, and eventually the databases we use today.

But the core idea never went away: keep things in order, and keep a separate index that points to where each thing lives. It's still how things work today, just about everywhere you look. Every SQL database — MySQL, PostgreSQL, SQL Server, the database behind almost any app or website you've used — finds a row by key the same way. It doesn't scan the whole table. It walks an index (usually a tree-shaped one, a descendant of the same idea) straight to the answer. That's the difference between a search that takes a fraction of a second and one that takes minutes on a big enough table.

Search engines lean on the same trick at a much bigger scale. Instead of indexing rows by an ID, they index words by which pages contain them. So looking up "which pages mention this word" is also a fast index lookup instead of a read-everything scan. Different data, same core move: sort it, index it, and you can jump straight to the answer instead of hunting for it.

This machine borrows that same idea, without needing an actual 1960s mainframe. Like its ancestors — and like the databases that followed them — it keeps the index on disk as a tree, in a small companion file beside your data. The tree is a B+tree, the same shape SQL databases still use: a wide, shallow tree of pages that keeps keys sorted and quick to reach. Opening the file, looking something up, and saving it is all done with ordinary Shoddy values and functions — no special hardware, no punch cards required.

Why It's Useful

A lot of programs need to keep track of things that change all the time: prices go up, inventory gets sold, students get new grades. And they must remember those changes even after the program stops running. That means saving data to a file, and being able to find one record quickly — find student #4471, not "read every student until you happen to hit #4471." That's exactly what isam does. It saves records to a file and keeps a fast index, so you can look any one of them up by key right away, instead of scanning the whole file. Reach for it whenever a program needs to store a set of records between runs — inventory, accounts, a class roster — and needs to find, add, change, or remove one of them by key without re-reading everything else.

User's Guide

To use isam, you tell it three things about the kind of record you want to store: how to read one record from the file, how to write one, and how to get the key back out of a record once you have it (its name, its ID — whatever you'll look it up by). A key has to be a Number or a String, since those are the kinds of value Shoddy knows how to put in order.

Include "isam.shoddy"

Type Staff
    Name  As String
    Score As Number

Def RdStaff(f As Number) As Staff
    Staff(GetStr(f, 12), GetNum(f))

Def WrStaff(f As Number, s As Staff)
    PutStr(f, Name(s), 12)
    PutNum(f, Score(s))

Def StaffKey(s As Staff) As String
    Name(s)

Def Main()
    Let db = IsamOpen("staff.dat", 20, RdStaff, WrStaff, StaffKey)
    IsamInsert(db, Staff("ADA", 96))
    IsamInsert(db, Staff("LIN", 78))

    Print(Score(IsamGet(db, "ADA")))               ' 96
    Print(IsamCount(db))                            ' 2
    Each(IsamAll(db), Fn(s) => Print(Name(s) & ": " & Str(Score(s))))
                                                     ' ADA then LIN, key order

    IsamClose(db)

The 20 in IsamOpen is just the number of bytes one record takes up on disk — 12 for the name, 8 for the score, in this example. Your reader and writer need to agree on that number, or the file will be read back scrambled. A few things worth remembering:

One handle is all you need. Every change is written straight to the files the moment you make it — nothing waits in memory. So you open once and use the same db for everything until you close it, the way the example does. (IsamInsert, IsamUpdate, and IsamDelete do hand the handle back. An earlier version of this machine kept the index inside the handle, and code written for it threaded each returned handle into the next call. That still works, but there's no longer any reason to: the returned handle is the one you passed in, unchanged.)
Your data gets a travel companion. Opening staff.dat also creates staff.dat.idx next to it — that's the index, saved on disk so reopening is instant. If you copy or move the data file, bring the .idx along. If it ever goes missing, the next open quietly rebuilds it by reading the whole file once.
One program, one file, at a time. This isn't built for two programs to share the same file at once, and it won't survive your computer crashing mid-write. Keep it simple: one handle, one file.
You can read everything back in order, without a loop counter. IsamAll hands you every record, already sorted by key, as an ordinary list. IsamFirst, IsamNext, IsamPrev, and IsamLast let you step through one record at a time if you'd rather do that instead.
Looking up a key that isn't there stops your program. Most of the lookup and change words — IsamGet, IsamUpdate, IsamDelete, and a few others — will raise an error if you ask about a key that doesn't exist. Check first with IsamHas, or use IsamGetOr, which gives you a default answer instead of stopping the program.
Deleting a record frees its space. When you delete something, that slot in the file gets reused the next time you insert a new record, so the data file doesn't just keep growing. One exception: if your records are smaller than 8 bytes, freed slots can't be tracked and are never reused — see below for why. The index also keeps a small amount of permanent scaffolding as it grows — see below — but it's a few percent, not a leak that tracks your deletes.

Under the Hood: What's on Disk

You don't need any of this section to use the machine — it's here for the curious, and for anyone staring at the files in a hex viewer (a tool that shows a file's raw bytes).

The data file is the box of cards itself: one fixed-size slot per record, each slot being 1 + size bytes — a one-byte live flag, then the bytes your writer produced. Deleting a record flips its flag to dead and threads the slot onto a free list, a chain of slots waiting to be reused. The first 8 bytes of a dead slot's payload hold the slot number of the next free slot, so the free list costs no space of its own. One consequence: records smaller than 8 bytes can't hold that pointer, so their freed slots are simply never reused.

The index file (path & ".idx") is the tabbed guide. It starts with a 24-byte header: where the root of the tree is, how many records are live, and where the free list starts. After that come fixed-size pages holding a B+tree of order 16 — sixteen branches to a page. Leaf pages list records in key order and chain left to right, which is what makes IsamAll, IsamRange, and IsamNext walks cheap. Interior pages hold the signposts that steer a lookup to the right leaf.

Keys are never written into the index. Shoddy can't ask a value "are you a Number or a String?" at runtime. So instead of storing keys in some fixed-width encoded form, every index entry stores a slot number. The key is re-derived by reading that record and applying your keyOf — which is why both key types just work, with no maximum key length. The interior signposts must stay stable when slots are deleted and reused. So each leaf split appends one frozen, dead-flagged copy of a record (a "separator image") for the signpost to point at. That's the permanent scaffolding mentioned above — roughly one small slot per eight inserts. Along with index pages, which are never merged after deletes, it's the deliberate bit of waste this machine accepts. Shoddy by name.

What things cost: IsamOpen, IsamClose, and IsamCount are O(1) — constant time, however big the file is — because opening reads the header, never the records. Lookups, inserts, updates, deletes, and IsamNext descend the tree: a handful of pages, with one record read per key compared along the way. IsamPrev walks the leaf chain from the left up to your key, and IsamLast walks the whole chain — the two slowpokes of the family. If the .idx is missing beside a data file that has records, the next open rebuilds it with a one-time full scan. A stale .idx sitting beside a fresh, empty data file is detected and discarded. No crash safety, no sharing: one program, one live handle at a time.

Word Reference

Every word, plus the Isam type

The type

Word	Description
Isam	Your claim ticket for an open file: the two file connections and your reader, writer, and key functions, bundled into one value. You'll pass this to almost every other word below. It never changes after `IsamOpen` — all the state lives on disk.

Open, close

Word	Description
IsamOpen(path, size, rd, wr, keyOf)	Opens (or creates) the file at `path` — plus its index at `path & ".idx"` — and hands you back your ticket (`Isam`). Fast no matter how big the file is: it reads a small header, not every record. `size` is how many bytes one record takes up; `rd` and `wr` are your read/write functions; `keyOf` tells it how to find a record's key.
IsamClose(db)	Closes the file when you're done with it.

Looking things up

Word	Description
IsamHas(db, k)	True or False: is there a record saved under key `k`? Good to check before looking something up that might not be there.
IsamCount(db)	How many records are currently saved.
IsamGet(db, k)	Gives you the record saved under key `k`. Stops the program with an error if that key doesn't exist.
IsamGetOr(db, k, dflt)	Same as `IsamGet`, but gives you `dflt` instead of an error when the key is missing.

Changing things written straight to disk

Word	Description
IsamInsert(db, rec)	Saves a brand-new record. Stops the program with an error if a record with that key is already saved — use `IsamUpdate` instead if you mean to replace one.
IsamUpdate(db, rec)	Replaces the record that has the same key as `rec`. Stops the program with an error if there's no existing record with that key to replace.
IsamDelete(db, k)	Removes the record saved under key `k`. Stops the program with an error if that key doesn't exist.

Reading records back, in order

Word	Description
IsamAll(db)	Every saved record, as a list, sorted by key.
IsamRange(db, lo, hi)	Every saved record whose key is between `lo` and `hi` (both included), sorted by key.
IsamFirst(db)	The record with the smallest key. Stops the program with an error if nothing is saved yet.
IsamLast(db)	The record with the largest key. Stops the program with an error if nothing is saved yet.
IsamNext(db, k)	The record whose key comes right after `k`. `k` itself doesn't have to be saved — this finds the first record whose key is bigger than `k`, whether or not `k` is in the file. Stops the program with an error if there's nothing after `k`.
IsamPrev(db, k)	The record whose key comes right before `k`. Like `IsamNext`, works whether or not `k` itself is saved. Stops the program with an error if there's nothing before `k`.

Who Uses It

No machine and no mill includes it yet — its words are already at the reckoner's prompt through its seed. Its exercise otherwise lives in tst/ — isamtest.shoddy, isamdump.shoddy and isamfixture.shoddy.

The Machines It Uses

None — isam stands on the file and record builtins alone. It used to include seq without naming a word from it.

Not recio, despite appearances: isam speaks to the binary builtins — Seek, PutNum, GetStr and kin — directly. The two are siblings on the same foundation, not layers of one another.