I suppose the "binding" of the name "$a" to the value "1" is recorded in some data-structure (whatever that data-structure is called in the internals of Perl).

You're mixing compile-time events with run-time events.

The slot is added to the pad ("the data structure") at compile time (i.e. once per "my" in the code).

The assignment of "1" to the scalar occurs at run-time (i.e. once every time "my" is evaluated).

Under your model, the following code would add 8 entries to "the data structure" over time.

for (1..4) {
   my $a = 1;
   my $b = 2;
}
[download]

Perl only does that twice, at compile time.

(Independently, there's an optimisation in place that makes it so only two scalars are created in total. They are cleared and reused rather than freed.)

What happens in the interpreter when a statement such as "my $a=1;" is encountered?

At compile time, it declares the variable, i.e. adds a slot to the function's pad for $b.

At run-time, it assigns 1 to the variable after placing an instruction on the stack to clear (or replace) the variable on scope exit (the aformentioned optimisation).