[abecedarius]

Usually in 8-bit BASICs the lines would be stored consecutively (not in separate malloced segments) with each line starting with its line number. Yes, this meant that GOTO required a search. Memory was a really central design constraint on these systems. I don't know how closely MS's BASICA on the PC followed this model, but the PC's starting configuration had 16k bytes of RAM.

[david-given]

Here's a description of the file format used by BBC Basic:

http://xania.org/200711/bbc-basic-v-format

That's Basic V, which was the variant used on the ARM-based Archimedes, but it's the same file format as the 6502 machine Basics.

Note that the line numbers used by GOTO and GOSUB were specially flagged --- this was so the RENUMBER command could find them. It also meant that computed gotos weren't renumbered...

(Of course, BBC Basic had proper named procedures and functions with local variables, but all self-respecting Basics had to support GOTO and GOSUB.)